HAOI2018 纪实

只是记录一下考试过程。

Day 0

下午从学校出发去了河工大,路上晕车心情简单,看了一会 The Expanse 就看不下去了,靠在窗户上小睡了一会,一睁眼发现到了河工大。

然后就是试机,打了个 FFT 拍了拍,键盘挺顺手,没啥问题。试机的时候遇上了 zem,简单聊了一下。然后就回酒店咯,因为不想被别人打扰所以要求安排了单人间,但是特别害怕自己早上没人叫起不来,于是找前台的小姐姐说了一下让六点半的时候叫我一下。

因为预感到晚上可能会心态波动睡不着,所以去旁边小超市买了几罐咖啡和脉动什么的。就回到酒店准备自习。

之前一直留了 USACO OPEN 的题目在 BZOJ 上没写,想赶紧写完然后去颓颓颓。随机点了个题发现是个傻逼树上差分,现在是 2018 年?过了后就又点了个题,本来觉得挺朴素的一个题,想了想还是没啥思路,来回撕烤了半天还是不会..熬到了十点多就点开题解看了,然后又用了差不多一个小时才过了这个题。这个时候已经十一点了,赶紧过了一下之前的笔记就去洗澡睡觉了。

然后好像不出所料啊,躺在床上来回滚睡不着,然后就打开饭否尝试总结一下考试的经验,终于把自己搞的筋疲力尽后就睡着了。

Day 1

8:30 - 13:00 HAOI2018 R1

早上六点多从床上醒来了,还好挺早的。精神不是很亢奋,把昨天超市买的两罐咖啡热了一下灌了下去。然后收拾了一下就去考场了,路上还是很平静的,也没什么紧张的感觉。

到了考场发现周围基本都是认识的人,试了试机子也没啥问题,脑子里回顾了一下考试的规划,顺便把配置文件写了一下,就坐在那里等题了。发题后开始看题,题面写的好像挺正规的,看到了编译选项里的 -O2,一下子开心了起来啊,HAOI 竟然开 O2 了,那简直是我这种 STL 选手的福音啊,这场不好好打对不起出题人啊。

t1 看起来挺好做的,很容易猜到一个结论,然后顺着推下来就是一个 80 分的做法,而且应该不难写,那就应该先把这个 80 分拿到,保险起见先写了个小程序 check 了一下猜的结论,是正确的。然后大概用了不到一个小时的时间通过了所有样例,出题人给了大样例,感觉挺稳的,就去看 t2 了。

t2 也送了不少分啊,用上线性基那个结论,套个 bitset 就有 70 分的样子啊?那写写写啊,没用多长时间也过了所有样例。本地跑了个部分分的极限,发现过不了 2000 的,那就 60 咯,拿掉走人。看了看 t3 发现是个串串题,很容易发现所有最优的一定是从左向右依次选择,想到这个套上个 KMP 解决一下匹配的问题就是 30 分的样子。有个很显眼的限制是保证了询问的量级,那显然是 big and small 分类讨论了呀,大于边界的暴力处理,小于边界的预处理所有答案,那是不是就做完了啊?冷静思考了一下,小于边界的处理大概要用上主席树,大于的情况需要 sam 定位一下位置,那这个代码量就开始起飞了,手上还剩一个半小时,硬肝 AC 就是送死啊。

算了算大概是这场 80 + 60 + 30,那好像还不错啊。t3 big and small 这两种情况都不太好写,剩下的时间应该只够写一个,一个部分大概就是 30 分,也挺赚的啊。写之前先眼查一遍前两题,虽然给了大样例但还是检查一遍比较好。大概眼查了三四遍,都梳理了一下代码逻辑,看起来是没什么问题的。在查 t1 的时候突然想到,好像所有有用的数只有 P 的约数,在 P 的约数的数量级下就可以支持我现在的做法了呀,应该就是标算了,快速写了一下,过了对拍。

这个时候手上就剩一个小时了,t3 的一个部分分怕是凉了,那就裸 KMP 吧,十分钟写完,然后就准备走检查程序了。这个时候 hacf 的那个老师突然过来,在 NOIP 都还不错的几个人耳边说了几句话????到了我的时候问了题目难度和我写的期望分数,然后问我们要不要延长半小时???那当然滋磁啦,于是延长了半小时。

那好啊,延长半小时我是不是可以莽一下 t3 的一个 30 分的暴力啊,开始码码码,很快写完了。但是怎么都和我的 KMP 拍不上,于是修锅就用掉了大部分时间,差不多到最后五分钟的时候才发现是 KMP 写错了,赶紧改了一下成功拍上了,但是这个时候已经不允许我把两份代码合并提交了,没办法只能还是把原来的 KMP 交上去,草草检查了一下出了考场。

出来后问了一下是不是吕老板出的题,得知不是后就和吕老板讨论了一下题目,感觉写的还行。问了问周围的人也差不多证实了,上午分数还是挺稳的,但是大家分差都是 50 分以内,感觉不好翻到 A 队或者队长。

2:30 - 5:00 HAOI2018 R2

点开题目,发现是两个数数题,虽然我还是比较喜欢做数数题的..但是出题人这样搞是不是不太好啊…。t1 看起来是个多项式操作题啊,冷静了一下看了看数据范围是 2e3,那裸 DP 就行啦。t2 好像是个垃圾套路题,给了一点直接容斥的分,写了一下可以过大样例,那公式没写错,转化一下就是个分治 FFT,正准备写的时候冷静了一下看了看式子,好像变一变直接 ntt 就行了啊,快速写了写,一小时内过了拍。

然后开始休闲写 t1,DP 要写一大堆组合数,中间因为实在是太累脑子不清楚没发现有个地方写错了导致一直过不了大样例,下午还是和上午一样延时了半小时,还好最后冷静了一下找出了错误,成功过了大样例。

最后还剩半小时,走了三四次检查的程序,没什么大问题,开始闭上眼睛思考人生,坐到了结束。

result

评测过程还是出了不少问题,有些解决了,有些因为特殊情况没有解决。不影响 AB 队所以不再深究,这口气等 NOI 再舒吧。

官方结果综合 NOIP 分数以及省选成绩以 rk3 进入 A 队。矫情造作的话这里不再多讲,希望没有让那些曾经关心鼓励我的人失望,真诚的祝愿你们 NOI 加油,高考加油。