NOI2026 游记（终章）

· · 生活·游记

省流：5+100+(100+100+73)+(100+100+0)=578，rk42

前情提要：省选 429 分打的特别好，然后 APIO 打成区了只有 120 分，六月份在巴蜀训练，考试基本上都有不错的成绩。

Day -?

打 UNR，两天 T2 都没做出来，获得了 rk200+ 的好成绩。

然后 7.12 下午就坐飞机去青岛了，参加代码源在青岛二中的集训。然而青岛二中的宿舍条件非常撇（空调 23:00 自动断电，有很多虫子），并且这几天我还感冒了，所以在代码源的几场考试我都考的很不好。

说这几天对我 NOI 心态完全没有影响肯定是假的，好在我在 NOI 报道前几天想通了，认为像平常一样对待两场考试就行，具体最后是什么结果就不用在意了。

Day -3,-2,-1

代码源集训结束后我家长接我去吃了一顿海鲜，味道一般，然后就去住了城阳一中附近的一个酒店，这几天我本来计划看一下集训队论文的，但实际上大部分时间都在刷视频。

第三天下午就去城阳一中报道了，能明显地感受到这次的志愿者以及宿舍条件都比 WC 的时候好很多。抵达宿舍发现我和三个上海人一起住，体验到 NATO 之前的待遇了。晚上打了挺久的篮球，大概 23:00 左右睡觉了。

Day 0

上午开幕式，听到了 dzd 锐评国足。下午试机发现是 WC 的题目，大概能猜到两天题目可能都是交互格式。笔试满分没什么好说的。

吃完晚饭发现没人打球，然后就去操场跑了几圈。

晚上看了下板子和博客，睡觉前我想了特别多东西，比如如果这次拿了金牌我暑假应该干什么，或者说如果拿了银牌我就得在高三学习一整年的文化课，并且还可能辜负了大家对我的期望。但到最后我认为应该坦然面对明天的考试，不应该想任何其他东西。最终在 22:40 左右睡觉，睡眠质量挺好的。

Day 1

早上 7:50 进场，发现我可能是最后一批入场的。

8:05 开考，我发现当我真正去想题时，一切顾虑都不存在了。T1 计数题发现了毛毛虫的结构，想了个 \mathcal{O}(n^2k) 的 dp 做法。T2 推了下发现只需要求出 y 固定时所有点的期望时间的最小值，询问时回答 y 的答案和两点距离的最小值，容易做到 \mathcal{O}(n^2+q)。T3 看了下不知道是个啥东西。

先写 T1，T1 代码非常短，\mathcal{O}(n^2k) 做法跑了 2s 左右，我认为这个东西不太能卡常就没管了。T2 想到对每个 y 二分答案，然后转为求到 u 距离 \le k 的所有点的点数以及距离之和，可以直接点分树维护，复杂度是 \mathcal{O}(n\log^2n+q)。一开始先写了个整体二分，每次重新跑一次点分治并回答所有询问，这样空间是线性的但是跑了 10s+，改成点分树之后只跑了 2.5s，我认为这个时间可以稳过就没想继续优化了（实际上我在想到二分时就猜到相邻点答案差不超过 1，但写完之后又忘了)。

做完前两个题已经用了 3.5h，T3 先写了个最简单的 16 分做法，然后想着这个分可能已经够了？（实际上完全不够），所以能优化到多少分就是多少分。先看了下质数的情况发现完全不会，然后注意到这个题本质上是一次询问将答案集合划分为若干个等价类，所以可以每次随机要问哪些数，多随机几次使得所有等价类大小的最大值尽量小。随便写了个策略为，随机生成 7\sim 8 个在集合最小值和最大值之间的数，排序后给相邻两个数之间随机一个 \gcd，然后再调整每个数。每次随机 1000 次取最优解，写完后出乎意料的发现这能做到 5 次询问，总数不超过 30 次，发现有 73 分。后面又一直在调参数，然而我一直只能做到 5 次询问，所以最多也只有 73 分。

pretest：100+100+73=273

中午睡了个午觉，下午查分发现没有挂分。得知金牌线可能有 280？但我这个分至少没有拉开太大差距，所以就没管了。cdqz 其他同学好像基本都被 T3 击败了。

下午晚上几乎一直在打瓦和刷视频，然而宿舍网太烂了所以无法打匹配。

晚上得知第二天 6:20 得上车？？？成为史上最垃圾的 NOI 社会实践，晚上大概 11:30 睡的。

Day 1.5

早上 6:20 上车，中午 13:00 回学校，然而参观时间只有 1.5h 左右，其他时间要么在车上要么在晒太阳，无敌了。

下午基本上在睡觉。吃了晚饭之后跟巴蜀的同学在操场上到处转，然后又打了会儿篮球，认识了一位 CJ 的老哥。

晚上看了下板子和博客，依旧想了很多东西，因为根据前两年的经验区分金银牌的题都是 D2T2，所以认为 D2 的考试会比 D1 还要重要（实际上赛后发现真正区分金银牌的是 D1T3）。晚上还是 22:40 睡觉了，睡眠质量也还不错。

Day2

早上 6:10 醒了之后就一直睡不着了。最后还是 7:50 进场的。

8:00 开考，通读一遍感觉 T1 是可做题，T2 可能可做，T3 是我比较擅长的 n 较小的计数题，所以看起来还是比较有希望。

T1 先读错题写了个假算，然后准备先想 k 是偶数的情况，一个简单的想法是直接选 \frac k 2 个 1，但这样可能剩下段数为 k+1，所以一定是开头或末尾一段是 1，或者中间有两个相邻的 1，如果能确定这一部分只需要判断剩下的 1 个数和总数是否合法就行。开头或末尾段只需要取最短的就行，中间两个相邻的 1 只有可能是 (1,1),(1,-1,1),(1,-1,-1,1) 这些情况，不然一定有两个相邻的 1，于是会了偶数的情况。

奇数会多一些分讨，大概是开头+结尾、开头连续两段、开头一段+中间两段、结尾连续两段、结尾一段+中间连续两段、中间连续三段、中间两处连续的两段，这些都可以简单处理。然而开头或结尾连续两段的情况我有个细节没处理好导致调了很久，最后是观察 大样例才发现的。这个做法复杂度是 \mathcal{O}(n\log n)，不用特判 k\le 5 但是每次 check 的分讨会比较多。

写完 T1 已经用了 2h 了，感觉有点不妙。然后准备 T2T3 都粗略想一下，T2 先写了个暴力，然后发现可以根据 x,y 最后一次出现位置得到哪个可能是叶子，接下来只需要维护 c 表示当前有多少个叶子编号 \le x 即可。于是对于每个位置如果编号 \le x 并且是最后一次出现则看成 0 否则看成 -1，只需要找到 x 最后一次出现后 c 第一次变为 1 的位置，判断这个位置下一个是否为 y 即可。这个东西是个三维数点，大概可以用树套树维护。然后又看了下 T3，想了 20min 发现完全不会。

此时大概是 11:20，我准备剩下的时间都来冲 T2，最后有空再打 T3 暴力。T2 一个位置看作 0 的条件是 nex_i>r,a_i\le x，然后要区间查 0 的个数，按 x 扫描线之后就是单点修改，矩形查询。一开始还要用到区间中有多少个数没有出现过，所以还写了个矩形加，单点查的树套树。查某一位后第 k 个 -1 的位置如果直接二分复杂度是 \mathcal{O}(n\log^3 n) 的，但可以在第一层线段树上用线段树二分，时空复杂度都是 \mathcal{O}(n\log^2 n)。

树套树一个是线段树套线段树，一个是线段树套树状数组，树状数组我偷懒直接用的 map，一直写到了 12:10，调错又调到了 12:30，通过了所有大样例。然后我怀着激动又紧张的心情测了一发，只有 32 分？我发现 n=2\times 10^5 的点都 T 了。

这个时候差点要哭出来了，脑子里想了特别多如果拿了 Ag 会怎么样，但我立马调整了下心态，马上就缓过来了。我意识到 100+32+eps 的分数肯定不会有金，所以我选择继续去卡 T2。

我把 T2 的树状数组改成动态开点线段树，然后将两个树套树合并到一起，又改了下细节，终于在 12:47 过了所有大样例。这次又测了一发，在等待了人生中最漫长的一分钟后，pretest 显示 100 分，我做到了。

最后 10min 感觉冲不出来 T3 暴力，于是检查了下 T1T2 的代码。

pretest：100+100+0=200

出考场的时候腿都是软的，一开始都走不动路。吃饭的时候得知 T1 pretest 很弱，不知道会不会挂分，然后听说 T3 是简单题？有很多人都过了。接下来本来准备睡午觉，结果躺床上一直担心挂分或者分数线很高，所以一直没睡着。终于熬到了 15:00，查分发现没有挂分，终于，一切都尘埃落定。

过了 1h 就得知自己有 Au 了，特别兴奋地向教练和家长宣布了这件事情。然后马上就是签约环节了，最终签了清华姚班。

下午跟一群人去自习室五排打瓦了，不过一开始看一些操作给我手感看没了。晚上嘉年华还是在打瓦，中途下去听到了《光年之外》，感觉唱得还可以。

晚上因为没睡午觉所以很早就困了，熬到了 24:00 实在熬不动了就睡了。下午和晚上收到了好多人发来的祝福，非常开心。

彩蛋：中午食堂的饭菜极其难吃，我准备倒饭的时候结果有志愿者说我剩的太多所以不让我倒，这下跟 WC 坐一桌了。

Day3

早上 6 点就醒了，然后就睡不着了。去吃了个早饭又接着回来睡了，上午几乎一直在刷视频。下午闭幕式终于获得了心心念念的金牌，值得注意的是这是我打 OI 以来获得的第一枚金牌。

由于我一天也不想在城阳一中多住，所以晚上就坐飞机回成都了。

后记

关于我 OI 生涯的一些成绩，也可以在我博客里找到一些游记。

这次 NOI 无疑是我人生中一次特别的经历，这一路上的过程很曲折，我也想过很多不好的可能性，好在最终结果是好的。同时也希望所有没拿 Au 的 Oier 能坦然面对文化课，高考顺利。

这里原本可能有一些关于 OI 的锐评，但我觉得有点影响观感所以就不放了。

我认为这次我能发挥出来的一个重要原因就是我的心态一直都很好，希望大家能在面对任何事情时都保持一个良好的心态。

“生活就像，一场无止境的流浪。新患旧伤，我却更坚强，一路逆风飞翔。”