Archive for November, 2011

NOIP2011 完结了


22 Nov

这回主要是求稳,Day1 早上有个小插曲,被黄蜂蛰了3次,就这样 一瘸一拐地进了考场。T_T

大概用了30-60分钟写完一二题,发现二题比意想中的水,怀疑是不是大家都写了前两道,于是略有压力地写第三题。不是很习惯屏幕的比例,上下太窄了,每次能看到的代码只有很少一部分,字迹还有些模糊。第三题花的时间出乎了想象,弄完就只剩半小时了。于是改变策略去检查一二题。直到剩下5分钟时才猛然发现三题囧了——没考虑拿出来的那块掉下来的情况。这可是个Fatal Error,于是赶紧改。但是恼人的是怎么改都错了,样例都输-1了。 时间所剩无几,我干脆放弃修改,把原来那个代码硬着头皮交了。事实证明我这样做是明智的。

总之,Day1有些遗憾。

Day2吸取了Day1的教训,把终端字体改小了,并且按了自动调节钮把字迹弄清晰了。果然,一题水了,二题刚开始读错了题意,不过很快就发现了。接着就很自然注意到了单调性,一看范围,出题人意图很明显要求一个二分和线性的验证。但是验证却一直想不到怎么弄,有点被题意恶心到了。干脆先写了个二分加裸验证出来,一写完就发现可以转化成询问区间字段和的问题,自然先到树状数组。可是如此复杂度就是O(n logn logn)的了,应该有70吧,果断想三题。发现三题是我最讨厌的乘车问题,看得出来DP可以得60%,但是怎么思路都不明确。估计这题是整次考试压轴的,于是放了下,去看看二题有没有优化余地,重读二题代码,意识到只询问不修改,树状数组基本就是牛刀啊,直接记前缀和就得了。写好了拍了一会儿,在造数据过程中发现必须S弄大些才能让答案不总是一个值,进而查看题目S范围,大惊失色——忘开long long了,仔细把全部int检查一遍逐个看是不是该换成long long。心有余悸,三题已经无从下手,果断dfs裸之,因为此时只剩半个小时了。

二试纠正了一个大错误,比一试好啊。

这样mayan无法估计,但应该至少有30分,总分理想情况应该是460。

接下来就是为验证是不是理想情况而挣扎。我的记忆像内存掉电了之后一般逐渐凌乱不清:记不清qc那题究竟Y变量有没有开long long,就是说有可能为此丢失大量分数。纠结了好久,通过对记忆清晰的一些证据进行间接推断发现,是定义成ll(typedef long long ll)的,但是脑海中又似乎记得那里有个高亮说明是int而非ll。还发现hotel一题中虽然结果用了ll,但是可能过程中一处溢出。搞得我神经都要崩溃了。

最后看到自己的代码时,qc那道果然推理是正确的,用了ll,hotel有极限数据溢出的可能。

然后自己的成绩——470,mayan居然有个-1的点独立于30%的弱数据之外,得了40。其他4题全部AC,bus也裸到了30。

hotel居然没有极限数据,汗啊。。结果数据很极限很强的反而是我没问题的qc,有如天助。

这次的题型太过单一了,没有对一些很有用的模型的考查,DP和图论都没有(bus那道算作DP也重其量1/6)。考查的内容就是裸,裸,裸,还有二分。神马玩意儿,没有区分度啊!特别是学得少的同学占足了便宜,这套题4道门槛都很低,用for循环就可以结束战斗。。

万事俱备,只欠东风。


11 Nov

NOIP2011 两天,每天3小时3道题。

7:30到高新校区的考场,8:30开考

可以使用STL, freopen

long long 输出用%lld

比较输出时忽略行末空格和文末换行

 

做完题检查空间,时间,输入输出规模(是否爆int/long long),文件名(.in .out .cpp), 输出格式(是否按题目要求)

无题


08 Nov

Radix Sort && Counting Sort && Pigeonhole Sort && Bucket Sort


05 Nov

一直以来就没有搞清楚基数排序(Radix Sort)计数排序(Counting Sort)还有桶排序(Bucket Sort)的关系,今天wiki了一下,总算有了答案。

基数排序是利用排序关键字具有字典序特征的特点,对关键字进行分割,分若干轮子排序来达到最后使整个序列排好序的效果。至于子排序,可以以是其他的各种排序方法,基数排序仅仅指的是关键字分割这一思想。

计数排序顾名思义,就是开一个与关键字相匹配范围的表,对数据进行登记(即计数)。再通过按顺序遍历表,算出表中每个关键字序比它小的关键字有多少个。最后重新遍历原数据,根据处理过的表直接得出应该放的位置。注意表中记录的仅仅是数值,而没有把待排序的对象放进去。

这个算法有个特殊应用,如果需要排序关键字就是对象的全部,就可以在遍历表时,直接输出表中对应数值个相同对象就行了。

而桶排序是指将数据按关键字放入表中后,分别递归地对每个表内部进行排序,再按序遍历表输出。

基数排序的子排序算法常常使用计数排序实现(就是网上一搜一大把的那种开3个数组for3次,下标嵌套3层的那种)

有些资料上什么链表式基数排序又是怎么回事呢?

链表式是指子排序不是使用计数排序,而是一种叫鸽巢排序(Pigeonhole Sort)算法,其实就是桶排序省掉“递归地对每个表内部进行排序”步骤得到的算法,实际上递归的那部分被基数排序的多轮排序给完成了,使用了计数的基数排序本质上是拥有递归思想桶排序的一种特殊实现。

 

参考文献:

http://en.wikipedia.org/wiki/Radix_sort

http://en.wikipedia.org/wiki/Counting_sort

http://en.wikipedia.org/wiki/Pigeonhole_sort

http://en.wikipedia.org/wiki/Bucket_sort

Teddy

Studies,OI and Love