NOI2026 游记

· · 生活·游记

最后一次以 OI 选手的身份写游记，本来以为会写下一大堆东西，结果到头来却是什么都不想写了。

感觉比赛之外的东西没什么特别的，WC 算是都体验过一遍了，除了完全烂透的开幕式和社会实践。

那就着重写一写比赛的两天吧。

Day 1

早上慢悠悠走去考场，走到门口一看...手里怎么是笔试密码条？！

慌了，飞奔回宿舍。翻找了我能想到的所有地方，结果什么都没看到，魂都要吓飞了。强迫自己冷静了一下，回忆起了座位号的前三位，只有个位没想起来。

于是我当机立断，先拿着笔试密码条，以尽可能慢的速度进考场，这样已经有人坐下的座位就可以直接被排除，理想情况下我应该能直接坐到正确的座位上。

走进考场，发现可能的候选位置只有两个空座了。敲了其中一个位置的空格键，发现屏幕上的账号不是我的。赶快走到另一个座位，坐下，账号确实是我的！成功避免 -5！

开场先看了三个题，看到 T3 是长得很像 APIO T2 的交互题被吓了一下。

然后就慢慢做 T1，花了半个小时刻画出了合法集合的形态，找到了 DP 的方式。算了一下空间发现刚好超了一点，懒得滚动数组了，所以就开 vector 让空间减半了。

写写调调，大概又过了半小时拿到了 selfeval 92，最后两个点 T 掉了。测了一下大样例发现跑了整整 6s，简单卡了一下感觉不太卡的进去就先放掉了。

然后来到 T2，想了一下发现不存在一个点会走路走到传送门上，否则直接原地传送就好了。那么所有走路的点一定是包含根的连通块。

更进一步的，我们只关心所有走路的点的个数与深度和。按深度排序挨个选就能得到平方的做法。想到这里之后写了个暴力，又验证了一下起点的作用只是将答案跟起点到终点的距离取 min。

做完上面的一堆东西也只用了半小时，充裕的时间让我得以继续思考这个题。感性理解这个到根连通块的大小，太小会一直传送，太大会花半天才能走过去。那么记 f_i 是选 i 个点直接走的答案，计算一下 f_i - f_{i-1} 的值，发现分子是单调递减的，而且同一深度的点选一部分跟全选的效果是一样的。

那么我们要的就是第一个差为负数的深度。直接二分，需要解决的问题就是多次查询到 x 距离不超过 d 的点的个数，距离和。上个点分树...

我当时认为点分树查询静态问题也需要 \log^2 的时间。那么总的复杂度就变成了 \log^3，我认为这个复杂度不可能过任何多余的分数，于是当即拼上了 60 分的暴力，跑去了 T3。

PS：我赛后写了一份点分树 O(n \log^2 n+m \log n) 做法，总共花了 75 分钟，在 qoj 上通过了。而我在场上花了差不多的时间拼包，省下的时间也没有让我在 T3 得到更高的分数。

来到 T3，因为这个题跟 cake 长得特别像，我的思路一上来就被带偏了：开始思考缩短答案区间而不是缩小答案所在的集合。

我尝试了多种方向，最后决定构造一个相邻两项 gcd 互不相同的序列，乘上一个较大的质数，通过返回值除这个质数的值判断答案所在的区间。

然而这样的想法在区间缩短之后根本不成立，大脑短路的我只好将缩小后区间里的数全都扔进下一个包询问，拿到了 38（事实上按 systest 计分方式是 37）分。

最后时间还剩一个小时，我认为根本写不完 T2 的点分树，于是回头对 T1 卡常。可惜我用上浑身解数也不能让它稳定通过，最终以五次提交四次 100 一次 96 的不稳定分数结束了。

查分获得了 96+60+37=193，最终 T1 还是没能通过，在最后一个点跑了 2.538s，就比时限多 0.038s。

Day 2

提前把密码条跟其他东西装到了一起，这次没有弄丢了。

开 T1，先二分答案。考虑一个必要条件，也就是至少有足够数量的 1，起码要形成足够的段数。发现 x 段 1 最多只会分出 x+1 段 0。

发现如果有相邻的 1，只要直接选中间就不会出现 0，这样就少了一段 0。扩展一下，只要存在 11,101,1001 这样的结构，中间的 0 就会被吃掉。为了避免麻烦的分讨，我直接写了一个 DP 来做这个东西。

测一下样例，什么叫前几组全过了后几组全没过？手推了一下，发现问题出在它的 k 太小了！看了一眼部分分表格，那就是 k=2,3,5 的时候会爆了。又写了一个 O(n\log n k^2) 的暴力 DP，发现直接通过了，只跑了 0.1s，那就不管它了。此时过去了一个小时。

来到 T2，回想了一下线性从 prufer 序列还原树的方法，于是大概一个小时写出了暴力和 a \lt 1000，拿到了 36。我认为自己不可能会 D2T2 的正解，于是先跑去了 T3。

还有 3h，我期待能够编出一个 T3 的多项式做法。然而最后还是失败了，花了 2.5h 获得 n \le 8 和链的 12 分。

最后半小时，我盯着几道题的题面发呆。看着看着一个关于 D2T2 的框架在我脑中浮现出来：对右端点扫描线。区间没出现的数是一个二维的限制，可以树套树解决，区间内一些数最后出现的位置会挤掉一些位置，也就是在 01 序列上找第 k 个 0，用线段树二分处理...我似乎可以做出这个题？

然而没有时间去想更多的细节了，没有时间去写更多的代码了。比赛已经结束了。

查分获得了 100+40+12=152。T2 多过了一个数据随机的点，很神秘。

尾声

最后的结局就是这样了，445pts rk144 Ag。

这半年来我对 OI 的热情一直不怎么高，或许是早已经下意识的觉得自己做不到了。然而这一战让我清晰地看到我的上限其实是足够的，说不定在哪个世界线我就拿下了 D1T2，D2T2 和 D1T3 更高的分数，得到金牌了。

如果我还有一年的话会重新燃起斗志吧，然而我的 OI 生涯并不算长，在这里就要匆匆离去了。

再见啦，希望在将来还会有人记得，我曾经来过。

2024.03.06 —— 2026.07.24.