c++&oi

二中开学模拟赛(2)

第一次评测后 是第二,而且分数 奇低,不想说了。感觉和昨天的数学一样悲剧了~
然后发现各种问题,第二题全场爆零,第四题数据是原设计的10倍,标程只能过一个点。。。
纠正了这些后复测:300+,勉强比汪同学高一点。
话说麻同学来上课了,于是吵了很多,但大家发挥都不错,
汪同学300+,吴天舒279,陆瑾聪200。。后面的普遍100左右。

我们发现是学c的人多了。。。。。然后又怂恿了两个人转c。。。。

说说题目,
第一题:忽略了全是0的情况。。。。90
第二题:flood-fill,(题目描述的就是flood。。。)AC
第三题:数学题,因式基本定理及其推论。。AC
第四题:求逆序对数,经典分治就不说了,于是想标新立异。
一上来想到平衡树,SBT不会写,SPLAY又觉得太长了。于是想线段树,好像用不起来。
最后剩下时间不多了,忽然蒙出了树状数组,于是狂写。
本来题目设计的是两种方法都能过的,由于复测时,数据没改(原设计的10倍),所以只能拿一半分。。。。
后来发现经典分治1.08s ,树状数组2.73s(最大点),其实也不是很大的差距。

试题

maxmin

area

explorer(25行的压缩版)

negsort(AC,43行的基础代码)
(最新,在linux下测得最大点时间0.604s,完全AC)

negsort(50,树状数组)
(最新,在linux下测得最大点时间1.093s,还说的过去。)

最终结论:由于有重复相等的问题,所以SBT和SPLAY不能很好的解决这个问题

posted on 2011-09-11 19:51 zyn.cpp 阅读(144) 评论(0)  编辑 收藏 引用


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


<2011年11月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿

随笔档案(57)

文章档案(13)

搜索

最新评论

阅读排行榜

评论排行榜