[游记] NOI2024 游记

观前提示

游记是最后一天写的。

Day -3

参加了这一年中打过最烂的 NOI 模拟赛，打的稀烂。

Day -2

参加了一场纯娱乐的 NOI 模拟赛，打得不错。

Day -1

进校。欢歌载舞，交换徽章，共同庆祝。

室友是浙江队长和浙江副队长，上压力了，但是寝室只有三个人好评。

在签到处签署承诺书的时候要求“认同 CCF 价值观”，这下这下了。

Day 0

开幕式！

育才的节目比去年和前年都要唐氏，音乐剧疑似 AI 生成作曲。

然后有一些 d*d 的抽象发言，令人感叹。报告厅二楼没有网。

笔试！

首先是今年的题目从 NOIP2021 快进到 NOIP2023 了。

然后是一个非常抽象的数据残留：部分选手在笔试开始后登录网页时，发现已经存在被提交的答案，并且部分选手（我）得到的答案有错，笔试延迟15分钟开始，题目没有变化。 我的推测是选手们拿到了去年相同编号选手的答案……？毕竟22~24的笔试题目除了“今年是第一届NOI”是完全一致的。

显然最后笔试获得了满分，当前总分 5+100=105。

考前又到了不知道看什么阶段，这次特别去看了一些容易写错的板子（费用流，Tarjan，Manacher），然后重新读了省选前的 Reminder。

倒不如说在带有一定的节日活动氛围的 NOI 校园内，或许是有“Ag 也不是世界的结束”给自己的安慰，我的情绪没有省选之前这么糟糕，只有少量的焦虑症状。

在一番阅读之后，我发现我做的最糟的一条是：

• 在比赛前，你不应该思考其他人，包括你所认识或熟悉的选手的发挥，不要揣摩 XXX 能不能过这个题，不要揣摩做不出这道题目该怎么办。考场不是给你写回忆录的地方，请尊重你在漫长的训练中换来参加考试的机会。

嗯……确实吧，做不出题导致的焦虑会让我的思绪飘到和做题无关的事情上，而它们显然是不会带来收益的。或许在这些事情上浪费的时间，可以是某些比赛的胜负手哦？

晚上宿舍仍然是十点查寝十点半熄灯，但是九点五十几乎已经没有灯亮着了，糟糕的氛围立刻把我包围：仅仅十个小时之后，对自己的考验就会开始了啊。

所幸进校之后参加的一些活动让我的精力有所损失，所以入睡会简单一些吧……？

Day 1

第一比赛日！

果然比赛前一天失眠了，虽然准时睡着但是半夜醒了三次，最后在五点钟的时候彻底睡不着，听了一会歌六点半爬起来了。

然后考前头晕恶心肚子疼轮番上……焦虑症状拉满了。

但是不管是啥症状总还是要考的，还是早早走到体育馆门口开始排队。

八点，从文件袋里抽出试卷，怎么有交互题？预测试点是什么东西？这真是 NOI？

开始从前到后阅读题面，set 是一个判集合是否本质相同的题，看起来有点像哈希，但还不知道怎么写比较对，想了十分钟没有思路，跳题。

richest 是一个交互题，前 15 分是完全白给的，后面的分数看起来有点玄学？得分的第一梯度取决于询问轮数，然后才开始卡询问次数。一个简单的 20 轮 n-1 次确定的方法就是直接二分，1 轮 \frac{n(n-1)}{2} 次确定的方法就是直接两两问一次。tree 是一个给边定向最小化字典序满足给定限制的树上问题，看起来没有简单的分数。

一个结合它们的策略是做几轮前面的再做一轮后面的，大概可以获得 40\~50 分。

如果这一场很难的话，这个分数或许也可以接受？于是我又回去看 set，想到了扫描线维护元素前后缀，通过前后缀哈希值来判相等的做法，写了发现可以过大样例，但是过不了预测试中的 m=5 数据。而看起来预测试的数据范围和正式测试的是完全一致的，如果是同一个 generator 可以看作是类似 IOI 赛制？

但是做法还是错的！所以还是要想一个靠谱的做法……反例很好找，[\{1\},\{2\},\{12\},\{1\},\{2\}]\neq [\{1\},\{2\},\{12\},\{2\},\{1\}] 就是一组简单的反例，但是做法似乎没法修复？

这个时候已经过去 2 小时了，我居然在 NOI Day1 只能获得 100 分？其实这个时候心态是比较不好的，但是我让自己牢记自己考前做的话，思考了一下之后还是决定先思考 set。在上了个厕所之后，我思考到了可以维护所有值出现位置集合的可重集，并判断它们是否相等。

那么区间查询可以直接莫队，给每个位置随机赋权维护可重集就可以啦！时间复杂度 O(n\sqrt q)，但是常数有点大……？最后发现只能获得 90 分，太变态了！但是 90 分也可以接受吧，先看看后面的题……

首先想到的是再对 richest 自己的做法改进。一个更“结合”的策略是考虑每次分组，构造若干个大小为 B 的团，n 大的时候 B 小，反之亦然，手玩可以获得 60~70 分。

我想到的构造策略是分成若干个大小为 B 的团，剩下的全分到一组，这样的策略并不多，可以直接实现一个 DP，实现之后可以获得 82 分。82 分是不是也可以接受呢……毕竟比赛已经过去 3 小时了，我根本还没有对最后一个题有进一步的思考，是该看最后一题了吧？

可是 tree 作为当天的最后一题怎么可能很简单……投入半个小时之后根本想不出任何多项式复杂度的做法，唯一有救的是性质 B 和 n\le 15，加起来只有 24 分。看着庞大的部分分表格，我还是决定继续思考，不过这时上厕所的时候我突然想到 set 的答案具有单调性：对于一个左端点，合法的右端点是一个前缀，可以双指针维护！

这个性质改改是非常快速的，所以我在 3.5 小时的时候终于通过了 set，得分来到了 206。在对当时的 richest 做法端详一番后，我决定全力冲刺 tree。可是想到一个多项式做法谈何容易！写满了整整两张草稿纸的策略还是以失败告终，迫于时间压力需要开始实现平凡的暴力分，这一天的比赛就要这样了吗……

不！在最后 30 分钟，我意识到我有一个没有编写的特殊性质 A，这个性质中可以注意到，合法的解当且仅当对于边进行二染色。求出特殊性质的最优性是显然的，但是这类策略带来的强合法性是我没有注意到的！

于是我们每次只考虑唯一边，即只有一条边未被确定但当前不合法的边，这样可以唯一确定这条边。而如果没有这样的边就可以使用性质 A 中的二染色，所以我们可以在 O(n^2) 的复杂度内判断一个局面是否合法，总时间复杂度 O(n^3)，可以多获得很多分数。

可是比赛临近尾声，我努力让颤抖着的手敲下稍稍有些复杂的模拟代码，与剩下的 Subtask 拼在一起，组成一个 250 行的巨型代码……

12:58，距离结束还有两分钟时，我的代码通过了编译。没有时间调试，直接打开 selfEval，运行预测试，成败在此一举……64 分！64 分！我不仅没有写错，较小的常数还让我能够直接通过 n\le 2000 的子任务，虽然只是 pretest，但说不定正式数据同样不会专门卡选手的 TLE 呢？

出场时，我的分数是 100+82+[48,64]=[230,246]。经过一些交流，分数并不是很高：richest 我的做法和满分做法只差了可以选择若干点不参与合并所带来的 O(1) 次操作，而 tree 我的做法套上一些数据结构来快速寻找这样的边就可以通过。大众分大概是 100+100+64=264，而我的分数差不多在队线上。

查分，最后还是通过了 n\le 2000，分数定格在 100+82+64=246，至少第一天没有失误，是一个可以接受的分数。但是大家的分数非常接近，在第二场考试中不能掉以轻心。

Day 1.5

社会活动！

我们被分到了下午的组，于是上午就摸了一会鱼。

然后在走出校门的时候摔了一跤成功磕破膝盖，真倒霉……

不幸中的万幸是没有伤到骨头，碘伏之后注意保养即可。

社会活动是参观一个闷热，无趣，枯燥的博物馆，显然没有什么人享受。

还有一些同学随机获得了中暑 Debuff，这下真成身体素质竞赛了。

在第二场考试之前，我自信地没有再复习模板，而是直接提早睡觉时间。开考前过度焦虑的氛围在经过一场考试之后逐渐消失，我也找到了属于我的做题节奏。

这次，会是我的舞台吗……？

（擦伤之后洗澡进水真的很痛！大家一定要记得做好防水措施和消毒措施！）

Day 2

第二比赛日！

果然比赛前一天睡的好多了，一觉睡到五点半然后睡不着了，听了会歌六点半爬起来了。

虽然睡好了，但是考前的焦虑症状并未缓解几分，紧张与兴奋交织的感觉仍在驱使着我。

八点，从文件袋里抽出试卷，三个传统题？这下看懂了！

开始从前到后阅读题面，fraction 是个纯种数学题先跳过，mountain 看起来是个数据结构题也跳过，graphee 是个纯种图论题，这都是些啥……

那还是按照顺序想，fraction 是个和斐波那契，\gcd 类似的一个操作过程，推了很久性质并没有找到什么好的结论，但是在比赛开始 30 分钟后以外地发现，大样例的答案竟然很小！

最开始也没有发现答案很小有什么用，直到最后发现数的生成过程是唯一的，直接写爆搜就可以获得 85 分，卡了一卡可以获得 90 分。这就是非常可以接受的分数，可以直接扔了。

然后开始看又爱又恨的数据结构题 mountain，写完 O(n^2) 暴力之后想到的做法有两个：自顶向下直接计算，或者自底向上类似线段树合并计算。我选择了思考更加简单的前者，然后先套特殊性质：两个奇怪的性质 l_i=r_i 和 h_i=0 退化的有点多，链的性质可能更加接近本质一些。

先想了 cdq 分治，但是复杂度完全不对。又想了离线扫描线套树剖，但是一条链实际上要运用所有子树的信息。最后尝试了一下转置维度，从更新 f_i 变成用 f_i 更新子树，这个奏效了！

在这个做法中，如果我们按照深度进行扫描线，就只需要编写树上的历史和线段树，而这看起来并没有那么难写。于是我还是选择了稳妥的方法：先将数据结构的部分替换为暴力保证正确性，再上数据结构来做到正确的复杂度。

一行行代码从我的指缝中倾泻而出，写数据结构最美妙的时刻不过如此。解法的内容长度很多，但是细节却较为简单，于是只剩下用正确的逻辑编写一份代码。1.5 小时的时候，我的暴力代码通过了样例，2 小时的时候，我的数据结构版本通过了预测试。

或许这就是一直训练数据结构和代码能力的回报吧……作为一个数据结构题，我几乎没有调试就让程序执行了预期的操作，这也是我写数据结构最爽的一次。

唯一不是很爽的是我写了树链剖分，发现如果用力卡我可能可以卡到 4 秒，但我不想写全局平衡二叉树。于是我开始用力卡一些简单的常数，最后卡到 2.5 秒之后开始赌数据不会专门这么造才放掉。

于是策略看起来非常简单了：在 graphee 拿到尽可能多的分数。照例先尝试投入一些对题目本身的思考，但是以失败告终了。然后考虑逐个思考特殊性质来找每一类点的性质。

性质 A 是可以到达所有点的点集……这个一遍 Tarjan 就可以求出来，写写写，用了 20 分钟。

性质 B 是考虑每个点 DFS 树上是否只存在树边和返祖边……这个至少可以做到 O(n^2)，写写写，用了 20 分钟。

性质 BC 是考虑一个点需要走到它在 DFS 树上的祖先，所以要考虑子树内返祖边的形态，写写写，用了 20 分钟。

此时已经过去了 3.5 小时，然后我的选择有去做性质 B 的 O(n) 和去做性质 C 的 O(n)。我尝试用随机化方法找到一个一类点做前者，但是失败了，我又尝试进一步枚举 DFS 树形态去做后者，但是失败了，和大样例总是差几个位置。

还有 30 分钟，我最后还是决定咸鱼，去打最低档的 O(n^22^m)。但就在打的过程中，我突然发现 fraction 中第 18 个测试点和第 19 个测试点中 n 的范围是一致的，可以用一些方法让时间复杂度之和 \min(n,m) 挂钩，于是改了改在 fraction 获得了 95 分，分数来到了 95+100+35=230。

12:57，我再次检查了所有 Subtask 的组合，确认了三分代码都是我认为正确的代码。

这，就是我所能交出的答卷了啊。

从这一场来看，我最后 3 小时并没有获得很多分数，因为 graphee 确实非常有难度，我对于这类图论题的感觉也因为缺乏联系而并不是很精确。但考场上的我也只能相信大家都不会做，自己拿 35 分已经足够成功。

考试结束的指令响起。收卷的几分钟里，我又不断凝视着我的电脑。无论结果如何，一切都已经尘埃落定了。

这就是我的结局了啊。

查分，此时唯一能阻挡我的就是我把自己提交的代码删了，但这并没有发生，我也没有挂分，最后还是稳稳拿下了 95+100+35=230，是一个当场就知道自己集训队的分。

五年的努力在此刻凝结为了一块奖牌，这究竟是我只存在幻想中的愿望，还是日夜期望着的结局？

我不知道。金牌后的感觉是奇妙的，是游离于现实和幻梦之中的。体育馆里有笑声，有哭声，似乎成了人类悲欢最不相通的地方。

我笑了笑，然后又回归了沉默。我只是沉默着，从里到外一圈一圈地游走。

或许是一直占据我生活绝对众数的部分被忽然抽离后，我没法适应吧。没有之前猜测的难以置信和欣喜若狂，一种空虚与茫然一直盘旋在我脑边。

这是一个阶段的结束，也是下一个阶段的开始，但在此之前，先享受属于我的胜利吧。

一些题解

数字是考场分数，括号是题解对应得分。

• D1T1 set 100

考虑每个数 x 出现的位置集合 S_x，我们注意到两个序列可以通过将元素乘置换得到当且仅当两个排列的所有 S_x 组成的可重集相同。判断两个集合相等可以使用哈希，给每个位置赋一个 \{0,1\}^{64} 的随机权值，一个集合的权值就是所有位置的值的异或和。

这样两个不同集合的权值相等的概率显然是 \frac{1}{2^{64}}，可以近似地认为所有区间的权值两两不同，开一个 unordered_map 即可。直接上莫队做是 O(n\sqrt m) 的，可以获得一些分数。

考虑一个事实，让一个大区间满足条件比让包含它的小区间满足条件严格难。

也就是说，对于每个 l，存在最大的 r 满足区间 [l,t] 合法当且仅当 t\in [l,r]，且 r 随 l 递增是单调增的。这样可以双指针计算，时间复杂度即可降低到 O(n)。

• D1T2 richest 82(100)

注意到每次询问的信息是团时可以去除最多的可能，因此我们一定将点集划分成若干个团，最后团的数量作为这一轮删除的结果。

根据小学奥数，我们会发现让每个团的大小尽可能接近是优的，所以可以做一个 DP，我们就会有 f_{x,y} 代表 x 轮确定 y 个数中最大值的最小步数，这样是 O(n^2) 的，你可以通过跑足够久，或者决策单调性，或者手动限制取值范围来求出最优方案。

• D1T3 tree 64(100)

考察 A 性质，我们发现一个事实：如果不存在长度为 1 的路径，将边进行二染色之后显然存在一组解。证明是简单的，考虑相邻的边至少有一条不符合要求即可。

因此我们可以得到一个多项式复杂度的判定算法：不断确定长度为 1 的路径的边的方向并合并该边的端点，直到出现矛盾或存在一组解。直接逐位判断答案是 O(n^2m) 的。

容易发现根据我们的判定规则，在不存在长度为 1 的路径时，由于将每条边都取反不影响合法性，所以显然将任意一条边取任意方向后仍然存在解。所以我们可以考虑一边确定边的方向，一边寻找长度为 1 的路径。

一个直接的想法是对树进行点分治然后做折半警报器 Trick，时间复杂度为 O(n\log n+m\log^2 n)。

• D2T1 fraction 95(100)

因为可以取倒数，所以我们可以用一个二元组 (x,y) 代表分子和分母，规则可以重写如下：

• 如果 (x,y) 合法，那么 (2y+x,y) 合法。
• 如果 (x,y) 合法，那么 (x,2x+y) 合法。

经过简单的观察可以找到判定一个二元组是否合法的方法：将两个数做辗转相除法的过程写下来，如果到 (0,1) 前每一步的商都是偶数则合法，反之则不合法。

上述证明同样说明了一个数只有一种被构造的方式，所以我们可以直接搜索出所有的二元组，只需要将 (x,y) 转移到 (2ty+x,y) 即可。时间复杂度 O(\text{answer})。

正解并没有什么本质的新观察，只是考虑将第一步展开：将 k 作为参数搜索所有的 (ak+b,ck+d)。此时很多状态都被合并，一个二元组也只需要考虑合法的 k 的个数即可。时间复杂度未知，但是可以通过。

• D2T2 mountain 100

简单的观察是每次跳跃到的点显然都是比到达过的所有点还浅的。

考虑从上到下求出 DP 值。在求出一个点 x 的路径数 f_x 之后更新所有下一次跳跃到 x 的方案数。先不考虑滑落，那么所有能到 x 并且到 x 不会违反 h_i 的点都会被更新一次。而如果可以滑落，那么通过可以不违反 h_i 到达 x 的所有 y 都可以被更新。

因为我们可以扫描线维护每个点被更新的次数，先从小到大枚举深度，那么贡献的部分就是历史和线段树，一次区间贡献在 d_i-r_i 处加入，d_i-l_i 处移除。加了 h_i 其实是类似的，只不过有些点会直接移除我们考虑的树之内，考虑也是简单的。

如果你使用树链剖分维护树上区间历史和是 O(n\log^2 n)，全局平衡二叉树可以做到 O(n\log n)。

• D2T3 graphee 35

这题只写了暴力，对不起。

测试点 2,7：能到所有点的就是一类点，求出拓扑序最小的强连通分量即可。

测试点 3,4：直接求出每个点的一棵 DFS 树，点是一类点当且仅当树上仅有返祖边。

测试点 1：先爆搜出所有一类点。

考虑 m\le 20 的情况，对于每个边的子集重新搜一类点，将新的一类点归为二类点即可。

测试点 8,9：先求出一类点的一棵 DFS 树，一个剩余的点可以成为一类点当且仅当其子树内恰有一条比它浅的返祖边（否则它的父亲有两种走过去的方法），此时世界线收束。