NOIP 2018 蒟蒻爆炸记

Posted by wyj on November 10, 2018

Day0

今天到达了舒适的宾馆,居然有厨房。享受了一个下午。写了道墨墨的等式(居然部分押中了T2!)。晚上一直在看错误总结,祈祷不要爆炸。

Day1

上午觉得非常困,昨天可能没睡好。考场使用NOI Linux。Ubuntu各个版本的桌面快捷键太不统一了,我又找了好久(10.04:Win+D;14.04:Ctrl+Win+D;16.04:Ctrl+Alt+D;18.04:都可以)

发题了,我还在调Gedit环境。一看T1,shabi题,随便切掉。一开始还想写笛卡尔树呢,后来觉得恩欧爱皮应该稳一点,就写了个ST表。(后来才知道标算如此简单!)

正当自我感觉良好,同时开了后面两题,看了好久,一点都不会做。从九点看到十点,非常慌。主要是T2,一开始想到了那个墨墨的等式,却死活不会往上套,后来又觉得像bitset,却发现可以使用任意多次。这下不是烂了么,只好写了个80暴力。

T3更加蒙蔽,连暴力都一点也不会写。据说不会写暴力的题都是网络流,又YY了很久,不会流。菊花也不会做。实在没办法,写了个40暴力。

这下不是完了么,恐怕今年分数还不如去年呢,肯定要退役了。这时,T2测了下极限数据(一堆1,最后一个25000),却发现秒出!!!仔细分析了一下,bitset暴力只有当前数不能被表示出来的时候才会拓展状态,这个“不能表示出来”显然是个log的。那就很对了。可惜常数不给力,跑了1.8秒(之前秒出是默认开O2的)。这下还是只有80,于是试着手写了个bitset,还TM要1.2秒。反正一样是T,自带的还不容易FST,最后我就没改。这时刚好还有10分钟。

当时觉得这题真TM变态,一点也不NOIP。之前我们校内训练做的假NOIP可以两天加起来3.5h时间AK。出考场发现大众分300。生无可恋。上知乎发现是三道原题、\(\large\text{三道贪心}\)。没办法,贪心还是太弱了。

下午去了牛首山。去程五公里,回程因为单行道所以25公里。佛顶宫真的超大。玩的很累。

Day2

再不翻盘就要凉了。但事实证明翻车了。

继续使用Linux,环境全部重调了一遍。今天系统时间不对,更改时间还TM要root权限。

拿到题,先浏览了一遍,怎么没有像去年那样的一眼题?这时候已经慌了。过了一段时间看到了T1的m<=n。又过了好久注意到每个点编号都是不同的。原来是一道隐藏的很深的SB题,随便理论\(O(n^2)\)切掉。

然后开T2,因为T3非常明显的不可做。手玩了很久,大佬们随便看出来的每条副对角线递增的规律,我就没看出来,却把它总结成了很长很长的一段话,长到连n=3的时候都不想写了(但是这个规律好像是\(O(n+m)\)的,数据范围有点奇怪)。于是弃疗随便码了一个50。和暴力对拍,暴力太难写了,调了半个小时却连\(n=m=4\)都跑不出来。

这时还有一个小时,觉得好像要烂了,T3必须拿到70左右才能翻盘。我当时看错了题,以为是需要选中一些点覆盖每一个点而不是每一条边。所以这个DP好难写啊(后悔前几天弃疗了潜入行动),我又写了半个多小时。记得当时开题的时候策略是这样的:先写一个\(O(n^2)\)的DP,然后在链上用线段树优化,最后树剖维护(我当时还不知道这个叫做动态DP)。毛想想,记录线段树上每个区间的左右端点是否放、是否被覆盖是可以维护的。再毛想想,好像是能够树剖的,每条重链是可以单独DP的。

可惜时间已经不够了(还剩20min),勉强可以接受现在的成果。一测大样例,却发现WA飞了,赶紧调试。不对啊,手玩了几次,怎么结果都和我的程序输出的一样呢?肯定是我题意看错了。当我又读了一遍

\(\huge\text{由道路直接连接的两座城市中}\)

\(\huge\text{至少要有一座城市驻扎军队}\)

这句话的时候,我内心是崩溃的。这回翻车了,脑子里一片空白。然后发生了什么就不知道了。

考完出来,发现lzq也(自称)炸了,还和我一模一样。这时候心理稍微平衡了一点。(本来以为大家T2全都会状压,T3全都会树剖,大众分250+)

总结:看我不会贪心就出贪心;看我不会树DP就出树DP;这回翻车可是真的严重了。