相逢是问候，分手是祝愿——NOI2025 游记

· · 生活·游记

相逢是问候，分手是祝愿——NOI2025 游记

Infomatik verbindet dich und mich, Zeit und Raum trennen dich und mich.

信息使你我相遇，时空让你我分道扬镳。

12 日和 13 日的游记是当天写的，14 至 17 号的游记是 18 号 03:57 写的。熬夜太久，现在疑似神志不清。

之后有时间可能会补充一些照片。

UPD on 7/20：略修改了一些文字。

7.12

报道日。从三亚坐飞机来杭州，飞行途中飞机出现了严重且长时间的左倾错误（物理意义上的），好在完整着陆了。

在机场拿完行李出来时发现有摄影师怼脸拍我。

机场接站处有非常气派的 NOI 宣传墙，还有很多吃的，可惜我在飞机上吃太饱了，只拿了一个酸奶状物。好不容易找到一个薅 CCF 羊毛的机会，早知道之前不吃那么多了/fn

到学校之后和若干选手换了徽章。WC 的时候已经来过龙山书院了，学校设施还是一如既往的优秀。

幸运地和三位比较熟悉的同省选手 cwm，xzk，hjh 分到了一个宿舍，这对我这种社恐是比较友好的。APIO 的时候和三位河北的同学在一个宿舍，整个比赛期间四个人说了 0 句话。

晚上打 ABC，被 F 题击败，perf 未能上 2000，但仍然是历史以来第 2 高，希望是 NOI 的好兆头。（如果这场 ABC 打的特别烂，我就会说“给 NOI 攒 rp 了”）

见到了 DengDuck 和 sk。sk 当面说要“看看我的实体”。

补充：hjh 怎么这么 p，比 pcf 还批，在宿舍里面疯狂说批话/tuu

7.13

上午是开幕式，感觉文艺表演节目都挺有趣的。dzd 主席的发言还是一如既往的深刻，具体说啥忘了，就记得“制度好”和剩饭扣一分。（之前还是五分来着）

下午笔试，5 分钟就写完了，检查了两遍，不出意外地 ak 了，感觉良好。试机的时候写了下 NOIP T2，居然一遍过编译并且一遍 AC，非常神奇。

晚上再操场跑了两圈，看了看之前的笔记，决定在 10 点之前睡觉。明天就是 Day1 了，来绍兴之前，晚上睡觉时老是想太多，真到了比赛的前一天反而没那么紧张了。希望赛时也能保持冷静，吸取省选的惨痛教训。

经过 1.5 天的观察，总结出了 hjh 同学的行动规律：

while(1) {
    int op = rand() % 3;
    if(op == 0 || op == 1) {
        说批话();
    } else {
        询问是否有人打三国杀();
        if(有人打三国杀) {
            打三国杀();
        } else {
            cout << "呃啊↗你们这么这么强别卷了别卷了我就是个菜鸡偶日子偶日子\n";
        }
    }
}

7.14(Day1)

这一天终于来了。虽然我已尽力，但还是没能发挥出最好的水平。

看到 T1 以后立即想到可以把一个点 u 拆成 d_u 个点，用 (u, p) 表示到达 u 且指针指向 p 的状态，然后在这个新图上跑 Dijkstra。这样点数为 O(n + m)，但我只能想到在点之间暴力转移，显然过不了。过了一会我把转移改成了到达某个 (u, i) 时，松弛所有的 (u, j)，这样的时间复杂度是 O(\sum_{u} d_u^2)，和上一个做法没有本质区别。我此时可能脑子已经不太清醒了，不知道怎么转化才是对的，于是只好强迫自己继续想下去，却毫无思路。此时的心态已经不太妙了，我决定先实现这个做法，手里有点分多少能缓解一下焦虑。实现的过程也并不太顺利，明明是很简单的 Dijkstra，但写了一个多小时才调出来，调完已经是 10 点整。然而诡异的事情发生了：我测了一下大样例，发现它跑得很快。然后又放到 selfEval 中测，居然直接过了。我非常震惊，然后开始怀疑是不是分析错时间复杂度了。但无论怎么想，这个做法最坏都可以被卡到 O(n^2)，只要构造一个菊花图就行。出于对做法的不信任，我输出了大样例的 \max d_u，发现只有 38，于是释怀地笑了。现在考试已经开始了 2 小时 20 分钟，我手里只有一个 T1 的假做法，最坏可以被卡到 40 分，但它却鬼使神差地通过了 pretest，此刻我非常纠结，到底要不要想出 T1 可以证明正确性的做法，还是直接看 T2 和 T3。由于心态已经略微有点崩了，我感觉不太能想出 T1 的真做法，于是狠下心来决定往后开题，并希望出题人不要变态到在 pretest 放随机数据，然后正式数据狠狠卡假做法。

本来前半场比赛已经够拉了，但后半场更是突破了下限。看了 T2 以后发现可以刻画 0 的连续段。那么先预处理一个区间能否全部变成 0，然后再进行某种 O(n^4) 的区间 dp，可以获得 30 分。对于前者，发现把一段变成 0，可以进行的操作是往左推或者往右推，于是可以枚举一个中间位置，暴力判断从两端往中间推能否变成 0。后面的 dp 大概可以乱搞一下。不过我对这个做法的正确性没什么自信，写了两个多小时，通过了样例 1 的第一问，但样例 2 死活过不去。我实际上两问都写了，但第二问全输出 0，我本想先调对第一问再调第二问，但样例 2 的 n = 200，完全不能人肉模拟，对着代码反复看了好多遍都看不出问题，也想不到思路上哪里假了，彻底红温。这个过程中我的理智人格可能还暂时清醒了一下，提醒我至少要把暴力分打了，但我看了下 T3 发现一眼没想到暴力怎么写，而对于 T2 的暴力，我的想法是如果能写出这个 O(n^4) 的做法，那么暴力分也就包含在内了，所以应该把它调出来（显然理智人格在这里输了）。然后就彻底寄了，后两题直接爆零。最后几十分钟还是强迫自己写了一下 T1 的特殊性质，这样即使正式数据卡了我的做法也还能有 60。在比赛结束前几分钟突发奇想把 T2 的代码放到 selfEval 上测了一下，发现它可以获得第一个部分分的 4 分，感觉非常幽默，于是还是交上去了，反正不能倒扣我分。因此结束时我 Day1 的分数是 [60, 100]，玉玉了。

比赛结束后到下午查分前的时间非常煎熬，因为我不知道出题人有没有卡我的这种做法。如果 100 还能力挽狂澜一下，60 的话则没有获得任何奖牌的风险。查分的路上，我一直在想，如果打开成绩单时 T1 的分数是 60 分，我该怎么面对。幸运的是这个做法没有被卡，打开 HI-05.pdf 的那一刻发现 T1 是 100 分，终于松了口气。然后 T2 获得了高贵的 2 分，比上午还少了一半，这样总分就是 100 + 2 + 0 = 102。不过这也并没有什么好高兴的，只是从彻底死了变成了 ICU。问了一下别人的成绩，发现海南 9 人中有 7 人比我高（除了 gcx 是 173，其他人基本上都在 110~140 分段），更加玉玉了。

讲题的过程中突然发现，T1 我的做法转移改成只从 (u, i) 转移到 (u, i \pm 1) 就彻底对了，几乎不用改什么代码，我赛时怎么会差这么简单的一步没想到？？？然后 T2 和 T3 加起来有 36 分简单的部分分，完全没拿到。

寄。

7.15

上午社会实践。去了绍兴科技馆和绍兴城市展览馆。感觉前者并没有什么科技，后者看的东西可能还多一点，了解到了一些关于绍兴的知识。不管怎么说，我觉得出去走走总是没错的。

下午沉浸在 Day1 的悲伤中，完全不想做题和看笔记，狠狠开摆，和舍友联机 MC。

7.16(Day 2)

吸取 Day1 的惨痛教训，决定今天一定要稳稳打。上来先把 T1 暴力打了，获得 30 分。然后观察到一个串保持不变的充要条件为，对于所有的 1，后面跟着的两个字符必须相同。不过还是没什么思路。于是打表观察，瞪了一段时间之后发现第一个 110 子串会不停向后推，因此只要找到第一个 110 子串的位置就行，稍微证了一下感觉很对，写了个基于此的暴力，发现过不去样例 1。发现少考虑了存在 101 字串的情况，此时答案至少为 1，同样稍微证了一下，感觉挺对，加上这个判断就对了，那么单次询问是 O(n) 的，拼上特殊性质可以获得 65 分，此时距考试开始过去了 1 小时 20 分钟。然后想想怎么快速修改。几乎不用任何思考，我就知道怎么做了：线段树。此时我感到有一种宿命感，线段树是我最熟悉的数据结构，终于有一天在 NOI 赛场上把它当作题目的主要部分来使用。我迅速在纸上写下要维护什么东西：首先要维护一个段内有没有 101 和 110 子串，以及第一个 110 子串出现的位置。由于有翻转操作，还要对应地维护有没有 010 和 001 字串，以及第一个 001 子串出现的位置。为了合并信息，对于所有长度为 1 和 2 的 01 串 s，需要维护每个段是否存在前缀或后缀 s。细节可能有点多，但还可以接受。那么就开写！这可能是我这辈子写数据结构最认真的一次，我记得当时我把背挺直了，严肃地盯着屏幕写代码，30 分钟就把 5k 200 多行的代码写完了。遗憾的是还是有若干弱智错误，又调了大约半个小时，通过了 pretest，此时是 2 小时 20 分钟。

虽然赛后大家都觉得这题比较水，但我通过了这道题后还是比较开心的。虽然可以预知这题难度不高，但这是对普遍的 NOI 选手而言，客观来讲这题从观察性质到实现细节都有一定难度，我觉得我能写出来还是挺好的。不过鉴于 Day2 比赛还剩两个多小时，我尽力让自己忘掉 T1 去看后面的题，并提醒自己至少要打满暴力。

看完 T2 后发现自己居然连最低档的暴力都不会写，寄。只好看 T3，一开始以为能不放技能就不放技能，但如果是这样的话这题显然就是弱智题了，然后我也很快发现这确实是错的。尝试分析了一些性质无果，只会比较暴力的 dp。大概是二分 k 判定是否可行，判定可行性使用 dp，记 f(i, j, k) 表示到第 i 轮，使用了 j 次技能，上次使用技能在 k（k \in {0, 1, 2}）之前，是否可行。状态数为 O(n^2)，转移 O(1)，于是总时间复杂度是 O(qn^2 \log n)，可以获得 10 分。观察数据范围发现如果能把 dp 的时间复杂度优化到 O(n \log n) 将会多得很多分，然后尝试优化 dp 的状态，但始终感觉要有一个 O(n) 的状态，否则无法表示当前两种手牌的数量，于是倒闭了。

回来看 T2。想了半天才会了 n = 4，大概是枚举 \{0, 1, \cdots, 2^{n} - 1\} 子集的子集，时间复杂度 O(3^{2^n})，别的彻底不会，获得了 8 分。此时还剩 40 分钟，我在两道题之间随机游走，但感觉无法获得任何分数了。最后 15 分钟时还是不会任何东西，于是彻底摆了。今天该拿的分已经拿完了，Day1 考的再烂也无法改变了，结果只能听天由命了。（PS：比赛结束后交流发现 T2 其实还有 8 分比较好拿）

出场之后发现今天确实没那么完蛋，我和 cwm 的分数分布一模一样，xzk 多拿了 T2 的 8 分，但 hjh 好像有点倒闭，随机 WA 了 T1 的三个点，并且后两题没看。最后也确实没挂分，Day2 分数是海南第二名。不过由于 Day1 太拉跨，总分还是很倒闭，只有

0(A 类加分) + 100 + 100 + 2 + 0 + 100 + 8 + 10 = 320

大概是海南第五（而且注意到前四名都有 A 类加分而我没有，原因是省选也很倒闭）。然后意识到一个可怕的可能，就是我们宿舍其他人都有奖牌，就我没有。我超，别。

晚上有篝火晚会，感觉由于主持人对中学生喜欢的歌曲不够了解导致总体上有点尬，不过我对这些活动一向比较宽容，反正大家乐呵乐呵得了吧。反正我是戴了一个粉色恶魔头饰跟 adolphshi 合了张照

这时候成绩单也公布了，但是没有标明选手类别，所以分数线还是未知。舍友的教练发送了一个只含 AB 类选手的成绩单和分数线预测，这个预测中我是铜牌倒数第四名。但它没有考虑 C 类，所以还是不太准，不过考虑到 C 类人很少，所以理论上应该不会差太多。感觉大概率有奖牌，提前开个香槟。然后和舍友打 MC。

7.17

早上是“我与 NOI”文艺汇演。大家的表演热情都很高，氛围也很好，基本上每个节目的掌声都很热烈。同学们都多才多艺，表演项目有唱歌、乐器演奏、舞蹈和演讲，有的同学唱歌很牛，主唱太拼命了.jpg。为什么我不会唱歌也不会乐器，呜呜呜。我想着要是下次还能来，我也要报一个节目，但我怎么没有下次了？唯一的遗憾大概是没有 文艺汇演传统节目《蜂鸟》和《白鸟过河滩》了，据分析是大家都觉得别人会报，所以都没报。结束之后发现可以找 dzd 合照，然后我就跟 DengDuck 还有 dzd 合了一张照，巴结大手子.jpg

中午吃饭的时候看到了下午闭幕式的座位表，由于座位表是按奖牌划分的，所以这也就相当于公布了获奖名单。观察到自己出现在铜牌区里，于是松了口气。继续观察发现我认识的一位同学只比我低 2 分，正式选手中只比我低一名，但是没有奖牌。也就是说我是 Cu 最后一名？那这真是太极限了。

下午就是闭幕式了。之前参加大型比赛的闭幕式还是在 WC 和 APIO，但这两个比赛都铁了，闭幕式的时候看着大家都有牌，我只能看着，感觉很玉玉。这次终于有牌了，虽然只是铜牌，但对于我也意味着足够多了。

这是我第一次来 NOI，却也是最后一次。人生中唯一一次 NOI，经历了那么多事，却好像也只是弹指一挥间，不禁有点恍惚。这几天里我与很多同学交换了徽章，来之前订了 30 个，本以为很难换完，但最后只剩两个，差点不够用。换到了海南省所有订徽章同学的徽章，人大附中大多数同学的徽章，叉叉的徽章，还有全国各地的其他许多同学的徽章，NOI 的社交活动也算圆满了。我很珍惜和全国那么多有相同志趣的同学在一起的时光，尽管这个时光是短暂的，我们并不能打一辈子 NOI，但我永远不会忘记这一段时光。

出生在一个教育资源比较弱的省份，我接触到 OI 其实非常偶然。在初中时我其实并没有很投入地学 OI，到了高中，或许是某种心气的驱使，我才把很多的精力投入到 OI 上。这当然引起了身边许多人的不理解，班主任，年级组长都十分反对，但我还是走下去了。高二下学期停了一整个学期的课，我能想象到许多同学及老师对这种决定的不理解，有人或许还会认为我是打了半年的游戏。最后也没有什么奇迹发生，只得到了一个铜牌，不能强基，对升学没有任何用处。但我仍然不后悔选择了 OI，不后悔能领略到算法科学的美妙，能和全国的 OIer 们交流、学习、同台竞技。尽管我在 OI 的舞台上只是一个水平非常普通的无名之辈，但 OI 仍把它的全部魅力展示于我。现在这个故事要告一段落了，算法竞赛，有缘再会。

2025 年 7 月 12 日至 7 月 18 日

绍兴一中龙山书院