游记

作为一个高三半 AFO 选手，这次 NOIP 意味着彻底的 AFO 和全面的 whk。

赛前

day -3

中午开始停课。

教练安排我和另外一位同学在明后两天组两场模拟赛，我的题倒是提前组好了，不过感觉 A 题放了绿题会难过头，所以临时换了一题黄题。（然而 NOIP A 题蓝，哈哈）

下午帮同学证明代码正确性，然后在讨论区看到野题拉同学想了两小时，结果那个帖子被删掉了。后面在讨论区看到了你画我猜，第一次见到信息竞赛词库，挺好奇的，进去看了一下，结果一不小心玩了快两个小时，哈哈，太好玩了。

顺便也靠这个重新回忆起了许多算法，原来我三年来已经学了或者了解了这么多，十分感慨。

晚上在机房组了一场模板手速赛，基本十分顺利的写出来了。除了树状数组不小心把 $m$ 打成 $n$ 以及第一次写 $O(n)$ 建树，还有字典树的映射写挂，其他模板都一次过了。不过手速不够所以一些图论高级算法的模板没打到。

day -2

上午验了模拟赛的 C，中午开始考。然后经典赛时开始造大样例，以及赛时才验 D（本来几乎一次过的，结果因为不小心把 min 写成 max 调了好久）。

晚上给机房讲题，讲到喉咙冒烟。组比赛真的比打比赛累多了。

day -1

上午有点摸鱼，下午打同学组的模拟赛。A 因为差点没开 long long 差点见祖宗，B 是我推荐给他的题所以原了，C 是缩点板子所以二次原，D 是万恶的小木棍。

通过洛谷帖子保存站，发现前天那个帖子删之前有人回答了，并且做法大致和我想得一样。然后找到了那个你画我猜的帖子，但房间已经没了所以自己创建了一个。

和机房同学试了几个词库之后回到了 OI 词库，然后人一下子变多了起来，好玩。后面有点累了，想着等再轮到我画一次就退。结果中间有个人画了矩阵快速幂，所有人都答出来了只剩我，然后我猜了各种“矩阵优化dp”“矩阵加速递推”直到有人提示我“矩阵什么也没优化”才压着时间线答出了正确答案，他们甚至发起投票踢我，然而我是房主，乐。（伏笔）

晚上对着题解把小木棍调出来了，并且成功快速理解了那两个优化。后续接着打图论模板，除了欧拉路径有点模糊以外都很顺利的打出来了。

放学前半小时在机房里扬言要挑战 15min 敲树剖板子，结果因为太久没打所以手疏导致实际用了一倍的时常。打完之后成功过了样例，提交发现最后一个点没过。可恶，差点一次性过掉了树剖。

后面看讨论区才知道最后一个点是 hack 没对输入取模的，长记性了。

day 0

顺利起床，吃完早餐后坐校车前往考点。

在考场门外面基了某位神犇数秒，大致流程是：突然被手机贴脸->递东西->消失。

进考场，发现挡板不太行，能够清楚看到斜对角两位选手的屏幕，但看得出来主办方已经尽力遮挡了。

我们学校和另一强校交替着坐，感觉压力很大。而且复赛时候的咬笔哥这次来到了我的左侧，并且我依旧不知道他是否有第二支笔。

签字，话说今年居然不用填“我选择在 Windows 系统”，以及经典提前三分钟发密码提前三分钟收卷，到底有什么必要嘞，还导致我们开始前三分钟不能建文件夹。

看到这解压密码，感觉有点东西。莫名有点应景（指 AFO 前最后一战）

赛时

开 A，感觉有点难办。来来回回只能往贪心上想，去年的这个时候已经写完 A 了。

记得最开始写了一版贪心，但是后面发现假了，但是改一改就真了。一个半小时才敲完了，是现在主流的统计区间个数然后双指针的做法，我以为很对，结果大样例第 7 个和最后一个过不去，莫名其妙多了一点。

对着代码找不出错，想过写对拍但发现我不会暴力做法，于是只好硬着头皮去看大样例，但好在 7 是特殊性质，比较简单。

分析了 7 后手动模拟发现手算出来的就是那个错误的答案，很绝望，这可能说明我贪心假了，此时已经两个小时了，去年这时候我马上就要调出来 B 了。

想着至少能过好多个点，先去看 B 了。读完 B 感觉，完了，B 也不会，甚至不知道读没读懂。一开始以为是推出式子快速幂算就好，仔细读题之后分析了一下发现不是简单的相乘，要分情况递推。

因为感觉最后肯定是想办法压缩不确定的一段的方案计算，于是就先对 $n$ 写了个 dp。

可能是由于昨天你画我猜里矩阵快速幂给我印象很深刻，写完之后定睛一看，发现这状态转移式子长得很递推啊我啪的一下就改成了矩阵。卧槽那这不快速幂秒了吗，喜滋滋写完之后稍微一挑就过掉了大样例，芜湖。

还剩一个半小时，打算把后面两题暴力和特殊性质拼了再回去调 A。

C 题想了一会写出来一个式子，感觉是换根 dp 但我不太会，所以想着写个树形 dp 的暴力，结果写了四十分钟发现假了，只写了个链，然后菊花图的式子也假了，绷。

D 题很优雅，但是不会，看特殊性质火速打了链，但是是 $O(qn^2)$ 的暴力取 min 和 max，哈哈，炸裂。而且大样例不知道为什么会卡死，运行不了。

最后二十分钟调 A，然后这时候我终于想出来了错在没有考虑相交区间长度的限制，但是我以为这里要做决策来决定怎么分配 0 和 1 的比例，所以以为贪心假了。但是十来分钟也改不了什么了，所以写了个数学里的分层抽样一样按比例的神秘决策，结果过掉了大样例。

最后十分钟检查代码的，找到了 D 应该是导致卡死的原因，改了编译了但没测样例。最后三分钟想把 A 的 memset 改成 for 来初始化，最后勉强卡着时间改完了，能过编但是也没测。

出考场之后才回想起来 $T\le 10$，memset 根本不慢，后悔改了。然后这时候悟到了提前收卷的意义，因为这样哪怕结束后才保存的话也不会判时间无效。

赛后

出考场后

考完后听到很多人说很高分，压力。在考场外地板上发现了野生零食，乐。车上吃了好多零食，得知机房其他人考的也很炸裂，悲。

晚上过掉了 B 题的自测，舒服了。

次日

后面证出来了 A 的那个决策不重要，不影响答案，怎么选都行，于是乎就连最神秘的我的按比例选也能过掉，哈哈。

中午过掉了 A 的自测，舒服了。C 的链原来只有 4 分，好吧，合理。D 的暴力仔细一想好像其实估计没有分，悲。

退役很久之后

最终成绩 $100+100+4+0=204\text{pts}$。

实际上在上面的内容是去年十二月初写在洛谷的，但时隔很久（次年年初）才发布。不过并不是因为不接受成绩或者 AFO 伤感之类的，只是单纯没有机会转移到博客上来。

“没有机会”指的不是没有时间，尽管我确实更多忙于文化课。也不是懒，好吧感觉确实更贴近懒。

学习 OI 三年，不长不短，按理说 AFO 之后应该需要写一篇 OI 生涯总结，也许不久就会开始写吧，虽然已经 AFO 有点久了。甚至现在的时间点，比起 AFO，可能离我高考后回归 OI 的日子还要更近。

虽然 AFO 且时隔久远，还是多多少少复盘一下。首先这次最大的失利就是我在第一题上花的时间不太合理，并且我认为其中一个细节其实是很难想清楚的，导致我考场上不能肯定我的贪心是错的。我总觉得不太签到，但毕竟竞赛不是小孩玩的游戏，有选拔的目的在的。然后第二题能够写出来，真的很有运气的因素（详见 day -1 的伏笔），否则我真的没有信心能够在考场上想出正确的做法。第三第四题一如既往地不善于写部分分导致错失一等，不过大学比赛就不需要写部分分了，哈哈。

虽然认为没有以一等作收尾有些遗憾，但是也完全能接受。三年 OI 最终至少给我带来了相当于保送中大计算机系的机会，所以也算是减少了一些心理上的压力。尽管如此，我也还想尝试一下靠文化课能否达到更高的高度，所以仍然在加油的路上。

尚有星光伴前路，心向远方更前行，以此作结。

附录

参考文献

版权信息

本文原载于 reincarnatey.net，遵循 CC BY-NC-SA 4.0 协议，复制请保留原文出处。