我的NOIP2016

初赛

考前准备

考初赛之前,我把近十年的初赛题都做了一遍,发现了几个比较有用的方法。

组合数学

从排成一排的m个物品里面选择n个出来,要求不能相邻,有多少种选法?

这个可以用DP来做,但是有更简单的办法。考虑全部选出来之后,抽出来,再插回去,插法即为答案。我们在插入的时候选择的空隙必然是不相邻的,所以满足题意。

还有放小球到盒子里的问题,分八种情况,分别是小球一样、不一样,盒子一样、不一样,允许、不允许为空,二的三次方就为八种情况。对这八种情况的讨论,网上有解析,我就不赘述了。

算法复杂度

对于一个数组,最少需要比较多少次可以将它比较好次序?

可以转化一下问题,最少比较多少次可以将它的排列确定?

这个长度为n的数组总共有[latex]n![/latex]种排列,每比较一次可以减去一半的可能性,所以最少需要[latex]\log n![/latex]次。

而这个也是为什么基于选择的排序的理论时间复杂度下限为[latex]O(n\log n)[/latex]。

[latex]\frac n 2 \log{\frac n 2}=\log (\frac n 2)^{\frac n 2}\leq\log n!\leq \log n^n = n\log n[/latex]

考试当天

我早上再刷了一套,感觉不错。

下午,我和弟弟坐地铁前往深圳外国语学校初中部,再一次踏进了校园。弟弟在二楼考,我在三楼。我们学校大部分人都来了,缺一个发烧的女生。拜访了深中高中部众神,但是没在考试前看到何恩州。

开始考试之后,前面的题顺利水过。单选题的按规则敲键盘差点看错题,不是问按到第几个键的输出,而是第几个输出。多选题有一道问GPRS是不是无线网相关的,我不知道,于是没选,错了一题。填空题的黑白格染色要求黑格不相邻,但是涂的黑格数量不限。我用了我刚学的组合数学方法,险些漏了全部为白格的情况。

读程序写结果的意图都挺明显的,一个将数组倒过来,一个我猜是看全称是否满足缩写,一个是求最长回文子序列,还有一个求树的重心。

程序填空的链表操作比较多,模仿即可。第二题竟然裸考SPFA,还有验证路径是否在SPFA上,相比起前面的题目来说,还是有诚意多了。

考完试出来坐妈妈的车回去,然后就发现校卡和深圳通不见了。本来是为了方便把它们放一起,结果要丢就一起丢了……

考完试

成绩很快就出了,我96.5,我弟97.5,分别是深圳提高组第一和普及组第一。两兄弟同时在同一个比赛中拿第一的机会真的不可多得啊。

考完对答案发现quicksort在i=j的时候竟然要继续双指针的循环,不能理解,但是估计就是这里扣了另外两分。

考完初赛,感觉放松了很多。但是初赛考得多好没有任何用处,还是要看复赛。

复赛

宋老师多次催促我做完前五年的题。但是哪有这么容易做完呢?做一题就要调试半天的本蒟蒻,勉强刷完了去年的题。考前一个星期连做了4套学军的模拟题+一套信心题(最后学军的评测机爆炸了,没成绩),平均分170+,参考往年试题的难度的话,感觉胜券在握。

谁知道,今年不按常规套路出题?

星期五

和李泽慢一起吃完晚饭之后就出发了。火车上玩了好一会魔方,在和谐号火车灯光的颜色下没办法好好观察,avg 22s+。晚上酒店的问题搞得有点晚,不过休息得还算好。第二天早上4点就醒了,然后又睡了一会。

结尾

后面我就没有一直写下去了,所以也不太记得当时的情况。

avatar
Kerry Su