NOI2022 游记

前言

经历了几年的徘徊和折磨，现在终于是要正式退役了吧。

为了清楚地传达时间，就用日期来记小标题吧，机试在8.23和8.25。

8.20

早上坐一位本地大叔的车，来到了OI生涯的最后一站。校门前没几个人，大多都是送孩子的家长。即使是来自遥远的省份，家长还是愿意亲自护送孩子到最后的战场。

检查完健康码核酸身份证过后，我带着行李进入校门。我爸在低矮的铁栏杆外向我挥手，我也举起右手回应。我们都知道这是一次不同寻常的告别。对我来说，也许在我几天后走出校门时，一切都变了，唯一没变的还是这一挥手。

哎，这才第一天呐，心情已经不自觉地开始压抑了。这一天还是要多找些轻松的事才行。

上海华二昆山国际学校蛮大的，和BZ的渝北校区差不多吧，区别就是有点太平了，没有斜坡和长台阶:D

签到大厅里人很多，好多选手不认识（这是很正常的，毕竟只在网上见过），但是签名墙还是有些熟悉的称呼的。大家都签的网名，所以我也签网名好了，全都是大写字母感觉太突出了，就用灰笔好了，这也符合我的炮灰身份。$\mathrm{O}\mathrm{neInDark}$ 签下网名后就没再写什么了，于是我好心地给祂用金笔标注了一个“永神”。

豪华寝室，两人一间，还赠洗漱用品。我想起了以前CSP收百元，键盘老化错位，草稿纸稀薄四张抵一张的经历，割裂感甚重。食堂体验舒适，但是实际上吃的种类偏少。

剩下的就没什么好记录的了，基本上就是开摆放松，面基遛弯。MC小存档的刷铁机终于制作完成了，由于村名里只有一个农民，34格地，所以生育进行地缓慢，等到豹猫出现的时候，已经开始高效刷铁了。

虽然写了一点复习计划，但感觉写的都是些废话，看着旧题单还是无从下手。打了上百场模拟赛，两百篇博客题解，就是为了在这个时候用上啊！

思绪好混乱，不知道能不能调整到好的状态。

8.21

正式注册日，因为地区是重(zhong)庆的缘故所以11点过才领包。

之前对换徽章这件事不是很在意，现在才知道一个人至少有10枚自己头像的徽章，剩下9枚都是可以换的。然而我懒，所以就找临近的大佬换了6个（crashed的头像真朴实）。

22号要笔试了，所以今天一半时间在疯狂背单子（还有一半时间在疯狂摆）。

室友的密码条掉了，被人（不是工作人员）捡到了在U群里喊话，我也算见证历史了。不过只要不向工作人员要新的就不会扣分，所以我们早就有备份了，代价只有室友社死。

剩下就没什么好写的了，今天是相对无聊的一天（其实是因为我摆得太投入了所以没时间写了）。

8.22

上午具体干了些什么忘了，因为我是25号开始补这4天鸽掉的游记

因为下午就要笔试+试机，所以上午应该在疯狂背单子。

赛场很大很宽敞，但是空调不太给力，坐一会就开始脱外套。考前一天需要练板子，正好利用试机的两个小时打一打。

笔试题目有一道“开考前能否登录系统”，这条在题库里没有，不过根据“不能触碰键盘鼠标”合理推测应该是不行的（机试前的广播也印证了这一点）

本来计划着打一打Min25筛的，但是却发现根本记不住怎么打，只能试机完了回寝室看模板。后来证实我练习的所有模板中只用上了zkw线段树。

晚上复习不下去了，于是串门打牌去。6人局，手气意外地好，赢了三把，感觉第二天的RP被掉光了。

8.23（竞赛日1）

机试第一场，全身紧绷，手心不停出汗。尽管我已经打了上百场模拟赛，但是想想真的到了NOI2022Day1还是根本镇静不下来。

记录比赛实况，游记也要写一些正式的东西了。

---

Day1预估题目难度正常，直接顺序开题。

T1比较简单，经典众数题，可以线段树合并+线段树二分，直接开打。

代码打到一半去拉屎。临走前看了一眼T2题面，但是拉屎的时候主要还是在想T1的代码实现。苏州这地方我就没见到过一个坑位，公共厕所全是马桶。众所周知上厕所是OI系列比赛中的重要一环，但是我所有模拟赛上厕所都是蹲坑啊，蹲坑才是我想要的体验！

拉完回来，把T1代码的deque换成了单向链表，然后统计答案加上了long long。后来打听到，这两步是保命步骤，用deque的和没开long long的大多挂了分。

T2是个序列计数题，我直接往DP套DP上面想去了。感觉状态数可以缩到很少，于是在我两个小时的画图和猜测下，终于感性证明把 $k=0$ 时的状态数缩到了9个，已经可以在暴力基础上多得25分了。

然后 $k>0$ 怎么办呢？我又试图往贪心上想，想着想着看时间不够又索性开始打，打了一会又发现假了。MD当时已经快到12点了，T3还没看。

真的很慌了，脱下外套透了会气，感觉把T2贪心改一改应该可以卡过 $k>0,l=r$ 的点。于是改完后加了些边界特判，然后快速冲一个暴力开始看T3。

已经12点过了，我还要留下30分钟检查，不能再奢求更多分了。T3这个第二档分感觉很好拿啊，猫树比前面的换根DP好打多了。打完过后调了调交互，发现第二档的样例卡死了出不来。我又试了两个小的手玩数据，却发现没有问题。（考后才发现是我二分死循环了，而手玩正好没进死循环，NND我是啥B）

这个时候已经剩不到半小时了，我只能放弃调试检查T1T2了，毕竟要是T1T2的分挂了，那我就直接寄了。

---

下午查分，好在T1T2都没挂分，T3爆零。总分155，居然意外地挺高，这5分还把B类劣势拉回来了。

时间安排和省选的时候很不一样，后面还有一天半的时间准备Day2。

卷是不可能卷的，直接B站、MC、纸牌搞起来！

8.24

上午：颓废

下午：开幕式，颓废

晚饭时：不能再颓废了，你要考Day2了啊！！！！！！

晚上：颓废

睡前看了一下以前模拟赛的总结，感觉啥也没记住就睡了。

明天是最后一战，还是不要给自己太大压力了。

8.25（竞赛日2）

5点过的时候被冷醒了，开26度的空调居然因为一直扫风把室温降到了23度？！！

好不容易暖和一点了，腰又开始痛了。这几天每天都没睡好，早上6点过都会被腰痛醒。

开考前的状态…总之就是困到不行

---

T1居然是久未见的判断树同构的题，还好心提醒了数据不会卡树哈希…

树哈希的方法几乎忘光了，只记得某个方法好像和质数有关，就胡乱凑了一个，感觉挺合理。

T1真的良心，仅用树哈希+指数级暴力+小优化就可以得80分。于是在想了一阵子想不到正解之后，直接开打80分，打完就把文件夹iso暂时扔一边去了。

T2是道冒泡排序题，有种莫名的亲切感。

首先可以证明最优解取值一定可以只取 $m$ 个限制给出的值。

考虑怎么判断无解。我可以构造出一种方案，即按限制的值从大到小给区间内未赋值的位置赋值，然后看区间内有无取到最小值的。可以想到最优解一定是在合法情况下，把这个方案中的某些值增大，所以我们需要锁定一些位置的值不变动（限制的最小值一定是取到这些位置的），其它位置的值要求不小于构造中的值。最后算答案可以计算锁定的位置之间+锁定与非锁定位置+非锁定位置之间的逆序对。

可以很自然的想到一个贪心，即我们需要尽可能地让某个位置不锁定，这样一定不劣。

（看一眼时间，MD慌起来了）

然后…然后仍然按照构造的思路从大到小考虑每种值，可以发现在最小化锁定的位置之间的逆序对的时候，实际上是与最小化后面两项不冲突的，即最优解的锁定位置间的逆序对数一定是最小的。具体而言，当我们考虑最小化某种值的锁定位置的逆序对贡献和时，一定会最小化锁定位置的数量，并且此种情况下计算后面两项逆序对一定不劣。

（感性证明，感性证明…）

于是可以搞出一个 $O(n\log n)$ 的方法确定所有锁定位置。接下来若仅计算锁定与非锁定位置的逆序对的话，每个非锁定位置是独立的，可以一个线段树+扫描线。但是还要计算非锁定位置之间的就不好搞了。

在研究特殊性质B的时候找到一个结论：若非锁定位置的取值下界为0（即取值无限制），那么最优解中非锁定位置的取值一定单调不降，也就是没有逆序对。现在加上下界，那么对于非锁定位置 $i<j$，若 $j$ 的取值在 $i$ 的下界的下面，那么就有贡献；若在下界的上面，那么可以证明最优解 $j$ 的取值一定不小于 $i$，那么就没贡献。

于是 $j$ 的最优取值只与 $i$ 的取值下界有关，与 $i$ 的取值无关了。

然后线段树就做完了？

打完调完T2过后差不多12点了，T3赶紧冲一个指数级暴力走人。

---

查分了，很幸运，T1没有挂分。T2挂了4分，不知道哪个小细节出了问题。T3有个点1.936秒卡过了所以多了4分。（感觉自己要飘起来了）

两天分数加起来 155+193=348，刚好是我去年NOI同步做的成绩欸。

这个分数，不出意外的话应该是不用高考了~~

OID直接200+，%%%，但是第一天被deque阴得太厉害，还是没戏了，悲😟

8.26

疫情原因，闭幕式没了，今天成了最后一天。

火车上挺无聊的，由于订票时间紧所以没有和同学们订在一块坐，只能自己打打游戏睡睡觉。

火车上吃了三桶泡面，汤有点咸。

---

中午获奖名单就出来了，刚好冲进前15。

滚吧！吃人的高考！

我解放了！

CNM！

---

结语后面再来补吧，颓废去了。（话说牌子是要邮寄还是直接不发了呀）

结语

说一下这次NOI的心得，以及这几年的生涯回顾。

这几天不断的被奶+被泼冷水（包括自己对自己的），把我给整魔幻了。入省队以来的这七十多场模拟赛发挥得不错且相对稳定，于是被说是“金牌希望大”、“黑马”，然而关键赛事还是要翻大车（PKUSC、UNR等）。

这次NOI超常发挥除了碰到比较熟悉的题型（DP套DP、冒泡排序），其实主要还是因为策略稳吧。想题时直接部分分入手，过渡不到正解立马放弃去打很肥的部分分。心态？我心态可是糟糕的很呢:D

估计巨佬们的反应会是：怎么一个听都没听说过的小菜鸡冲前面来了呢？

事实上在这次NOI以前，我从来没获得过任何比较引人注目的成绩，而不少去年就国集的巨佬今年的表现就很能引起其它选手的注意。模拟赛打得好？顶屁用，在外人眼中还是坨*。

省选倒数第二进省队B类，我拿什么在其它选手面前炫耀？

高一一年啥成绩也没有，THUSC还两天爆零，我凭什么让别人知晓？

OI生涯连一次NOIP省一都没得过的省二选手怎么能和这些两枚金牌的巨佬比较？

当学校宣传要求再附上一些其它的成就时，我翻遍阅历，却发现根本没有什么拿得出手

我深知我是一个很弱的炮灰，而前辈们的经历告诉我选手的实力大多是高一就定型了，很难再升档次。当我的最后一次NOIP仍以省二失败告终的时候，除了教练和老师们，没人对我还抱有希望了。

当时队里的策略很奇怪，不管省没省一全部准备省选，不劝退任何人。然而尽管我不是NOIP考得最差的，却是唯一一个一次省一都没拿过的。我当时赌一口气，觉得怎么也得得到点荣誉吧，哪怕省选前20不进省队，也不能让三年OI一场空！

后面的训练不好评价，只能用疯狂+大开眼界来形容。疯狂是因为模拟赛轰炸，两天一场还带专题训练，而大开眼界是因为我发现我真的好多东西根本不会，好多板块学得像*一样。

网上认识了RSX等人，交流的时候提到NOIP成绩，我如实交代了分数和排名。RSX听着感觉不可思议（当时我的模拟赛成绩刚刚开始突进），然后很中肯地认为“没什么希望”。

省选时究竟发生了什么，可以看我的省选游记。省选翻盘，是我OI生涯最要紧的节点。

进入省队以后，我感觉自己已经上升了一个档次，总算和共同训练的选手“地位平等”了。

后面冲刺NOI的训练，其实没有准备省选的时候那样煎熬和吃力，有时候还会摸鱼。不明白这种现象，可能是因为“实力”这个东西，真的发生了质变么。

我不再是炮灰了，而是直接以金牌为目标的省队选手。

我想起来初三那个暑假，我是为什么执意要在退竞赛一年后重新开始呢？当时大概是中考翻车了，赌气觉得自己文化课没有出路，高考也会翻车，不如靠干自己喜欢和擅长的事升学。当时那个水平就定下不想高考的目标，绝对是幼稚和好高骛远了。

---

  ~  
  ~  
  ~  
  ~  

NOI刚结束的一两天，我的情绪非常奇怪。抑制不住的喜悦，但是却并不怎么激动。午觉睡得特别好，晚上却辗转难眠。

直到，我看了同伴们的游记，意识到一些东西再也回不来了。

我们都知道NOI拿银牌铜牌对一个高二的OIer意味着什么。三四年，甚至五年以上的OI生涯，就像一场梦，在走出赛场的那一刻终结。

---

从高中竞赛队成立以来，大家一起做题、讨论、分享自己的研究和发现，分享自己的心得感悟…

从机房边吵闹着边走下楼，买走食堂最后几勺菜坐在空食堂里吃…

敲着代码时不忘向对桌发着嘴炮，闲了就在机房追逐打闹，像幼儿园小朋友把地板踩得咯吱响…

三五个人趴在窗前侦查天象，雨停了就高呼打球…

---

现在大家退役了，离开机房去教室寻找自己的归宿，那么“不退役”对于我而言，尝不到半点的欣喜。

一个选手的OI生涯绝不仅仅是参加过的比赛，获得的荣誉，写下的题解博客，和学到的知识。

队友们的旅程结束了，我的OI生活也已经残破不堪。

经过金牌过后短暂的爽快过后，我才意识到自己所处的折磨。一边是转身离开的同甘共苦的队友，一边是不等我准备好，如暴雨般袭来的未来。

MD，文笔不好，好多话想说却说不出来。
我喜欢OI，喜欢信息学，喜欢你们所有人。

G2023 TOGETHER WE WILL MAKE IT