注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Codeforces 170 div1  

2013-03-01 01:42:38|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
蛋疼的比赛啊
真心是奇葩了,如果不是附赠了E这道大裸的费用流
我估计就只做出A了
B的构造一直WA
C好像是稍稍理解错题意了
以上两个都是-3囧。。。
不过最终借助E的费用流模版和好多人估计没有用模版结果打错了
顺利rank40了
只可惜是开小号参加的。。。错失了涨rating的机会啊
===============================================================
现在更新题解。
A题:是很简单的并差集的题目。用了几乎14分钟才过的。我就不说我题目看了好久好久。

B题:给定两个数n,m (2*n>=m>=n),要求给出一组点集,使得由这些点集组成的点数最多的凸多形的点数刚好为m。
当时考场上,我是yy了一个二次函数然后将其平移——似乎答案是对的,但是我没有几何板,手画了蛮久觉得没错交上去——结果样例都没过。正解是膜拜了rng_58的代码才知道,将二次函数沿原点中心对称并互相远离。感觉比我的高明多了。

C题:n*m的网格,两个人游戏,操作是可以在网格的格线上画一笔,使得每次操作画过的路径必须有没有被画过的,不能画者输。
开始我看错题了,考场上死活过不了。
首先行和列显然可以分开考虑。每行每列也是独立的。
对于一条线段,其sg函数就是其没被画过的长度。。。考场上怒打了个表
所以其实就是根据蛋疼的输入,统计出所有没有被画过的线段长度,逐个异或起来就行了。
至于要求先手必胜的第一步,考虑线段x,要求(x-y)^ans^x为0。那么y=x-ans^x。
然后就没有然后了。
令人惊讶的是,我由于是直接在考试时代码上修改的,于是代码好长好长,很多都是复制粘贴——没想到代码长度还可以排在第一版。其它人究竟得写多麻烦才能让代码比我还长啊。

D题:好长的题目。就是每道题目有一大一小两组数据,必须过小数据才能做大数据。做小数据和大数据都有相应的分数,和相应的时间。通过大数据是有一定的失败概率。罚时是最后一次成功提交的代码。要求最大化期望分数的同时最小化罚时。
主要是题目太长了。。。所以比赛时没几个人做了。但其实是挺简单的dp。
概率部分其实以前cf考过。
注意做题顺序和期望分数没有关系。
假设已经决定了做哪些题目,考虑顺序,那么小数据永远成功,做题时间无论如何都会累加进罚时,无需考虑,只考虑大数据的排列。交换相邻两组数据的排列,那么变化是线性的,所以最终排序一定是确定的(同noip某无聊题目)
于是就可以dp了——f[i][j],表示前i道题目,时间为j,最大化期望分数与其最小化罚时。
分数很好算,直接就是普通的背包。
罚时,如果只做小数据,就可以直接加上。否则,那么设当前罚时为k,有100%的概率加上小数据的分数,有失败概率*以前的罚时,有成功概率*当前时间。
注意用long double ,不然精度会成问题。

E题:平面上有n个点,要求组成最小的生成树,使得每个点只与y坐标比其低的点相连,且每个点往下连的点数至多为2。
裸的费用流,暂时不想吐槽了。
  评论这张
 
阅读(173)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017