NOI 2026 退役记

· · 生活·游记

Day 1

开场很快会了 T1 时间复杂度为 \Theta(nmk)、空间复杂度为 \Theta(m^2 k) 的做法，想了想发现交换一下转移顺序就可以把空间复杂度优化至 \Theta(m^2)。写 T1 的过程中假了两次，一次没有处理明白独立集个数为 1 的情况，一次把树判成了森林。大概在 1h 左右通过了大样例，随便卡了卡常就过了。

接下来做 T2，很快意识到只有以 y 为一个端点且 不包含 x 的 链 是有用的，其他的点权值都是 -1。写完暴力发现假了，正确的结论是只有以 y 为根且 不包含 x 的 树 是有用的。于是我又花了很久来修正暴力，最后大约在 2h 左右获得了 T2 的 40 分。

考虑优化。我很快猜到答案是单谷的，但我证明竟然是用 作差然后通分 来证的。于是直接使用二分套点分树即可做到 \Theta(n \log n + q \log^2 n)，但是接下来优化的方向我就完全没有头绪了。我首先发现由于有 不包含 x 的限制，这个二分无法去掉，然后这个二分也不能像线段树上二分那样放进点分治里面。那么看起来唯一可行的优化办法是使用更优的数据结构代替点分治。我尝试了很久使用长链剖分或者换根来优化复杂度，但是最终都失败了。

此时时间来到了 3h，我发现我已经浪费了 1h 在 T2 上，但我仍然只会 \Theta(n \log n + q \log^2 n)，再不开写就来不及了。在整理思路的过程中我开始重新审视这个分式，我终于意识到答案单谷的本质是不断向单调不减的深度去逼近。于是这个 不包含 x 的限制显然是可以去掉的，答案只和 y 有关，但由于时间已经比较紧了，我并没有继续往下想。我大概在 4h 左右通过了大样例，但是被卡成了 70 分，发现最慢的点只跑了 4s，于是把二分的上界换成 \sqrt{2n} 就擦着时限有惊无险地通过了。

来看 T3，此时还剩 1h。但由于 T3 是我并不擅长的构造，我蠕动了 0.5h 才发现可以使用 1, 2, 3, \cdots, 35 来获得 Sub 1 的 10 分。又过了 15 min 我意识到要想过得更多的分，那么必须要让相邻两个数的 \gcd 尽可能不同。那么这个东西显然可以外面套一层 1, 2, 4, \cdots, 2^{11} = 2048 来优化，稍微均衡一下可以变成 128, 128 \times 1.5, 128 \times 1.5^2, \cdots, 128 \times 1.5^7 = 2187，但是我直到比赛结束都没有写完这个优化。

100 + 100 + 16，复评的时候发现如果把这个构造写完应当可以获得 23 分。

后来听说 T3 的大众分达到了 90 分，并且听说 T3 直接构造 1 \times 2, 2 \times 3, 3 \times 4, \cdots 就可以获得 38 分，将其分层并调一下参就可以获得 90 分。没有人类了。算了，我本来就不会构造。

Day 2

开场发现 T1 是中位数题，使用二分转 01 的 trick 并在 check 的时候贪心就做完了。写的时候发现贪心是假的于是换成了 DP。大概在 40 min 的时候写完了，但是发现被 k = 2, 3, 5 的情况卡掉了，获得了 45 分。

这个时候有两种选择，一种是给 DP 加一个维度（或者换维），另一种是使用分讨一亿种情况把 k = 2, 3, 5 判掉。在犹豫了一段时间后，出于常数的原因我选择了后者。本着每 WA 一次大样例就加一种特判的原则，在大概 1.5h 左右通过了 pretest。

然后来做 T2，直接对着 prufer 序列还原的过程模拟是不可取的，但是发现如果继续使用转 01 的 trick，把 \leq x 的数视作 1，把 > x 的数视作 0 就可以得到一个形式比较好的刻画。在大概 2h 左右写完了这种刻画的暴力并获得了 20 分。

考虑优化，可以使用莫队做到大概 \Theta(n \sqrt{n} \log n + q \log^2 n) 的复杂度（没有仔细分析），但这样显然是无法通过的。经过一段时间的思考，我发现本质是在 P4396 [AHOI2013] 作业 外面套了一层二分。又思考了一段时间，我大致明白了使用整体二分 + 扫描线做到 \Theta(n \log^2 n + q \log^2 n) 的方法。

但此时我突然发现之前的暴力有一个地方写错了，但是它竟然神奇地通过了 pretest。我开始紧急修改之前的暴力，发现改完之后就无法通过大样例了。在又调了大概 0.5h 后，我发现之前的思路有两个地方没想清楚，但它们合在一起竟然阴差阳错地撞对了。

此时时间已经来到了 3h，我发现我又成功浪费了 1h 在这个 T2 上。于是我开始紧急冲刺，大约在 3.5h 通过了 T2。

接下来还有 1.5h 做 T3，我只需要在 T3 获得 40 多分就可以翻盘。会有奇迹吗？

事实证明是没有的。我狂冲了 1h 特殊性质 B 的树形 DP，但是发现根本转移不明白，最后发现就连指数级暴力都需要结合树形 DP 才能通过，但是已经没有时间了。大势已去。

100 + 100 + 4，复评的时候发现 T1 竟然还挂了 5 分，变成了 95 + 100 + 4。

5 + 100 + (100 + 100 + 16) + (95 + 100 + 4) = 520，Ag。

我退役了。

一些想说的话

首先是关于 OI。在我的认知中，OI 考察的内容应当是应当是思维方式 + trick 的结合。而这当中，思维方式的比重应当远高于 trick，或者说 trick 只是对思维方式的补充，因为通过自身的思维方式可以独立发明出一些 trick，但反之，知道更多的 trick 并不能自发地促使思维方式发生质变。在这种意义下，“天赋”的含义就变成了一个人与生俱来的思维方式，而 OI 训练的根本目的，就是调整自身的思维方式，使得自己能够独立地想出更多的 trick。

说回我自己。我在调整思维方式方面，可以说做得相当失败——因为我根本不知道，思维方式具体指的是什么，以及如何调整。在我平时做题的时候，对于我擅长的类型，我做题的时候就有一股非常强烈的感受；反之，对于我不擅长的类型（比如数据结构），我通常并没有任何感受，甚至连从哪方面下手都不知道。在一年前我遇到过很多道猫树分治的板子题，但我无一例外地都被创飞；我尝试去感受它是如何被想到的，可能有一些收获，但总是会在下一次遇到的时候被打回原形。于是我的解决方法是，遇到某个相关的结构时就来枚举一下做法，看能不能套上去；在这种思维方式下，我成功学习了猫树分治、点分治、长剖、容斥等算法。但事后看来这根本不能算对思维方式的调整，因为我总会在遇到一些题目时，要么忘记去枚举这些算法，要么没有找到正确的方法把它们套在题目上，要么光顾着想怎么去套用而漏掉一些关键的性质，NOI 2026 D1T2 就是一个极好的例子。

至于这次 NOI，我看起来是输在了 Day 1 上，但这真的是因为我“状态不好”“缺乏策略”“缺乏大赛经验”“运气差”而导致“没有发挥出水平”吗？如果我没有去思考 T2 的单 \log 做法，而是在不到 3h 的时候就通过 T2（虽然这好像也不太可能），转而思考 T3，那么我也许有机会在 T3 获得非平凡的分数——因为联考中真的存在交互题枚举了两个小时枚举出做法的经历。但是话说回来，我根本不知道做交互和构造正确的思维方式是什么，对非传统题也没有任何感受，并且 trick 积累得也并不多，唯一的做题方法就是在脑子里随机枚举做法，因此能否想出来全看我场上的运气。因此我无论如何都无法理解，为什么有些人非常擅长做这种题，为什么我的同学看到题就能马上反应出 1 \times 2, 2 \times 3, 3 \times 4, \cdots 的构造方法。从这一点上来看，我的思维方式还和正确的思维方式存在很大的差距，因此我可以说是死得心服口服。

牢骚就发到这里，接下来就是高三的文化课学习了。我希望文化课不要成为我的累赘，希望这段经历能够有一个圆满的结局。

再见。