NOIP 2021 游记&退役记

Cover Image

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

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,而这道题 10710^7 的数据量显然会超出大小限制而爆零,果断否定。考完后发现傻乎乎打表的人竟然还真有,上海有个人打出了 23MB 的表。

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

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

T2 数列 sequence

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

T3 方差 variance

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

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

  1. aia_i 进行连续的两次操作将使其复原。(非常显然)
  2. ai1a_{i-1}aia_iai+1a_{i+1} 放在一条平滑的曲线上,发现操作的直观意义在于使 aia_i 变为其关于 ai1a_{i-1}ai+1a_{i+1} 的均值的对称点。(也比较显然)

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

T4 棋局 chess

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

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

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

结束

我的高中三年 OI 生涯就在这一场失败的比赛中结束了,感觉自己又回到了2019年第一次打 CSP-S(那年 NOIP 取消)的时候,也是拿了几十分滚粗了,还真是首尾呼应啊(笑)。不管怎么样,至少高二的时候拿过 CSP-S 一等,拿过 NOIP 二等奖,也算是满意了。

更何况,自始至终我从来不指望 OI 能给我带来升学上的任何实质性帮助,也并不只是为了那么几个奖打 OI,更是因为热爱它,愿意为它付出时间和精力。三年下来,我收获了独属于我的一段人生经历与体验,也深刻认识到了自己是多么的菜,比自己厉害的人数不胜数,因而时刻心怀谦卑,这就足矣。

借此也特别感谢我校的两位信竞教练,把我们领进了 OI 的世界,高一高二时坚持每周两个晚上的集训无偿给我们上课,真的付出了很多。还要感谢我的班主任,在刚进高中家访的时候得知我有这方面的兴趣,二话不说当场打电话给了我现在的教练,把我拉进了校队。

延续

12月底还有一场上海市高三信息科技竞赛,仅限上海市高三学生参加,教练推荐了我去,到那时就要真正和 OI 说再见了。

不过,在9个月之后,当我考完高考,当我步入大学的校园时,说不定还能再次重逢,也许我会去打蓝桥杯,也许会成为 ACMer,又有谁说得准呢。

OI,后会有期。

NOIP 2021 游记&退役记
本文作者
Hans362
最后更新
2021-11-21
许可协议
转载或引用本文时请遵守许可协议,注明出处、不得用于商业用途!
喜欢这篇文章吗?考虑支持一下作者吧~
爱发电 支付宝

评论

您所在的地区可能无法访问 Disqus 评论系统,请切换网络环境再尝试。