NOI2022 退役记

It's My Fiesta ~

zxy 的 NOI2022 游记

一些闲话

首先，笔者是 NOI2022 Ag，已经退役了。

在这段搞文化的日子里，总觉着这篇游记不能少，虽然打得非常煎熬，但我也不希望忘记这一切。

前天收到了获奖证书和奖牌，当我看到 zxy 的金牌时，我意识到我还没有对这次失利释怀，我的脑中还是在不断重复“要是不挂就好了”。

或许有一天我会与 NOI2022 和解，不过想必前提一定是我在没有得到这块 Au 的情况下，仍然得到了更棒的东西；也或许只是随着时间的推移，这种痛苦逐渐淡去，只有在提及这一切的时候，痛苦才会被唤醒。无论如何，我期待这天的到来。

前情提要

NOI2021，Day1 做了 4h T1，喜提 168 的高分；Day2 想到 T1 随机化的做法，最后因为实现的问题沦为暴力，总分 99。

NOIP2021，T3 写了个奇怪随机化拿到了 100，总分 324 排名 HN-02（并列）。

联合省选 2022，Day1 被卡常 40 分，Day2 靠着 T2 的一个奇怪随机化贪心多拿了 8 分。

最后以 1.5/1000 的微弱优势拿到 HN-01。随机化赛高

Day -?

听说要早一周到昆山，于是联考集团在某酒店包了一个会议室来集训。

这段时间认识了 XJ 的 zky，zy，xyf、ASDF 的 wd，zjf 等人，但是其他人大概对我没啥印象。

三场模拟赛成绩分别是第 5、20+、还有和 30 多个人并列的 AK。

雅礼的那场模拟赛，一开始搬的题看起来被群友卷完了，于是临时改成了之前的校内互测题和 zxy 出的一个题。感觉也挺好的，在雅礼最后一场模拟赛留下每个人的痕迹。

Day -2

进校。感觉这个学校非常高贵 据说一学期的学费值一个 C

在签名墙上留下了一个小小的 “CXY07”，然后和 juju 一起转了转，把几个关键的活动场所都逛了一遍。在考场外疑似透过玻璃门看到了 zyy /xia。

发现由于省队排名的缘故，和三个 HB 老哥住在一个寝室，击中了不与 zxy 一个寝室的 1/4 的概率。

Day -1

领到了纪念品，和之前订的 30 个徽章。和省内的朋友们换完就少了 10 个左右。今年竟然还有吉祥物 /jy 但是为什么之前说好的衣服是蓝色，现在却变成了绿色，差评

晚上迎新晚会，感觉氛围挺不错的，除了坐在地上咋坐咋难受（x）

竟然还有主题曲，很有感觉！

Day 0

上午各种刷笔试，把 ouuan 的题库和 luogu 的题都刷了若干遍，觉得差不多得了就去搞颓了（

下午笔试，右边的是去年 Au，GD 的 cdw。笔试的时候 5 min 写完，然后狂暴检查 5 遍（，最后竟然没有当场出成绩，很难不觉得这是系统出锅了笔试分没了（

回到房间之后就开始狂暴写板子，写了些什么 tarjan、stoer_wagner、SA、KM 之类的，自己经常要蒯板子的模板 可能也是第一次成功默写了 SA。

傍晚被屈哥拉出去散步，聊到了今年大概率有非传统题的事，但我说就算有也必然在 Day2。

回到房间继续写板子，和父母打了电话，收到学长的祝福，晚上 10 点就睡了。

Day 1

早上可能 5 点多就清醒了。6:20 左右干脆起来，准备了下就去吃早餐了。

非常非常紧张，屈哥一直给我打劲，不过进考场前紧张是我的常态了。过了会就进场了。

进场发现座位就在门边，左边是 SC-01 yny，右边貌似是 do_while_true（如果我没认错的话/kk）。

开题发现 T1 就是直接摩尔投票，线段树合并一下就行了。可能需要 deque 来启发式合并，但是我记得 deque 空间有点大，那还是写链表好了。

接着去看 T2，一开始把题看错了，以为是 $r-l+1\ge 2$，玩了一会觉得很简单，就只有一丁点状态不能出现。接着去看 T3，这是个什么锤子，感觉很怪，为什么 NOI Day1 就来交互。

去写了个 T2 的搜索，然后开始写 dp。写到 9 点发现过不了样例，但是和爆搜答案一致。仔细看了看发现把题看错了/tuu，是 $r-l\ge 2$。把搜索改了之后发现其实不合法状态非常多，没啥想法于是先回去把 T1 写了。

写完之后先测极限，然后想了想怎么拍。最后的做法是随机把元素放进一个集合，查询的时候随 3 个序列拼起来（伏笔），直接过拍了。

接着回去 T2。想了一段时间觉得可能自己会一个判定的 dp。大概是 dp 记录有多少个 2 操作是从上一个、上上个开始的，覆盖当前位置的 2 应该不多。

本来想把搜索内层的判定改成这个，后来可能是太眼高手低了，觉得 40 分有点少，就继续想正解了。

兜兜转转去看 T3，想了半天甚至不会第一个包。但是 A 性质是简单的，直接猫树就行。于是就在 T2、T3 之间转了半天，最后突然觉得 T3 的 log 次查询就是个点分树，全然忘记了边集不交的条件！

觉得这个东西有 60 分，于是直接开冲。写完之后一直在拿第一个 grader.o 测，测完以为自己过了。可能最后剩 1h 左右的时候，发现 check.o 才检查正确性！！！

尝试调试，发现 check.o 只输出哈希值，根本没法调。试着把 info 再套一层 struct，在里面自己记一下点集，不知道为啥咋写咋 CE......

到最后 10 min 的时候才醒悟这做法根本不对，这时候 T2 还只写了 15，T3 的猫树也还没动。直接红温了，想直接写个 T3 的 $\mathcal{O}(n^2)$ 说不定第一个包就是这么过的呢？结果还是过不了，直接预处理甚至是 $\mathcal{O}(n^3)$，根本没戏......

然后就下考了，我的估分是 $100+15+0$ ......

我无法完整地形容出那一刻的感觉，看着人潮朝我涌来，我的手在颤抖，双腿几乎无法支持我站起来。

我突然觉得都无所谓了，什么 HN-01，什么 Au Ag Cu，什么 THU，都无所谓了，都没有意义了。

走出考场，看到了站在外面的 Qiuly。他问我咋样，我只能不停地说“我完了，我完了”。

后来听到大家都只有 115、125，可能稍微有所缓解。但在和 zzm 讨论 T1 做法的时候，他说他做法是直接二分，但比较坑的是要开 long long。我心头一紧，问为什么要开 long long，得到的答案是序列编号可重。

意识到我的做法也需要 long long，但我没开。我甚至在下考前的最后 1min，盯着那句 #define int long long，想了想说不开得了。这下是全完了，可能全挂了。

然后就坐在宿舍走廊边的沙发上，给父母打了电话。顿时，我就从一个保 Ag 冲 Au 的选手，变成了不一定能拿到 Ag 的人。

后来，zxy zzm lzh zhy Qiuly 等人都坐了过来，一大部分人都没开 long long。能怎么办，我只能对着大家苦笑。

没胃口吃饭了，直接坐到 3:00，去看成绩。耳机里放的是早就设想好的《Paris In The Rain》，我打开电脑，看见了 $85+15+0$。我不知道是该哭还是该笑，挂了 15 分，或者说只挂了 15 分。

然后在考场走来走去，得知了 zxy 150，zzm 115 的消息，然后听说 lzh 因为空间问题爆零了。

我突然觉得有种被命运调戏的感觉，谁知道呢，打开 pdf 文件之前，谁知道呢。

走到屈哥身边，屈哥把手搭在我的肩膀上，我说我忘开 long long 了，打了这么多场大赛，这是第一次。

后来听说 zhy 105，Qiuly，juju 在 125 左右，Achtoria 拿到了 140。

晚上还是去听了讲课，看着 yyl 讲着是如何将交互 ds 换到 D1T3，出题人眉飞色舞地说着题目的精妙，我开始怀疑，他们是否知道，或是否关心，台下有的人心中无比煎熬。

后来我想了想，我们也出过一些比赛，有一些也关乎升学优惠。我不能说如果我站在台上会做得多好，或者是说我根本不知道应该怎么做，才能减轻他们的痛苦。甚至是与在联赛、省选退役的朋友们的相处中，我也谈不上做得多棒。这次轮到我了，我也该体会一下这种感受了。

Day 1.5

虽然没有比赛，但还是很早就醒了。醒来之后一直躺在床上玩手机，在我印象中应该是没去吃早餐。

我想，我今天就不碰 OI 了。

然后 juju 来找我，于是拉着他一起看了两集《旺达幻视》，还有《寄生虫》。感觉很有意思，但我也说不清到底我是不是真的全身心投入进去了。中途屈哥来了一次，也没说什么。

下午参加开幕式，或许被 CCF 笑话逗乐了。

晚上吃完饭，屈哥还是把我们拉出去散步。他说队线应该在 120 左右（其实比这要高），不知道是不是为了安慰我。他还是搭着我的肩膀，跟我说“没关系”，“何况你还有 A 队加分”......一直告诉我没问题的，没问题的。zxy 也在说，有很多高水平选手都只有一点点分，关键在于 Day 2。

走了两圈，屈哥就说让我们回去了。我没回去，而是接着按照原线路打转。

后来我找到了一个好地方——操场边的看台。我就坐在看台上，发呆。然后再次给父母打电话，他们都说，Au Ag Cu，都没关系，他们都会支持我的。然后想给朋友们打个电话，但算了算他们还在晚自习，于是先打给了姐姐。

和姐姐扯了将近一个小时，其实也并不是真的一直在说 NOI 考炸了相关的事情，更多的貌似在说过去，和未来。我表达了我的一个遗憾——我的高中生活几乎是缺失的，她却告诉我，与众不同的更值得纪念。有道理。

然后打给了朋友，可惜并没有接通。

然后就回宿舍了，这时候我可能已经在看台上坐了 1.5h 了。坐在电脑前，突然发现买的实验舱讲课还压根没打开，“就算听不进去也播一遍吧，毕竟是花了钱的”，抱着这样的心态我打开了讲课视频 然后早上的 flag 就倒了。看到 zzq 讲课的视频，我突然意识到，如果我不是个 OIer，我可能压根 THU 想都不敢想，不会认识像各位这样如此优秀的人，也不会有希望在将来与大家走上一样的路。这么一想好像不亏。

这时候朋友回电话了，我跑出宿舍去接 然后才知道人家压根不知道这是我的号码！！！，描述了一下 Day 1 到底有多寄，情况有多不乐观，但仍然得到了很大的鼓励，收获了祝福。那好吧，不去想 Day 1 发挥得有多差了，毕竟我还是有机会打好 Day 2 的。

再次回到宿舍，洗洗睡了。恩，最后一场了，我争取打得漂亮点。

Day 2

仍然在 $5:00$ 就处于一种半醒的状态了，强迫自己再躺了一会。然后发了一条 “Just Enjoy” 的说说，想到去年考完 Day 1 遇到 Deep_Kevin，他也跟我说 Day 2 享受比赛就好了。当时我从中感受到了无比的遗憾，没想到今年的我也是如此。

吃完早饭，站在考场外排队，屈哥仍然在告诉我，没问题的，相信自己。心跳还是加速，不过感觉还好，比 Day 1 不知道好到哪里去了。

进场，左边坐的是我的室友老哥，右边是谁不太有印象了。这时候我的想法是，“反正不会像 Day 1 那样狼狈了”。

开题，T1 感觉像个神秘的树同构，T2 咋又是冒泡排序，T3 一看就不可做，但是感觉有点像流。

还是先回去看 T1，首先 $k\le 5$ 一看就很有深意，然后如果有相等的子树就不用管了。那么剩下的子树就只有 $5$ 个，是不是暴力枚举匹配就行了啊？感觉很靠谱，但是不知道能不能卡。稍微尝试卡了一下，发现好像就是根拉下去 $5$ 条链最劣。

秒掉之后先不开写，立马去看 T2。一眼某位歌姬的故事，然后感觉有点像之前做过的一个 CF 题。可是我不记得那个 CF 题的具体题面了，两道题的做法我也不完全记得了......可能这就是一味只会做题但是不总结不消化的代价吧。

想了一段时间 T2 没什么头绪，于是先去把 T1 写了。我只会 OI-wiki 上那种树哈希，即使我其实知道那东西巨大好卡。于是先筛了素数（伏笔），然后为了保险甚至写了双哈希。稍微写了一会会，过了样例和自己手造的拉 $5$ 条链就跑了，根本不会拍。

瞟一眼 T3，感觉是一些神秘的流，编了半天编不出一个建模，甚至不一定会用流判定。

返回去 T2，开始从部分分一个一个想。对性质 A 编出了一个 $\mathcal{O}(n^3)$ 的弱智 dp，但是不太会更高的分数了，不过这已经有 40 了，可以接受。然后去看性质 B，首先相当于钦定了一些位置的取值，剩下的该怎么放呢？猜测剩下的部分是单调不降的，然后据此编出了一个 $\mathcal{O}(n^2)$ 的 dp，实现了一下过了样例。然后想如何优化，一开始以为是 dp 值单调，瞪眼了半天发现不太对。继续想了想觉得可以优化成 $\mathcal{O}(n\log n)$，因为貌似如果不是出现了钦定元素，变化都是没有意义的，所以每次只要手动改 $1$ 个值。

写完之后接着去想性质 C。那肯定要把钦定的元素放在区间的第一个，这样后面可以更大一点。剩下的是不是只要在满足区间权值限制的情况下，也单调地放就行了呢？把性质 B 的 $\mathcal{O}(n^2)$ 改了改，发现过不了样例。想了很久，然后花了很长时间把这个 dp 和暴搜写了个拍，最后发现可能一开始拔太高了，后面适当降低还更好。

到这里想法就进行不下去了，尝试上了若干次厕所，也没能想到怎么办。不过脑子里一直有两个声音在打架，“那个题贪心放就行，这个是不是也是呢？”，“这感觉有点假我还是再想想吧”。我还是犯了一直有的问题，两个想法一直在纠缠，却没有做出任何行动......最后迫不得已，尝试着写了一下贪心。

很好写，写完发现竟然过了性质 C 的样例！！！百感交集，既有一种“天不亡我”的感觉，又觉得自己为什么这么离谱，搁那口嗨却动都不动。想着这玩意肯定也能做性质 B，万一性质 B 写错了咋办，然后就把性质 B 注释掉，再实现了性质 C 的 $\mathcal{O}(n\log n)$ 做法。

然后继续去研究 A 的优化。想了半天没得到 $\mathcal{O}(n\log n)$ 级别的做法，但是好像可以用单调队列优化到 $\mathcal{O}(n^2)$，那就先写了得了。还行，这样就有 76 了。此时我全然忘记了最开始想到的 某位歌姬的故事，如果一开始记录下来，应该就有机会了吧......可是我就是这样，不会改正。

时间不多了，赶紧去看看 T3 能摸几分。然后想到一个首先搜出所有可能的方案，查询的时候 chkmax。不管多少分了，写了再说。这回我记得开 long long 了，过了所有样例就跑了。

之后就是不断地检查，文件，内存，样例......检查了不下 10 遍吧，要是是出了这些错误那就是真搞笑了。最后一分钟，我把电脑锁屏，盯着考场跳动的大屏幕，心里也在倒数。“5，4，3，2，1”，结束了，都结束了。挺好，最后的收尾是这样一个浪漫色彩的场景。

出考场，精神比 Day 1 好多了。和朋友们聊了一下，报了 190 的得分，zzm 好像和我差不多；zxy 210，过了两题，真好，大概前 15 了吧；lzh 也过了两题，非常厉害。

接着听说 Qiuly 也 200+，真强。收到通知，晚上就要立马跑路，闭幕式都不办了......也好，不用思考要以什么姿态站在台上了。

回到宿舍，zxy 教会了我 T2——原来再套一个 某位歌姬的故事 就行了啊，那好吧。还是没去吃饭，跑回宿舍立马往 APEX 里氪了好多钱，买了我的第一个传家宝 zzm 称之为破财消灾。接着就是清理行李，到 $3$ 点左右就被催着去看成绩。

推着行李箱离开宿舍，耳机里还是《Paris In The Rain》。走到电梯口，屈哥一个电话打过来。“你快来看成绩，你挂分了，来看看能不能申诉”。

整个人僵住了，背上立马开始冒汗。努力憋出一句“是什么分布啊”，得到的回答是 $84+76+21$。T1 竟然挂了 16，不过 T3 搜出了比我想象中更多的分。于是更加加快脚步前往考场。

打开电脑，找出数据，先自己测测试试。发现就是 WA 了，代码往下一拉，我恍然大悟。我需要用 $10^5$ 个质数，我的筛却只筛到 $10^5$。

此时就像 myy 在 IOI，zxy 在 NOIP 时说的那样，我感觉命运在 tantalize 我。真可笑，最后导致挂分的问题，全是我一直注意的地方。况且，我并不认为我能在考场上修正这个问题，除非一开始就写对。

突然回想到 zxy 博客里那篇 AHU，我考前还在想，要不要看看呢？最后的结论是“算了，考了我就树哈希”。真有趣，当一切都发生了之后，回过头看自己的每一个行为，都预兆着这个结果的到来。

和屈哥一起坐在考场里，他说：“要是不挂这 16 分就稳了啊......现在悬了”。我确实没想到，当我担心的这一刻真的到来时，我竟然这么平静。

之后就是马不停蹄地离开，在大巴上和 zzm 坐在一起，看 yyl 在 U 群理发店。这时候可能还抱有一丝 Au 的期待吧，总之就是紧张得不想说话。不过随着时间的推移，在上飞机前就差不多放下这种希望了。听说了联考集团一些超人们都发挥得很一般，还出现了一些从未设想过的情形，感到非常惋惜。

在飞机上开始写这篇游记，不过因为时间不长所以也就写了一点点。非常神奇，飞机貌似提前了至少 30 min 到了长沙，正好赶上了学校的晚自习下课时间，于是就又打了个电话给朋友。

接着就得知了集训队分布，“雅礼中学”四个字出现在第 $8$ 名，但也仅仅出现在第 $8$ 名。

首先当然是为 zxy 感到高兴，一直以来我都对 zxy 有无限的信心，这种信心甚至超过了对我自己。如今他创造了雅礼近几年 NOI 的最高排名，比 hh 还要更高，实在感慨万分。接着就是好奇，要是在某一个平行宇宙里，在榜单的最后，我又一次找到了“雅礼中学”四个字，我会是怎样的心情呢。

然后突然意识到，如果今天没挂 16，正好就在集训队下一分。那还是算了，要么就都别挂，要么就这样吧。

接着收到了学长们的安慰，并向 pzk，czy 请教了高三经验。然后就睡了。

Day 3

比赛已经结束了，我却仍然在 $5:00$ 就自然醒了。

上午在家玩了玩 APEX，被锤爆了所以其实也没玩多久。下午就被家长拉去一个培训机构，准备补课事宜。晚上和周老师商量了一下，得出了“明天就回班”的结论。

也行，过去的两年里，我无数次地觉得我的高中生活简直是太无趣了，尤其是在雅礼这样多元的学校，看着同学们在各个方面大放异彩，我却只能窝在机房里日复一日地对着模拟赛自闭。或许这是老天给我最好的安排，让我在学习 whk 的同时，尝试去找找自己的初心，体会体会一个高中生应有的生活。

Day ?

被屈哥叫回了机房，拿到了奖牌和奖状，并拍了照片。

好几年的努力，凝聚在这张纸和这块牌中。金牌真漂亮啊，比去年的是不是好看些

然后立马回到了班上，继续上课。

莫名有种怅然若失的感觉，这下是真的结束了啊......

一些瞎扯

到这篇游记发出之时，我已经回班一个月了。目前的感觉还不错，生活很紧凑，没有搞 OI 的时候时常出现的“不知道该干啥”的情况。老师们都很照顾我们，上课都很有意思 回班一个月已经得知若干老师的外号了，同学们也很有趣 花了一整节课一起看海绵宝宝。

不过也还是意识到了，想要达到目标其实也不是非常轻松的事情，还是需要拼尽全力去冲才行。总之，革命尚未成功，同志仍需努力！

我似乎不希望把高三视作 OI 的结束，相反，我更愿意把他称之为 OI 的延续。在这 9 个月里，提升提升自己的文化素养，学一些之前没用心学，但其实也很有趣的知识，这似乎是在帮助完善自己，完善曾以 OI 为生活全部重心的自己。

请 zxy 等我，虽然想必不能继续同班了，但我一定会去那里。

说不定有一天，当我终于意识到了我所真正想要的，我还会回来。

也许我会找到更加热爱的事业，亦或者以更自信的姿态与 OI 重逢。

总之，在这之前，请等我。