旅途的尾声

· · 生活·游记

声声慢

这首词理论上是 NOI2025 结束后打算填的，但是下阕一直咕到了 NOIP2025 结束后才填完。正好那段时间在写《年岁归春》，就化用了几句到歌词里。

从考前状态来看，无论是压力还是训练动力，省选都比 NOIP 高出一大截。当然这不是什么坏事，但是从结果来看确实没有对我的分数起到什么正面的作用。

考前不敢听什么过于昂扬激烈的歌。前一天晚去 HZNU 的路上在车上放了经典曲目《人是_》《光与影的对白》、WC 汇演的《上山岗》《十重告别》、拜年纪的《辟浪》《年年对对》。等放完《Positive Outlook》已经到酒店了。想起来一年前还在这里遇到了 @ztlh，时光飞逝啊。

睡前放了一遍《年岁归春》（vocaloid ver.）和若干遍 @Comentropy 弹的钢琴曲。

第一天。晚上睡眠质量还可以。读完 T1 几乎立刻会了，重新想了一下确定自己的做法没有假之后就开始写。写的途中发现自己不太清楚退背包部分复杂度有没有写对，写完再说吧。还想了一下会不会不存在逆元，结论是不会。写完发现最后一个样例 T 飞了，再仔细一看发现退背包果然写成 O(n^3) 了，改完就飞快过了所有样例。这时候 ~45min，优势在我。

看 T2。读完题想了一会会了一个做法：记录 kmp 匹配长度、有几个在匹配长度以外的 l 会在新加字符的时候产生贡献、目前字典序比 S 小的子串有几个、以及有没有匹配上，然后在这上面跑 BFS，时空复杂度都是 O(nk^2) 的。 这咋优化来着。想了一万年怎么做到 O(n^2k) 或者 O(n^3+k^2)，看了眼特殊性质，发现全 0 直接做，全 1 好像不太会。那么我这个做法看起来只有 45 啊，感觉有点细节，根据 noip 经验，写代码挫伤锐气，还是应该每道题都先认真想一会！

这时候有点困，读完 T3 题决定去上个厕所。回来之后感觉清醒了一点。思考了一下发现题意等价于有一个环，有一个标记序列开头的指针在上面移动，然后可以 merge 相邻元素，这样的状物。先判掉两个序列异或和不相等。手玩几组发现 merge 在一起的元素对应的区间长度 mod 3 是很重要的，对于一般的情况，mod 3 = 0 就倒闭了，mod 3 = 1 是指针需要先走到右边再走回来，mod 3 = 2 是指针只能往右走走不回来了。猜了一个结论是，B 性质有解当且仅当所有区间长度 mod 3 = 1，并且长度恰好为 1 的区间必须出现在原序列的最前面。先只写了第一问。发现样例只有俩 YES，于是写了个拍子。这我也不会造数据啊，只会直接随。发现有一个 corner 是其中一个序列只有三个 1，我声称这时候一定有解。然后就过了六万组拍。想了一下感觉 C 性质好像也可以类似地做啊，但是感觉依托。

这时候只有 1.5h 了，感觉还是要稳一点先把 T2 写了。感觉我 1h 能写完啊，剩下 30min 把 T3 能写的部分整理一下，优势在我。

写的时候我才发现这个 T2 好像细节有点多（我的预处理转移写了一大坨，还写了 z 函数）；直到还剩 15min 的时候，我还没过去大样例。

这时候我终于意识到，我好像有大麻烦了。

我没有指数级暴力，没法拿到一组用来调试的小数据。

瞪眼瞪出来了一处错误，改完，还是挂得一样。

13:20。我决定进行最后的挣扎，写一份指数级的代码交上去。但是此时巨大的心理压力和随之引起的生理反应让我几乎丧失了写明白代码的能力，我的两只耳朵开始剧烈地发麻，同时开始不由自主地喘气，根本调不出来我哪里写挂了。

100+0+12。

在这漫长的十分钟里，我接受了 day2 将要成为我 OI 生涯最后一场比赛的现实。

下午阅读 uq 讨论，发现我认为 O(nk^2) 的 T2 做法复杂度怎么可以分析到 O(nk^{1.5})。没有人类了。

和家长在 HZNU 周边随机逛了一下。看到了绚烂的晚霞。

第二天。比赛策略是要么翻盘要么炸成咋样都无所谓了。怎么两道交互啊。T1 稍微卡了一下，因为我第一反应是需要二分 0 的位置。差不多也在 45min 的时候通过了。T2 咋做啊？？？第一反应是随元素然后插线性基里，但是线性基咋最大化元素异或和 popcnt 来着？？？这我哪会啊。看 T3。大 DS。经过一些手玩我意识到了题目中比大小的组合意义，相当于给两个子树，比较其字典序最小的括号序哪个小。写了个暴力验证了一下结论是对的。随机拼了点部分分。观察了一下，拿持久化平衡树维护哈希，就可以在合理的复杂度内算出以 1 为根的答案，同时由于如果两个子树最大深度不同，那么其大小关系也是已知的，经过一些手玩似乎只需要 check O(1) 棵换根后的子树即可解决 ox=oy=0 的问题。

但是场上是不可能写持久化平衡树的。拼完 24 分后我决定 all in 这个 T2。这时候还有差不多 2h，还有希望。

先做第一问。观察完打表打出来的线性基形态后，我发现 k 是偶数的情况非常简单，但是没有分。接下来我做了一万年 k 是奇数，没有任何思路。通过观察打表，我甚至得到了偶数 k（mod 4=0 或 2）各自的构造，但是没有丝毫用处。

还是得做 k=3 啊。根据线性基的形态，我发现三元环其中一个点一定可以定为 1 号点，但是还是没有任何想法。万念俱灰之下，我决定求助于随机算法，但是爬山和退火都收效甚微。这时我突然发现随机算法输出的解都小得离谱，但是其实我可以先用三元环把没有和 1 相连的边全部“点亮”，这样答案应该已经很大了，然后再在这个基础上爬山。写完发现过 k=3 了。

会有奇迹吗？

经过一些不冷静的思考，我认为 k mod 4 = 3 本质上就相当于 k=3，而 k mod 4 = 1 相当于每次操作必须同时操作两个三元环。

实现了一下，发现 k mod 4 = 1 在比较大的样例上会偏小 eps。

13:15。

我认为，“每次操作必须同时操作两个三元环”不一定对，吸取了 d1 的教训我决定立刻开始写指数级暴力。这时候听到了比赛延时 15min。

写写写。在 13:40 左右我发现我的暴力即使卡了常也跑不动 k=8。这时候我才猛然发现，我估算复杂度的时候把 \binom{8}{2} 算成 18 了。

最后还是白写了指数级。

花了一点时间调整了随机算法的一些参数，还是没能随对 k mod 4 = 1。

13:43。

我在 starmap.cpp 的结尾写下了 // Farewell.

星图指引的，未必是归途。

我确实战斗到了最后一刻，但是并没有奇迹发生啊。

13:45。

赛后我发现，使用一些精细一点的爬山策略，就可以过第一问了。如果我最后不去 rush 指数级，我认为我还是有拿到这道题 25 分的机会的，但是看起来这并不会影响结果。

我曾经无数次想象，我在 OI 赛场上的最后一分钟会是怎样的场景。

写的上一篇真正意义上的游记是 NOIP 2024，当时是作为高中正式选手的第一战；一年多过去了，我也迎来了我 OI 生涯的谢幕。

这一天总归会到来的，不是吗？

我进过了省队，拿了 Ag，组过了 CF Global Round，发明了某个还算经典问题的新做法，站上了 WC 文艺汇演的舞台，其实并没有留下很多遗憾。

感谢大家一路以来的陪伴，相信我们的故事还没有结束。

算尽命运纷繁岁月沧桑 依然向未知远航

偶见云破月明千里银妆 便忘却淹没四周的迷惘

谙旅途难测 许不变信仰

何当与君再聚一堂 将往日故事重讲

前路何种模样 毋须想 春归时将希望鸣响