NOI 2024 游记

前言

这是我的最后一场 NOI，也是作为正式选手参加的第一场 NOI，不过作为 D 类选手参加的经验还是很足的！

省选以后水平并没有很大的进步，三次省队集训没做出任何不该做出来的题，不过心理状态一直比较平稳，我也早已认清了我不是天赋哥的事实。

7.13 UNR #8 Day1

两个小时做完了前两题，但是第三题只会 24。

下午想了想，感觉第三题至少 n\le 4 是不难的，但我确实没想到啊。急。

7.14 UNR #8 Day2

获得了大众分 100+40+40。

总分 504，rank 40。主要问题就是 Day1T3 分太少了。

7.16

进入了 CQYC，但是并没有心情面基。

下午和 fireinice 一起打板子。

晚上听了一遍加尔基，似乎 2024 年的所有大考前都听了加尔基。

7.17

早晨是开幕式，印象最深的就是 N O I 三个大字在屏幕上晃来晃去，让我想起了这张图：

下午试机+笔试，试机题是 NOIP 2023，但是我仍然不会 T3，好心的 yaoxi 老师给我讲了一下做法。

笔试听说把上次同考号选手的答案发下来了，但是我手速慢了没登进系统，没能拿到答案。不过今年的题似乎没啥坑，问了一圈除了被拿到的答案坑了的以外，没有不是满分的。Eaoci 照抄拿到的答案，然后扣了两分，有点难绷。你的 A 队加分怎么是加三分啊？

晚上和 fireinice 加训 slay。

睡觉前听了一遍《In Rainbows》。这个时候还挺有睡意的，In Rainbows 这张专辑里也没有情绪激昂的歌。但是躺到床上以后总会去想明天怎么打，翻来覆去到一点才睡着。

7.18 Day1

早晨七点起床，喝了一瓶红牛，感觉困意消减了很多，但是七点五十坐在考场里有点想吐。

八点，强压着想吐的感觉，看了一遍三个题。给我的第一感觉是，T3 是可做题，可能需要拿不少分才能进队线。此外，目录页写了个“预测试点数目”，说明今年应该是类似于 IOI 赛制的东西。

决定顺序开题，想了想 T1 发现需要 a,b 里每个数出现位置集合的可重集相同，那应该是哈希，但我怎么快速求出来一个区间的哈希值呢？好像很难啊。这个时候我还没发现可以直接双指针，所以我认为哈希的思路是不可行的。

于是我换了个思路，编出来一个不需要哈希的很难写的做法，写到九点半发现过不去小样例。实际上我已经知道了错在哪里，但是已经写了 3.5k 了，再写下去就寄了。我强迫自己冷静下来，仔细想了一下，发现可以直接双指针，15min 写完了。

十点的时候开了 T2。首先最朴素的策略就是先分治，分治到比较小的时候跑 n^2 暴力，写了一下发现可以拿 51 分。又想了想，我可以把这个策略推广到，每次选择一个 k，把 n 个数尽量均匀地分成 k 份，每份内同时跑暴力，然后递归到 \lfloor\frac{n}{k}\rfloor 的子问题。写个 DP 决定最优决策点，拿到了 91 分。此时是十一点。

因为我觉得 T3 是可做题，所以拿到 T2 91 分以后就直接去看 T3 了。想了一会 T3，发现判定是否有合法方案，就是先把能确定方向的边确定了，如果这个过程里矛盾了就不合法，否则合法。

直接做是 n^3 的，分不太多，但我不会更低复杂度的做法，所以直接写了。十二点半调完，发现 selfEval 能跑 56 分，那我就直接认为它能跑 2000 了，自信即巅峰！

剩下的时间在写 B 性质（菊花），但没写完。

结束以后问了一下坐我背后的 Nesraychan，他 234，写了 T3 的 KDT 做法但被卡常了。

出来问了一圈，好像我比集训队线高了一点。

下午听讲评，好像不仅 n^3 能过 2000，写得好的指数级做法也能过 2000，怎么回事呢？

7.19 社会活动

社会活动是参观三峡博物馆，但是三峡博物馆里大部分展厅好像和三峡没关系啊？

在博物馆里听得昏昏欲睡，下午直接回宿舍睡觉了。

晚上去自习室和 fireinice duel，但是他没加粉兔群，所以我们随了几道 AtCoder 题做，并成功随到了 ABC 特色套路数据结构，我们两个都不想写；还随到了某场 ARC 的 E，我们两个都不会做。

睡前听了一半的《大人》。这次倒是很快睡着了。

7.20 Day2

八点先看了一遍题，怎么 T1 是数论？群友说的 jv 题不会是这个吧？

先给 T1 打了个表，但没看出任何东西。观察大样例发现答案不会很大，所以先写了个 dfs，卡卡常获得了 90 分。

九点开了 T2，这看起来有点典啊，应该得过了才能拿 Au。我先写了 O(n^2) 的暴力 DP，这个 DP 是个半在线的形式，于是我想套个 CDQ 分治上去，在树上应该就是点分治。过了一会发现假了，因为转移点可能不在当前的分治区域内，而且就算没假也是个大常数 O(n\log^2 n)，不一定能过。

换个思路，树剖以后对每条重链分别做。这个 DP 倒过来就是一个线段树全局 check min，全局求和，所以我可以先做这个东西然后撤销回去（具体做法见 我的题解）。写到一半发现根本不用线段树，map 就能支持这些操作，所以很快写完了。

测了一下 pretest，最慢的点只跑了 0.4s，我自己造了一棵完全二叉树甚至只跑了 0.2s。

这个时候是十一点，我觉得已经稳了，但是这个 T3 看起来还挺有意思的，所以剩下的时间就在慢慢做 T3。

首先 T3 的一类点需要的是 DFS 树只有返祖边，这也意味着 DFS 树是唯一的。这样的话 A 性质和 O(nm) 的 B 性质都是简单的，但是我一直不会 O(n+m) 的 B 性质。十二点时我觉得不能再想下去了，所以拼了 25 分暴力。

还剩一些时间，我想了一下 BC 性质，现在我已经知道了一棵满足一类点条件的 DFS 树，那我可以直接在树上做个 DP，就能确定所有的一类点。于是又获得了 10 分。

还有二十分钟，我觉得 T3 剩下的分已经不太可能会了，所以给 T2 写了个对拍。

下午是签约环节，在我家长的劝说之下报了 t。但好像我认识的人几乎全都报了 p，有点玉玉，也不想加训了，所以随便找了个专辑《Ants From Up There》听。

晚上和 jsy, YunQian 换了徽章，咕了好几天终于换成了。

后记

后面几天就一直在重庆玩，和 xqw 家长群群友玩了点桌游。

我的最终得分是 100+(100+91+56)+(90+100+35)+5=577，并列 rk11。考得最好的一次是 NOI，也属实有点狗运了。

xqw 家长群大获全胜，拿了 13 块 Au，我的一个同学也拿到了 Au，祝贺他们。也有一些我认识的人没有取得理想的成绩，祝愿他们 OI/whk 加把劲，希望明年能够在北京相见。