NOIP 2021 游记&退役记

2021-11-21 水

文章目录

Day 0
Day 1
结束
延续

本文最后更新于天前，文中部分描述可能已经过时。

11月20日下午一点，考场内清脆的结束铃响起，我按下了屏幕上的提交按钮，短暂的三年 OI 生涯终于随 NOIP 2021 的落幕画上了句号，我的心里感慨万千。这应该是这个博客的最后一篇 NOI 系列活动游记了，因为，无论这次考得怎样，我都真的彻底退役了，高三了，老了。

Day 0

没想到 NOIP 竟然不在自己学校考，大概是因为比起 CSP-S2 人要少很多，我被分配到了比较远的华师大二附中某分校，路上要花不少时间。

考试前一天周五晚上六点放学（毕竟高三了），回到家都已经七点了，写了会儿作业就开始看 OI Wiki，复习了一些模版和 STL，十点多就睡觉了。

Day 1

一大早六点起床，七点四十五到达考点。门口工作人员正在悬挂 NOIP（上海赛区）的横幅，排了会儿队测完体温就进去了。

进了机房找到座位开始试机。不愧是四大名校之一，华二的机房硬件设施比我校的高到不知道哪里去了。电脑装的是 Windows 10 精简版本，内存配了8个G，VirtualBox 装了 NOI Linux 2.0，总算不会出现 CSP-S2 时在我校虚拟机都开不起来的情况了。唯一一点不好的就是这精简系统把 Windows 自带的计算器给阉割了，要算个东西还得写代码。

到时间了下发密码，建文件夹，解压试题。看了眼编译参数，是开 O2 优化的，说明以后 O2 优化将成为常态。扫了一眼四道题，果然又没看到什么签到题，T1相对而言感觉是最好下手的，决定从 T1 开始。

T1 报数 number

读完题想到了三种思路。第一种就是喜闻乐见的打表。幸亏我在考前仔细阅读了相关的技术条例，在 CCF 一份2011年的文件中明确规定了代码的长度不得超过 100KB，而这道题 $10^7$ 的数据量显然会超出大小限制而爆零，果断否定。考完后发现傻乎乎打表的人竟然还真有，上海有个人打出了 23MB 的表。

第二种想法是预处理 $10^7$ 以内所有含 $7$ 的数字，打上不可报标记，同时对于每个含 $7$ 的数字其整数倍对应的数字也打上不可报标记，这些都在预处理过程中完成，然后再针对每个询问进行查询。这种方法实际上就是所谓的「埃拉托斯特尼筛法」，貌似是本题的正解。我竟然在没有学过线性筛法的情况下自己想出了这种做法。悲催的是我错误地估计了时间复杂度，觉得预处理时间复杂度很高，查询又不需要使用到预处理的所有数据，会进行很多没有必要的预处理，从而超时。于是我在未加尝试的情况下竟然毅然决然地否定掉了正解。我根本没有意识到这样的查询实际上是离线查询，查询时间复杂度是 $O(1)$ ，预处理时间复杂度也不过 $O(nloglogn)$ ，是完全可行的。这也为我在这场比赛的失败埋下了伏笔。

然后我就瞎搞出了第三种做法，预处理只处理 $10^7$ 以内所有含 $7$ 的数字，打上不可报标记。然后针对每个查询数字 $i$ 再去校验 $i+1$ 及以后的数是否可报。我洋洋得意，自以为这样的做法似乎避免了不必要的预处理，但赛后发现实际上查询时间复杂度高得离谱。一测发现前三个样例 AC，样例4 TLE。于是我又加了个记忆化数组，保存校验结果减少对同一个数的重复校验，然而样例4依旧 TLE。一看时间已经过去一个多小时了，想着算了先往后做吧。

T2 数列 sequence

一看真就没啥思路，感觉和组合数学有关，估计是什么数学题。思索了很久实在没想法就 DFS 暴力开搞，逐个枚举数列 $\{a_n\}$ 中每一项的值，再求相应的 $S$ ，用 __builtin_popcount() 统计二进制中 $1$ 的个数（今年起开放了下划线开头的函数），如果满足 $\leq k$ 就计算权值。同时要时刻注意取模避免爆 long long。测了一下样例1 AC，样例2 WA，而且我的答案竟然是负数，怀疑哪里溢出了检查了好几遍都没发现问题，该取模的地方也都取了，我只好决定放在一边接着往下做。

T3 方差 variance

一看这题，我靠，怎么又是数学题，搁这上机数学竞赛呢？莫不是全国高联 CCF 限定版？

众所周知方差是反映一组数据波动程度的统计量，方差最小那不就是要数据波动尽可能小嘛，那这道题就是要通过若干次这种操作减少数据的波动程度。我打算先研究一下题干中给出的这种操作的一些性质，花了点时间发现了下面两条：

对 $a_i$ 进行连续的两次操作将使其复原。（非常显然）
将 $a_{i-1}$ ， $a_i$ ， $a_{i+1}$ 放在一条平滑的曲线上，发现操作的直观意义在于使 $a_i$ 变为其关于 $a_{i-1}$ 和 $a_{i+1}$ 的均值的对称点。（也比较显然）

然后就没了，~~好不容易~~证出来的结论似乎对解题依然没什么帮助。考虑了一下贪心、差分，感觉都不太对，也没敢贸然下手。最后只好忍痛放弃，拿了 $n \leq 4$ 的12分跑路。

T4 棋局 chess

看完题目就没有什么做的欲望了，再加上给了 1024MB 内存，4s 时限，估计不是什么好做的题。写 DFS 当成大模拟做我觉得划不来，吭哧吭哧写完调半天可能也没几分，果断放弃。

回过头又在 T1、T2、T3 间反复横跳，一道都没能突破，直到最后都没意识到自己把 T1 正解给否决了。走出考场的那一刻我知道自己已经凉了，突然很庆幸去年拿了二等奖，今年恐怕连奖都没了，在高一高二同学面前我这个高三的半退役选手真的是身败名裂。同时也深刻认识到了数学是自己的最大软肋，今年三道数学题一搞就拿不到什么分了。

回到家测了下民间数据，洛谷 62pts，小图灵 82pts，InfOJ 82pts，市排名 200+/371，凉透了。写这篇游记来记录我在考场上的真实反应，也是希望后人能吸取我的教训，引以为戒。