NOIP2024 游记

花开于尘世梦乡，何不着不遗余力去绽放。

写于赛前

不觉间，又是清秋至。

从去年 12 月到现在，我参加了那么多比赛，认识了那么多人，取得了那么多并不显眼却令我满意的成绩。一年过去，平衡树还是没有完全学懂，但是图论和 DP 也还是强了些吧。至少现在的我不会再因为有不懂的算法而痛失分数，至少现在的我可以自信地走进 NOIP 的赛场，而不是以体验者的身份看着 AK 虐全场的大佬们望眼欲穿。

每到比赛前就会无比焦虑。模拟赛打得不好时，总是怅然若失；打的好时，或觉得自己已无限接近于省队，或以“这次别人没发挥好”为理由，在心中飘忽不定的天平上又加上几颗沉重的砝码。也许这就是 OIer 共有的焦虑感。怎么不是呢？摘星者皆穿蚀于暗夜，微亮的莹屏却永载着溯游的梦舟。

依稀记得去年被急速升温的中枢神经系统和颤抖的横纹肌击倒在地，赛后一边吃退烧药一边在游记里疯狂发癫。真希望这次能写下一篇明亮些的文章。

祝好运。

抑扬顿挫的比赛

先依次看看四道题，T1 好像是签到题，T2 疑似是神秘计数，T3 好像还是神秘计数，T4 好像是神秘数据结构题。

那么顺序开题吧。

T1 好简单的样子，随便一写就过大洋里了。

开 T2，仔细想了想贡献，发现只是所有相邻对的贡献乘在一起。发现合法情况很多但是不合法情况很少，只有从 j \to i 的一条链，只是最后一步不连到 a_i. 然后随便做一做就结束了。

T3 一眼没看懂，感觉会是类似双序列拓展的困难题，于是考虑 T4. 仔细想了想，发现一个关键的性质：将一个集合 S 拆分成不交的子集 A, B，有 \operatorname{LCA}(S) = \operatorname{LCA}(\{LCA(A), LCA(B)\})，于是可以用类似 ST 表的东西倍增一下，时间复杂度 O(n \log n + qn)，能过 n=5000.

诶怎么这个做法还能过 B 性质的……于是开始考虑 A 性质怎么写。

发现将链上的情况转化到序列上，可以变成一个经典问题：在区间中查找一个长度不小于 k 的子区间，使其中的最小值最大。

先考虑单组询问的做法，一眼二分答案。考虑从小到大插入序列中所有元素，并用线段树维护每个空段的左端点向后延伸的一段的长度。

若某个答案能被满足，必然被 [1, r - k + 1] 中的某个长度 \ge k 的区间包含。于是可以用权值线段树维护这个东西。分类讨论一下 [l, r-k+1] 中的和左端点 < l 的情况即可。

注意到这个权值线段树其实是可以在多组询问中共用的，所以用整体二分做到 n \log^2 n，和前面的部分拼起来（大概）能拿到 64 分。

赢麻了赢麻了，先检查一遍然后去冲 T3.

诶怎么我 T1 大样例其实没过……

不是哥们？

回头狠狠改狠狠检查，怎么下发密码条了还没写完……

写了三个小时终于写完了，还剩 15 分钟结束。已经没啥时间了，只能检查文件读写并提交。

输输输。但值得庆幸的是，还好我调出了 T1，要不然这篇文章就真的变成退役记了。

赛后的话

出厂之后发现大家貌似都被 T1 控了好久（但是 MMH VP 的时候秒切了 T1，%%%）。

怎么大家 T3 都拿了好多分……没看 T3 的我输麻了。

和 user 交流了下，又仔细想了想，发现我 T4 做法其实可以拓展到图上的，而且基本上不用改什么东西，还是按顺序插入就行，只不过每次需要插入多个点。考场上确实疏忽了，错过了单杀 T4 的机会。感觉自己分数的瓶颈不在思维，而在代码的实现能力，看来有机会还是要多练练大模拟了。

听说 ANIG AK 了，好强好强。

和大家简单对了一下，感觉队线会是 272 左右，而且这附近挤了很多人，所以进队的关键还是在省选了。我和大部队差的不远，还是有希望的。

（UPD：T4 整体二分的清空和递归好像写反了，没有一点希望了，但愿别的题不要挂分。）

枫叶红时，总多离别。很多熟人都宣告退役了，心里很难受。也许 OI 就是这样的一场旅程，在这里，我们不断分别，不断失去，不断进步，不断成长。抵达终点者终究是少数的幸运儿，但既然走上这不归之途，便带着希冀与愿景走下去。愿此行，终抵群星！

UPD2：最终成绩 232 分，不挂分的话果然卡在队线上，不过现在和队线差距不是很大，还是有机会翻回来的。继续努力吧……