NOI2024游记

终于还是到了这一天。NOI，无论金牌与否，都会是我 OI 生涯中最后一场正式比赛了——哪怕进入了集训队也是这样。那么，走完最后这一程吧。

Day -6(7.11)

结束学考，抵达重庆，最后四天集训。

Day -5(7.12)

模拟赛挂分，原因是不会贪心。感觉真是越学越菜了。

晚上和 Clonoth,A_zjzj,275307894a 一起加训博弈。

Day -4(7.13)

UNR Day1。被 T3 的部分分爆了，赛后发现少打了 38 分。

下午还在加训博弈！

Day -3(7.14)

UNR Day2。不会交互，不会 DS。最后获得了银牌。

但反正 UNR 也就图一乐（确信）。以及这个区分度疑似有点太优美了。

下午接着加训博弈！

Day -2(7.15)

最后一场模拟赛！一道 DS，一道交互，一道提答，我们模拟赛真是太厉害了！

下午依旧加训博弈！

Day -1(7.16)

报道日！上午去了学校，但是教练带着学籍卡下午才来，不过也没太影响。

徽章带太多了，只换了三分之一不到。

不知道该复习什么，随便敲了点板子，然后就开始摆了。

Day 0(7.17)

上午开幕式有点太抽象了。只有最后的音乐剧还可以，虽然有一点点小尬。

下午试机+笔试，好像出了些“问题”但是我没有遇到（指去年同考号选手的答案还保留着）。结果笔试挂分了，死因是开考前不能碰键盘。出师不利啊。试机是 NOIP2023，受不了一点，全省队 NOIP 最低分跟你开玩笑呢。

晚上仍然不知道复习什么，随便看了几个题就开始摆了。

Day 1(7.18)

第一天比赛日，起了个大早。

8:00 准时开题，密码是“just remember 19”。交互是什么东西，是 “rembember” 19年的交互题么？

我就一题一题的看，发现都没什么思路。那我只好一题一题的做。第一题看起来比较抽象，开始想着先 \(O(m!)\) 枚举，但仔细想想这东西显然不可能是正解。推了一下发现相当于要求两个序列中每个数的出现集合的集合相同，那就直接哈希一下就好了。开写！大概 9:00 写完了，第一题做了一个小时，感觉还行。但是为什么 selfeval 里面有 20 个测试点？

第二题是个交互，找最大值，要步数比较少。感觉有一点困难，先写点部分分。第一个点很好写，第二个点也有一个显然的二分做法。然后把底下几层暴力一下就 \(52\) 分了，不知道行不行，先放着，去开第三题。

第三题的特殊性质看起来不难，性质 A 是显然的，性质 B 是一眼 2-SAT。但是 2-SAT 最小字典序怎么求来着？板子打少了。想了一段时间不会，又回去看第二题。

观察一下，一个比较明显的做法是分层，也就是将区间分成一个树形结构，求出一个区间的所有子区间的最大值之后，用 \(n(n-1)/2\) 次询问求出它们的最大值。想起了模拟赛的一个题，询问方式是类似的，要求是排序，做法是按照归并排序分层并行一下。那么这道题显然也可以并行。

接下来要做的就是一个 DP 了！但是这个 DP 的复杂度为什么这么高，达到了 \(O(n^3)\)，优化一下也只会 \(O(n^{2.5})\)。打个表也没发现有什么规律，就是 \(2\) 的方幂特别多一点。那先尝试手动分块一下，结果比直接二分还弱一点。不管了，先去看第三题。此时大概已经 11:00 了。

又想了一段时间的 2-SAT，发现还是不懂。没时间了，得开始写了！拼了前 10 个点的部分分，有性质 B 的 \(O(n^2)\) 做法，性质 A 的暴力做法，还有 \(O(n^2m)\) 的贪心做法。写完这些将近 12:20 了。

很急，第二题还得骗分。想了一下，第一层分一下块，后面再套用二分做法，获得了 \(69\) 分。此时已经没时间了。检查一下就收卷了。

收卷收了 \(10\) 分钟，然后又是在这段时间内我发现我会第二题了，只要换个方向 DP 就对完了。感觉很寄，大家是不是都过第二题了？第三题是不是都保底 \(56,64\) 了？比大众分低了 \(50\) 分左右啊，这怎么翻？

出来之后发现真的比大众分低了 \(30\) 分。很寄啊，不知道怎么翻。下午讲题前大家口胡了一下发现又会 T3 了，那今天岂不是爆完了？算了，就这样吧。

Day 1.5(7.19)

社会活动。去了三峡博物馆，然后不知道跟三峡有什么关系——原来原名是重庆博物馆。

在博物馆里走了两个小时，感觉一般，不太好玩。不如加训博弈！

Day 2(7.20)

很大概率就是最后一天了，认真打吧。

同样是准时开题，第一题数学题，第二题一眼典的树上 DP，第三题图论。感觉有点优势？

第一题推了一会发现要求辗转相除每一步的商都是偶数，那就有了一个 \(O(n^2)\) 的简单做法。但是不会优化，先这样吧，\(50\) 分拿到。8:30，直接去开第二题，因为一眼典。

典归典，要想的细节还是一点不少。先写了一个 \(25\) 分的暴力，然后尝试用 DS 优化一下。可以先树剖，每次处理一条重链；转移式子是区间和，可以拆成前缀和；于是每个点就有一个存活时间，也就是给重链上的一段区间贡献，用 BIT 维护一下就好了——以上内容想了一个多小时。但是不难写，写写调调，再小小的卡一下常，大概在 11:00 的时候通过了这道题。

上个厕所冷静一下，感觉今天应该是不会爆炸了，但是这样肯定还翻不了盘。回去看第一题，想了想会了搜索，再剪剪枝就卡过了 \(95\) 分。很喜欢一句话：\(5\) 分谁写。直接去冲第三题。

然而第三题是我一点不擅长的图论，还是那种经典的分类讨论题，那就更不会了。写了一下会了性质 A，会了性质 B 的 \(10\) 分，然后就没时间了。检查一下，收卷。

总分 99+209+215=523，至此 OI 生涯的最后一场比赛，就结束了。

乐观地估了一手分数线 \(520\)，因为两天队线加起来减掉 \(30\) 大概就是这个数。但是队线随着越来越多的人分享了自己的分数一路飙升，最后停留在 \(538\)，也宣告了我这个分完全没法碰瓷金牌。或许是因为两天都有不错的 pretest 吧，导致今年挂分的人数少之又少。不过也无所谓了，感谢一年半以前的自己给了现在的自己一个机会，能够不带包袱，全凭热爱来到 NOI 的现场。

问了几个人好像都进队了，好神奇，这就是身边统计学吗。

晚上去 AK 了一下嘉年华，投壶和射箭有点难；接棒子直接作弊（手的位置）；颠球很好玩，全程就没停过笑。不知道换什么奖品，拿了一个笔记本回来。另外吐槽一下 OIer 都唱了些什么歌，三首米游，一首鸡哥，还有一首你被骗了。

Day 3(7.21)

早上是《我与NOI》，（待补）。

下午闭幕式，领到了第一块银牌（不只是证书），还是有点小小的遗憾吧。不过看到大家都进队了，自然也是很高兴的，到时候可以北京再见了。

Day 4(7.22)

返程！再见重庆！再见 OI！

不做过多的总结了，大学再见！