c++&oi

SDOI-07-DAY1

做了SDOI第一轮的一试题,差点被完虐。。。
内存限制竟然全部是2MB!!而且linux下arbiter,2MB竟然无法检测,全部判定为Wrong Answers!!
浪费了我好多时间。
第一题,递推+高精度,类似于AHOI2010的送分题。
我自以为聪明,用了和递推一样复杂度的模拟,结果90分。
原来,我那种算法对于n==1是不成立。。。。
(前几名中好像只有一个人AC了,其他和我一样90)
第二题,真的是模拟了,但需要一定的技巧,果断AC。
然后发现这个题我虐爆全场了,可能是因为我用cpp的原因。
第三题,最小路径覆盖。没有思路,本想写搜索,显然没有时间。
于是想贪心,考虑到答案可能会根据数据规模呈对数级增长,于是直接输出
2*int(log(n+m)/log(3.141592653*2))
【常数全是瞎编的,唯一的确定的是那个n+m,技巧就是随便弄几个小数据,都满足即可】
结果过了2个点。
后来看了题解,是转化成二分图做,正在研究中。
最后90+100+20=210,SD第4,考虑到最后一题爆0的概率,SD第5还有的
(NO3,4,5都是最后一题偏分的。。。最强的骗了30分)
(NO1,2 AC了最后一题,结果第二题。。。。)
第一题AC代码(M=1时输出2^D)

第二题模拟链表水掉(手写的万能线性表传说)

第三题是这样构图的:原边数n,构建一个X,Y集合各有n个节点的二分图,X表示发出,Y表示接受,
原图中a->b的有向边转化成二分图中x[a]与y[b]之间的无向边(目前见过的二分图都是无向的)
然后求出最大匹配数M 。 最终结果为n-M。我只有记结论的水平,证明略。
第三题AC代码(DINIC求最大匹配)


posted on 2012-04-07 17:27 zyn.cpp 阅读(218) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年4月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

导航

统计

常用链接

留言簿

随笔档案(57)

文章档案(13)

搜索

最新评论

阅读排行榜

评论排行榜