NOI 2024 游记

人生中的第一个 NOI。

Day -1

比外校的其他同学提前两周到了重庆，在南开中学参加集训，有极为强大的讲师团队。模拟赛打的感觉还不算很差，不过除了补题之外基本也没做什么别的题了。

UNR 个人觉得打的也不错，能拿的分都拿的差不多了。

下午和外校的其他同学汇合进入重庆育才。WC 已经来过这里了所以校园倒也没什么新奇之处。值得一提的可能是这次育才在校外布置了很多宣传海报和旗帜，给路过的人一点小小的 NOI 震撼。

晚上跟着马思博四处换徽章，马思博还是有人脉的。意外捕捉到了 zak，成功交换徽章，赢。

Day 0

基本没复习笔试，在电脑里下了个 Despised 但是没怎么用过，可能就是 UNR 的笔试场稍微练了下手。考笔试之前的半个小时紧急进行了一波复习，感觉还是能拿下的。

笔试在试机进行半小时后开始。笔试开始后因为网有点卡所以迟迟进不去答题界面，但是此时已经有点喧哗了，进答题界面一看发现怎么答案都已经选好了，简单做了几题发现答案好像都是对的，这下下发 std 了，于是果断保存网页。工作人员紧急修复了这个问题但是题目完全没改，选项顺序都没变，保险起见还是自己做了一遍，然后和 std 比对一下发现没有差异，那就很稳。

赛后有说法是这个提前下发的答案是去年同考号选手的答案，有选手被坑了。去年的 HB-02 也很厉害。

Day 1

开考首先发现题目摘要里多了「pretest 数量」这一栏。pretest 和大样例并不等价，今年的大样例都没有给到极限数据，给的一般是中等大小的样例或者特殊性质。pretest 可以用 selfEval 测试，只能看评测结果，看不到测试点内容，但是 pretest 和正式数据的性质是一样的，也有说法说两组数据是用同样的 gen 生成的。看来 NOI 要变 IOI 赛制了，这是巨大的进步。

顺序开题。T1 想了一段时间，想到可以维护每个元素在哪些集合中出现过之后这个题就好做了，大概 1h 的时候理清楚了做法，但是我做法里有二分哈希以及二维数点，所以写起来有点答辩。大概 2h 的时候过了这个题。

T2 发现居然是交互。这个时候脑子有点不清醒。sub 1 是直接暴力，sub 2 可以将元素任意匹配之后将问题规模减半，这样是 $\log n$ 次请求，$n-1$ 次询问。场上想过分块，然后块内暴力块间做这种两两匹配的操作，但是这种操作在元素个数很多的时候是劣的，不知道为啥当时我就止步于此了。事实上正解是在元素个数多的时候两两匹配，元素个数较少的时候再用 dp 求最优的分块方式，用询问次数换请求次数。场上拿 26pts 之后脑子里啥都没有，不知道能咋做，认为这个题困难，然后只能去看下一题了。

T3 想了半天感觉只会 $O(n^3\operatorname{polylog}(n))$，因为不知道怎么找满足两点间路径上只有一条边方向未确定的点对，所以只好每次都暴力将所有边扫一遍判断是否符合条件。写了个 $O(n^3\log n)$ 的东西，结果发现其以非常快的速度过了 $n=2000$ 的点，以为是算法在随机数据下表现优秀。这玩意正式数据也跑过了 $n=2000$。讲完题之后会宿舍想了一想，发现事实上每条边只会被找恰好一次，所以复杂度就是 $O(n^2\log n)$ 的，那就很有道理了，感觉其他 $n^3$ 过 $2000$ 的选手也有可能是复杂度没分析清楚。本来还准备打菊花的部分分，先以为直接并查集可以维护，结果发现需要求 2-sat 的最小字典序解，这玩意我会做线性但是太难写，并且好像只有 4pts，遂放弃。最后这题拿了 56pts。

Day 1 总分是 100 + 26 + 56 = 182。显然是非常低。T2 感觉很白给，但是我基本没拿分。如果是 UNR 或者 CF，别人的高分还能提示我这个题是简单题，这样大概率我是能过这个题的，可能这就是 NOI 赛制和其他赛制很大的区别。

Day 1.5

社会活动去参观三峡博物馆。我看博物馆可能看不出什么名堂，我没啥文化的。

Day 2

T1 是个很怪的东西。可以用类似辗转相除的方法判定一个二元组是否合法，但是这样做没啥前途，分析性质和打表也都没看出什么有意义的东西。可能唯一观察到的事情就是合法的二元组数量很少，并且由于我们可以为每个二元组确定唯一的前趋，直接 dfs 就可以不重不漏的生成所有合法二元组。简单卡常可以让搜索次数做到 $ans / 2$，这样就可以拿到 90pts 了。有效代码只有 10 行左右。总共花了 1h，然后弃了，再做感觉没什么意义了。

T2 感觉有点困难。T3 是图论推性质题，感觉部分分是好写的，于是决定先写 T3。

A 性质很平凡，直接缩点就行。同时有 B 和 C 简单推一点性质即可做到线性，这样想 $O(n)$ 解决 B 要做的就是找任意一个一类点，我认为这个我是会做的，而且这玩意好像是有 20 多 pts，很想写这个部分分。狂暴敲了 150 lines 发现假了。NOI 场上的 vscode 没有 timeline 功能，没法回退到代码以前的版本。这个题的代码虽然不难写但是是由巨大多 dfs 拼起来的，所以写起来极为恶心，没有版本控制更是雪上加霜，改着改着代码可能就废了。好在有一些手动备份的版本。3h 后放弃了 B 性质，30pts 跑路，比大多数人可能就是多拿了 BC 那一档分。

然后 T2 只剩一个小时不到了。想了一会儿感觉是会 $O(n^2)$ 的。写着写着觉得不对劲，好像只会 $O(n^3)$ 啊。时间实在不够了，写点分也比爆零好，所以 rush 了一个 $O(n^3)$ 的东西，拿了 15pts。感觉部分分有很多能写的但是都没时间了。

Day 2 总分是 90 + 15 + 30 = 135。

晚上去嘉年华把所有项目都玩了，还是很有意思的。还和小粉兔换了徽章。

Day 3

总分是 100 + 182 + 135 + 5 = 422。民间有说法是 Ag 线 409，那还是比较好的。

颁奖时分数线确实是 409，压线拿了 Ag。

xxy 拿下 Au，不愧是湖北队长。

这次的 NOI 毫无疑问发挥的非常差。做 NOI 2023 的题的时候我觉得我上我也行，感觉真的是有拿 Au 的希望的，但是事实上如果是场外看今年的 D1T2，我肯定认为这是送的，事实上场上又只拿到了那样的分数。

可以发现两天的 T1 和 T3 可能打的都还行，问题出在 T2 上。这可能主要是对题目难度判断以及时间分配上的问题。从今年 NOI 的情况来看，如果目标是 Au，两天的 T2 恐怕都需要通过，或者至少拿到接近满分的分数，所以 T2 是需要优先拿出一些时间来解决的。对于 D1T2 那样放在 T2 的非传统题，更好的方式可能是告诉自己这题不会太难，并且如果知道自己的思路没有前途，就先去写 T3，或者上厕所，换个脑子再回来做，直到有靠谱的想法再拿出较多的时间冲击高分。

离金牌到底有多少距离，还是有点难说的。

总之今年 NOI 是一次珍贵的体验，OI 生涯可能在此刻需要告一段落了，高二不可能像高一那样拿太多时间出来训 OI。今年能拿 Ag 是幸运的，剩下两年 all in 文化课也能有不错的前途，虽然这样有点太无趣了；但事实是，对我来说拿 Au 是需要运气加持的，NOI Au 的容错在变低，还有随机区分的题会把人创死，太多时间学 OI 也不合理，更何况我的文化课底子并不好。究竟怎么规划，可能只能走一步看一步，能够再战 NOI 2025 自然是好的。

当然从另一个角度来说，经过一年的训练，现如今我对 OI 的热情恐怕早就不及当年了。虽然拿到题目还是能够专注到题目中去，但是并没有激情像以前那样维护博客，以及高频率的参加比赛。以这样的状态，可能从一开始我就没有想过能在今年就拿下 Au。两年前我就写过有关压力的东西，恐怕现在不是压力的问题，而是动力的问题。我的未来会何去何从，我确实也不知道了。

湖北新高一目前来看没什么强力选手，不过一年的时间足够让一个努力且有天赋的人脱胎换骨，还是很期待新高一新人的表现的，感觉老登们战斗力都不是很行。也期待远处 hsy 的表现。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。