NOI 2020 退役记

## NOI 2020 退役记 ### 引子 我走进允公楼（说实话，第一眼看成了充公楼）三楼的自习室。 打开网易云，播放 [Euphoria](https://music.163.com/#/song?id=551339691)。看着歌词跟着唱起来。 这首歌陪伴了我一半的 OI 生涯。它是 Jin 作曲、IA 演唱的，它还是 IOI 2018 主题曲，种种因素叠加起来，这成为了我 2019 年播放次数最多的一首歌，也是我 NOIP 2018、WC 2019、NOI 2019 省选、GXCPC（广西大学生程序设计竞赛）2019、THUSC 2019、NOI 2019、CSP-S 2019、THUWC 2020、NOI 2020 省选、WC 2020、NOI 2020，这些比赛前必听的曲目。 > 「同じ世界に、立っていたんだ」と > “在同一个世界 站起来了” > 「同じ未来に、立っているんだ」と > “也会站在同一个未来” 五分钟的音乐结束，我又打开了 01 颂。这次可以不看歌词，直接和着熟悉的旋律唱起来。 > 我才发现，我才知道 > 原来机房是我家 > 我只相信，我只明白 > OI 天不塌 这首曲子，更是有特别的意义。cultry 学长，在 NOIP 2018 前，根据我们校歌的旋律主题写作了这首歌，作为我们 01 社的社歌。01 者，初音ミク之肩标也（cv 01），因此我们 01 社也被称作术（术力口，ボカロ，Vocaloid）社。而这社歌，自然也是初音ミク演唱的。从知道有这一首社歌以来，我就十分喜爱它。在上面的每次大赛前，播完 Euphoria 之后我也总会播放这首曲子。 也许 cultry 写作这首曲子的时候并没有想到，就在不久后，OI 会遭遇如此多的磨难；当时的我，自然也不太能理解什么是“OI 天不塌”。 WC 2019 上，兄弟学校南宁二中的 OIer 演唱了 OI 版的千里邀月，当时我就立志，我们三中要在 WC 2020 上台演唱。2020 年寒假前，强基计划的消息传来，我们似乎瞬间发觉，OI 真的处在巨大的危机之上。那时想，在 WC 上演唱这首歌，应该会引起不少人的共鸣吧。 然而春节前夕又是变故，之后的事相信大家也比较熟悉，我先是盼 NOI 能有文艺汇演，后来听说 WC 要线上办又幻想线上文艺汇演，再之后又孤注一掷盼望 NOI，再又看到 NOI 2020 简洁的日程表，终于是不抱任何希望了。WC 2019 的时候，大家都在讨论某个事件会不会导致第二年 WC 没有文艺汇演，殊不知，在命运的潮流中，那终究只是一小圈波浪，WC 2020 的文艺汇演，是被更大的命运浪潮，打回去了。 然而我终究是比较幸运，虽说没有文艺汇演，没有这样一个把热爱的歌唱出来，把心中的情感与众 OIer 分享的机会，但我还是得到了参加 NOI 2020 这样一个难得的、好好地结束自己 OI 生涯的机会。 没有失去过，就不会知道得到这样的机会有多不容易。在去长沙的列车上，读到 StudyingFather 祝大家 `rp++` 的[帖子](https://www.luogu.com.cn/discuss/show/249119)，乃至后来读到描述到更多细节的[博客](https://studyingfather.blog.luogu.org/skyline)，我都深深体会到这句我们教练当时也引用了的话—— > 一个人的命运啊，当然要靠自我奋斗，但是也要考虑到历史的行程。 当时感触颇深的我，在第八页这样的后排写下了[一点感想](https://www.luogu.com.cn/discuss/show/249119?page=8)，同时也是给退役前的自己说些话吧。里面的“一日 OIer，一生 OIer”，我想，我会努力做到的。 收拾收拾沉重的心情，我又点击了 LCA 的“线上文艺汇演”作品，海伊演唱的 [OI Diary-Madia Lemon](https://www.bilibili.com/video/BV1Uh411d7Ab)。在备战 NOI 2020 时我才偶闻 Synthesizer V 和海伊的大名，当时便惊叹于其高还原度。而这次看到这典雅的填词，歌声中少年的意气，又不禁一阵触动。 接下来，便让我随着这些曲子，重温我 NOI 2020 的旅程吧。 ### Day 0 启程 在疫情期间，全副武装地出门，坐上开往长沙的高铁列车。 痛苦地调着 UNR 的“己酸集合”一题——事实上到现在还没调出来，也许永远不会调出来了罢——累了就玩 osu!，度过了有些漫长的乘车时间。 来到长沙，在炎炎夏日之下走向大巴车。经过一段不长的乘车旅程，我们到达了长沙一中雨花新华都学校。 “惯例”地交材料，领衣服和书包，又在签名墙上“小气”地签了名，并在墙上写上了新梗“幽兰捧杯”（对比之下，我的字真的好丑）。 来到宿舍，队友敏锐地观察到了宿舍门前的“女生宿舍楼”牌子，于是乎 Sweetlemon 人生第一次踏入了女生宿舍（大雾）。后来又得知女生住的地方原来是男生宿舍，看来真是奇怪的主办方呢（大雾）。 宿舍有四张床，上下铺，由于男生是按学校安排宿舍，因此我们三位——Alear, JasonL, Sweetlemon，“占领”了一个宿舍；而 hkr04 和广东、黑龙江的选手同宿舍，我想她得到了与强省选手交流的机会吧，她说住在强省选手旁边也不太容易（笑）。 看到上下铺的宿舍（而且床好像还比三中的窄），我不禁感叹，三中的住宿条件真的是顶级的，七人间，上床下桌，能比一比的高中大概不多吧（逃 宿舍很干净整洁，配的生活用品也很“财大气粗”——床上有两条新的毛巾，阳台有“高端”的洗发水，还有一大瓶沐浴露、一大瓶洗衣液、一瓶洗手液，还有看上去很漂亮的口杯、三只大牙刷（刷着挺舒服的）、三大支牙膏，后来发现还有全新的撑衣杆（挺细心的），然后枕头也很软很舒服。在感叹主办方用心的同时，我也不免感到有些浪费（ 晚餐则更是丰盛，相比 NOI 2019 的四个菜，今年更是采用了自助餐的形式，实在是非常令人享受，饭、菜、汤、饮料、水果，都一应俱全，实在是要给主办方点赞。后来某一次，我吃到了一个扇贝，非常美味，然而后来就再也没有吃到了（笑）。食堂外有乙醇免洗消毒液洗手处，我们每次饭前饭后都洗一洗，其实挺舒服的（笑）。 睡前仍然是试着调调己酸集合，又玩玩 osu!，下载了 Katawa Shoujo。Katawa Shoujo 中少年少女的乐观情绪在一定程度上也启示了我，很多时候，能够“正常”地对待他们，也是非常好的尊重。 ### Day 1 晨曦 起得不算非常早，吃完早餐，先是开幕式。开幕式上我当场听录了 dzd 的致辞，原稿在[这里](https://www.luogu.com.cn/blog/Sweetlemon/noi-2020-ceremony)。 稍作休息，下午是试机。就在 NOI 前几天，我的 NOI 笔试百题大过关登上了洛谷日报，再加上两年的研究，我也没有太大压力地过了笔试。我又 看到试机题目，基本都是我去年 NOI 不会写的。我又研究起如何评测交互题来，后来发现，最终的解决方案貌似是在 `explore.h` 这个头文件中写 `main` 函数并输出 token 一类，然后按传统题的方法进行评测——真是巧妙啊。 后来又利用剩下的一小段时间，测试了赛场机器的效率，1s 2e9 没有问题，还是非常强大的。 另外提醒一个小问题，去年和今年我都遇到这样的问题，NOI Linux 的机子插上 U 盘小概率会死机，而今年我试过 SysRq 都无法重启，似乎只能用电源键。 下午试机结束后我们去运动场跑了两圈，我还试着做了十几个引体向上，感觉体能掉得挺厉害（bushi 教练给我们买了茶颜悦色的少年时，茶味很浓，和我喝过的“奶茶”有很大区别。 晚上也没敢太浪，写了后缀数组和一道离线的模板，又写了 NOI 2018 的归程，还算比较顺利地通过了。 ### Day 2 早晨与阴云 机试第一天，进场前教练 HDM 反复强调了“FFA”（Force First Algorithm，暴力优先）战略。 拿到题目，大概把每道题的题意看了，又敲了 `quick_template.cpp`（就是些快读），就一点一点地写暴力。 T1 首先写了暴力 dp，T2 写了指数级枚举，T3 写 $\mathrm{O}(n^3)$ 暴力（讲题时才发现 $\mathrm{O}(n^2\log n)$ 很好写）。 接着又回去看 T1，看到了“环”的部分分（所有点在一个有向环上），我把它写了，于是就往“环”上考虑了，想的都是什么“找包括 1 号点的环”之类的奇怪思路，当然并不会做。 紧盯 $k=0$ 的部分分，想着这个可能会有某种“规律性”，把 dp 数组打出来，并没有发现什么规律。考虑了好久，没考虑出什么来；旁边的高频率敲键盘（真的很高频）在一定程度上也给了我一点心理压力…… 转变战略，去做 T2 和 T3。T2 一开始并没有太多优化思路，而是在 T3 中发现了一个类似“一维问题”的部分分，研究后发现可以用莫队解决。敲完莫队，回到 T2，根据前段时间学到的“用 dp 优化暴力的过程”的思路，写出了一个 $\mathrm{O}(n^2)$ 的树形 dp——说实话，我对我的状态设计和转移方程挺不自信的，而且也是比赛末期，心态也有些波动；但后来它过了大样例，也就任它吧。 最后进行了一些检查——第一次在比赛中使用测样例脚本。 出来听到“矩阵”，似乎瞬间领悟到了 T1 的做法——所谓的“规律性”，自然指的是转移的模式固定，也就可以用矩阵描述嘛。这还是反映我对矩阵的理解还不够深层，也算是学到了不少吧。 下午复评，成绩一分不差，$50+48+28=126$，这三个分数我都写在上交源程序的第一行注释中了。 程序没写挂，本来心情还不错，然而晚上讲题的时候，感觉人均 AC T1，大众分 $160+$，心情一下子肉眼可见地变差了；甚至还觉得，我是不是今年要打铁了。回到宿舍，觉得自己甚至不应该来听讲题，好好在宿舍呆着多好。 又想想，心理素质还是很重要的，因此想到自己去年 Day 1 似乎也是差不多的分数，似乎有一点安慰；然而心情终究不是太好。 Day 1，Alear 和 JasonL 也都没有发挥好，JasonL 甚至已经知道了 T1 的正解，还知道它和某道省选题的 idea 类似，但写炸了掉了好多分；hkr04 则稳扎稳打，坚决实施 FFA 战略。唉，现在想来有点惭愧，没能帮助大家稳定情绪。有些自闭的我们三位，回到宿舍下载了某个 D 开头的游戏（English Version，以下略称为 D，**请不要无视其警告**），在初期体会到了 koi（恋）的甜蜜（大雾）。前一天中午玩 Katawa Shoujo 时已经有了玩英文 Galgame 的体验，这次我们几个人一起同步阅读，互相帮助理解~~题意~~文意，似乎顺利了一些。选词写诗的时候，看到了 tears 和 destiny 两个词（笑）。 总之不管怎样，D（的初期）还是让我的心情好了一些，至少能够暂时放下一些东西吧。 ### Day 3 阳光重现的下午 Day 2 起得也不是很早，正常时间进了赛场。 仍是照例的读题，T1 可能是数论，而 T2 的题面一下就吸引了我。这样对话式的题面，让我想起了数学女孩和花与向量（我的小说作品），想起了我出的几道对话式题面的题目（“小说题”），还说出了我们 OIer 的许多心里话，读完题目后我也确实有了解题的欲望。相比之下，T3 就显得普通，看上去是一道不可做的图论题。 开始写暴力。T1 看到材料不超过 4 种的部分，想到一个全暴力的 dp，然而空间有点大，考虑用 bitset，写了几十行之后觉得实在太难写了，就弃了。 为了让暴力好写点，我不停地想性质。一开始想到了大小搭配，就是最小的和最大的配合做菜，结果发现过不了样例 1 的最后一个点。后来又发现，过不了常常是因为最后剩下三个加起来等于 $k$ 的数；于是想到，至多两个加起来等于 $k$ 的数是可以接受的；后来又证明，至多三个加起来等于 $2k$ 的数也是可以接受的；如上推广，得到，至多 $(m+1)$ 个加起来等于 $mk$ 的数是可以接受的。而且，这些全都可以用大小搭配的算法构造可行解。 咦，$m\ge n-2$？那是不是说 $m=n-2$ 无解，其他都有简单的解呢？但是样例 1 里面 $m=n-2$ 就有有解的例子啊。 仔细观察，哦，样例 1 里面把 $m=n-2$ 分割成了两个 $m=n-1$ 的部分分别求解。后来我又证明，如果一个 $m\le n-2$ 的集合中不存在和为 $k$ 的倍数的子集，那么它一定无解；于是我大胆推论，一定要划分才能有解。 那划分是不是一定会划出 $m=n-1$ 的呢？我感性理解一下，如果划成的不是 $m=n-1$，那么会有 $m$ 更小的，用数学归纳法大概可以证明出，最终一定会划分出一个 $m=n-1$ 的部分。 最后就是判断能否划分成 $m=n-1$ 的部分了。这个 dp 相对简单，一下子给了我信心，我经过简单优化，做到了 $\mathrm{O}\left(\frac{n^2k}{w}\right)$ 的复杂度。 把程序写完，为了过样例，我还用 Python 手写了 checker，全部通过了。 此时已经过去 3.5 h 了，想着别人一定早已一个小时切完，心里还有些压力；但似乎能 A 掉一题的感受也让我安心不少。 接下来 T2 和 T3 轮流看，目标只是写暴力。T2 简单思考后手推了高度不大于 $2$ 的情况，有 12 分；T3 发现没有任何思路，就输出了 $-1$，预计有 5 分。 又想着推 T2，弄出了 $2^{2^{h}}$ 的枚举，似乎能多过一个点，但对我而言实在是太难写，此时只有不到半小时了，考虑 T1 写挂的风险，最终还是选择回去检查 T1。 写了 T1 的 generator，有解的情况输出的解都没有问题。但在比赛还有 5 分钟时我发现，如果全部数据都是 $m=n-2$，程序就需要跑 $3$ 秒左右。到了这个时候，降低复杂度已是不可能，只能想办法卡常。突然发现自己 bitset 为了防止“内卷”开到了两倍，考虑到 bitset 左移出界应该会直接丢弃而非循环左移，所以把 bitset 改小，不到 $2\mathrm{s}$ 就跑完了。最后略有些刺激地把代码从编码区复制到测试区，测试通过后又复制主文件夹下的提交区。这应该是我 OI 生涯中正式比赛上最刺激的比赛体验了吧（非正式比赛上，更刺激的是 2020 年洛谷 8 月月赛 I）。 出场后发现并不是大家都秒切 T1，相反，今天的题让很多人都没有发挥好。于是去吃午餐，午餐后本来计划接着玩 D，但我实在太困了，就直接睡了。 睡到下午 3 点半，听到 JasonL “出门”的声音，我看一眼时间惊起，他却说他其实是刚刚回来，又说可以不必着急，门都没开；我遂重新躺下。 看群里大家似乎在集体面基，我似乎也不应该错过这个好机会，于是和 Alear 一起下去。看到千奇百怪的 WiFi 热点名，我突然想到，如果不能直接面基，也许可以开个热点证明来过吧，于是打开手机热点（笑）。 等待中，我们又打开 D。我评价起四人（下面只用 S, N, M, Y 代表，抱歉略去全名）的英语字体，认为 Y 的花体在高考中一定会低分，而 N 的字体是比较标准的高考高分字体，我的英语字体可能比较像 S 吧。 评价着评价着，考场的门开了，打开机器发现分数很符合预期，$100+12+5=117$。简单拷了数据，找其他三位交流。Alear 的 T2 “乱搞”算法拿了 40 分，算法逻辑也很简单，我就突然发现自己一味追求正确性，忘了“乱搞”这一种思路。hrk04 很乐观地对成绩表示了满足。JasonL 没有发挥好，我们安慰他，明年一定还有机会（这是事实）。 吃晚饭时我们又交流了一下，突然想到自己马上就回去学文化课了，不知为何有一些害怕。想到自己已经退役了，要尽可能地体验更多东西，于是决定讲题时要上台表白 T2 的题面。 到了晚上讲题的阶段。T1 的证明有好些和我的思路相似，而分拆的地方用连通性证明，非常巧妙。T3 基本没听懂，但看到直接输出最短路可以拿好些分，我又想起了“乱搞”算法的重要性。T2 讲解开始，我如愿地上台，并出乎意料地收获了不少掌声；后面的讲解也听懂了不少，又发现 Alear 的做法与正解其实有一点点接近，因此得 40 分应该也是正常的。 了解到大众分，我的心情也更加好转了。回到宿舍便继续 D，读着读着便有些困倦。 ### Day 4 黄昏 早晨起得比较晚，因此到国家候选队论文答辩的时候已经晚了，教室里人分布得非常稠密，于是我和 Alear 就不想进去，只想在外面看。 我们站在前门，听了一段时间，结果 dzd 出门看到我们，就说：“进去啊，现在还可以进去。” 于是我们就强行挤进去，后来还找到了座位。听了一上午，感觉 OI 的知识点扩展好快啊，于是又在 LA 群探讨了 OI 知识点变化如此之快的原因。 接下来是闭幕式。[这里](https://www.luogu.com.cn/blog/Sweetlemon/noi-2020-ceremony)同样记录了闭幕式的内容。最后拿到了一块银牌，从奖牌的成色上来说，应该是匹配我现在的水平的吧。 下午回到宿舍，被布置了写游记的任务，然而还是以睡觉为主。 晚上来到自习室写游记。在 LA 群看到了大家与 kkk 面基的照片，遂想尝试。得知 kkk 第二天早上有空，经过尝试，终于约成功（社交经验++）。 晚上回到宿舍，本层楼还住在宿舍里的只有 8 人了，学校里也好像冷清不少。 由于第二天有约且要收拾行李，没敢睡晚，因此没玩 D。要是真的玩了 D，怕是会“玉枕**纱厨**，半夜凉初透”哦。 ### Day 5 灿烂的夜空 早晨吃完早餐，基本按时间规划离开学校，并把行李放在教练的房间。 到地铁站，简单确认了一下发现了 k 总。时间还不到 9 点，地铁站的茶颜悦色还没有开门，于是 k 总请我们喝了一杯瑞幸。JasonL 拿到了国家集训队论文集，遂请 k 总在论文集上签名；我没拿任何纸质书，最后想到请 k 总签在胸牌上（笑）。另外，我基本没喝过奶茶/咖啡，竟然不知道热饮怎么喝（捂脸）。 喝完茶，k 总带我们去逛了长沙的老街，看了看火宫殿，参观了超级文和友。一路上也交流了各种，对 OI 界的许多认识加深了。最后在超级文和友拍了一张合影，下次有机会还真想去上海洛谷总部参观一下。 与 k 总告别后，我们又到附近的茶颜悦色，每个人点了一杯幽兰拿铁。香甜的奶油之下，是醇味的茶饮，让人切实感受到了拿铁的快乐（大雾）。 接下来我们到一家 ~~香菜~~ 湘菜店体验湘菜，吃了些醋血鸭、剁椒鱼头这样的名菜；果然我被食堂惯坏了，吃到有一点辣的菜就浑身发抖，太可怕了。 吃饭吃得非常急，因为此时离我们的火车出发已经不到一小时了。然而回酒店的路上又遇到了堵车，在酒店又遇到了房卡失效等问题，于是最终还是误车了。 后来几经辗转，我们坐上了一趟开往北海的列车。在列车上我们继续玩 D，我和 Alear 毫不犹豫地选择了向 S 告白，实在想不到没多久就遇到了那样的结局。我没有什么玩二周目的心情了，最后看了些剧透，又复习了 git，就结束了 NOI 的旅程。 回归文化课之后，我想我还是会偶然回去看一看的吧。 我把文化课的书籍收拾到袋子里，关上了机房的门。 星光正好。 ### 尾声 事实上这篇文章到这里本来应该结束了的。 但是一路上，那个游戏给我的思考，让我认为有必要加上这一段。 首先，再次强调，请不要无视其警告。 我只玩了一周目，因此给我印象最深刻的还是 S。她让我想起了西宫硝子，也许都没有认识到自己的价值，觉得没有自己别人会更好，然而事实完全不是这样。 进行到后期，S 真的让我感到心疼；我也想要责备主人公，为什么不能做得好一点。但在最后的选择中，主人公不管选择 friend 还是 lover，都无法拯救 S，这也是非常无力的。我想，我们能做的，也只能是珍惜身边的人吧。