省选联考 2026 游记

wshcl · 2026-03-12 13:22:14 · 生活·游记

省选联考 2026 游记

前传

上接虚空调试导致 NOIP 233，然而 FJ 队线 274。

如此幽默战绩，何以竞争省队？

请启动省选联考 2026！

Day 1

被分配到了 sdfz 502 机房座位号 09，第一次来，之前都是在隔壁的 501 。

这个机房键盘怎么键程这么短，怀念隔壁 501 的长键程键盘了（虽然还是自己的机械键盘打着舒服）。

下发代码后先看题目名称：recollector、string、night，第一印象是：追忆、串串、无。

再看时空限制，发现 T2 3s 2048MB，追忆还在追我。

扫了一眼 T1，随便云了个 f_{u, i} 表示 u 子树内 u 所在底下重链长为 i 的概率，感觉随便转移。然后发现数据范围是 n \le 5000 ，应该是正解。

开始推推转移式子，想到枚举重边，然后再枚举其他轻边底下的重链长度和。直觉上是一个退背包状物，但是我咋退不出来。分治会带一只 \log ，前后缀自己不会卡，写之。

代码不算难写，写完开测大样例，跑的挺快，9:05 弃了 T1。

开 T2，发现是个构造，但是好像和构造没啥关系，也和串串没啥关系，何意味？

好吧其实想到了 KMP 状物处理匹配，感觉一眼没有想法。

手玩发现填的过程中一些位置作为左端点时一定满足字典序 < s ，具体的结构为一段前缀 S[1 : i] 满足 S_{i + 1} 为 1 ，然后在后面填 0 ，这样字典序就会严格更小了，且称这些位置为支配位（支配点对还在追我，其实一点关系也没有，名字叫着顺口）。

打打暴力，尝试一下 n \le 50, k \le 2000 的档。先堆一堆状态，设 f_{i, j, k, l, p} 表示填了 i 位、匹配了 j 位、出现了 k 个支配位、是否匹配成功过、有 p 个子串字典序 < s 的可行性。

但是还有个问题，我完全无法确定第一维（答案长度）的范围，综合所有大样例，随便估了个 n + k 。然后发现空间差不多要 1.25 \times 10^{10} ，纯纯的爆炸。

直觉告诉我这种可行性 DP 可以上 bitset ，发现每次维护 p 应该可以用位移操作整体转移，对这一维开 bitset 时空复杂度就可以除以 \omega ，差不多是 2 \times 10^8 级别，还是不太够，但是可以冲一冲，大不了赌一手答案上界更小。

推推转移，枚举一下 s, t 的下一位分类讨论，感觉是不难的，新出现的 < s 的位置就是原来的支配位、新的支配位、以及当前匹配串在 fail 树上的深度。然后发现每个支配位在后续过程中会一直贡献，因此支配位是 O(\sqrt{k}) 级别的，于是新的时空复杂度来到了 4.4 \times 10^6 级别，看起来还可以。

最后写了 4.8k 差不多，发现答案长度是挺对的，但是咋还要输出方案，把 DP 又复制了一遍，何意味？

接下来考虑调调空间，看看能不能跑跑 n \le 150, k \le 2000 的档，但是空间限制，答案维只能开到几百了。翻了一下大样例发现答案长度普遍都很小，几个很长的 s 都是全 0 的结构。于是开始乱搞，考虑给全 0 的串单独写一个暴力，然后剩下的就把第一维开小、其他维开大。这个暴力还是很好写的，输出方案也不难。

众所周知，一般情况下 DP 输出方案就是倒着走回去，但是 wshcl 在这过程中写错了每次要回退的数量，导致可能会将当前合法子串数量减到 < 0 。而一般退出的标志是当前合法子串数量减至 0 ，于是程序 TLE 了，并且向输出文件中输出了好多好多 GB。

发现不对后 wshcl 就把程序关掉了，稍作修改后系统提示内存不足无法保存。正常人都会想到是刚刚的输出文件的问题，wshcl 也是这么想的，于是直接把输出文件删掉了。

但是怎么还是保存不了，wshcl 认为是 Sublime Text 的问题。正常的 Sublime Text 是存在自动保存的（哪怕你的文件还没保存为文件也会留着），于是 wshcl 将 Sublime Text 关掉后再次答案，神人的是该文件在打开后什么都没有，于是 wshcl 认为是 Sublime Text 的问题，但是尝试用记事本打开后也还是什么都没有。随便敲了一两下发现还是保存不了，红温了，遂向监考寻求帮助。

监考在我的电脑命令行上输了好多好多我看不懂的指令，然后发现电脑内存还是被占满了。交涉后未果，于是申请了换电脑。但是刚刚写的 4.8k 的暴力全部都没了，非常非常红温，非常非常爆爆爆，何意味，怒了！

唯一幸运的点只是在于 T1 代码还在吧，拷贝了 T1 的代码后转移到了别的机子继续考试。期间同校的容三喜悦目睹了全过程，我想他能够感知到我的幽默。

现在首要的问题就是赶紧凭着记忆把 T2 的代码重新写回来，wshcl 尽量平复自己的心情，给予自己信心。这个时候差不多是 11:34，把 T2 大头的分数拿回来。T3 这个一眼构造思维题的状物感觉就不是很好弄，大不了最后拿个最低档暴力跑路。

目前唯一的信息就是草稿纸上的状态设计以及新合法子串的来源（只有七个字：原配、新配、前后缀），wshcl 尽量冷静下来，告诉自己还是有机会再理顺代码的。

开写开写开写，这次写的比之前顺畅许多，改了几个边边角角的错误之后就过了一部分大样例。用自己写的 checker 测了一遍应该没啥问题，原来的分数应该是拿到手了，这个时候差不多 12 点多了。

后面的时间就是在调答案维的范围，差不多只能开几百这样，最后程序的空间占用 1800GB 左右，离 ML 还是很接近的。

剩下的部分分感觉短时间没有什么想法，想到了也不一定写得完，于是考虑开 T3 了。

T3 第一眼秒了前三个点的暴力，然后想着剖析一下操作的结构。发现 2m \ge n 的情况判掉全 1 或全 2 的操作后好像可以钦定一段是匹配的然后做，应该是比较启发性的。

后面还想了想操作的性质，尝试合并连续的操作为如下状物：左边或右边的四个合并成一个、左边的一个和右边的两个合并到右边（对称的同理），综合这两个操作写了个形式化的结构，然后发现没啥用。

感觉钦定一段匹配的方向很对啊，但是后面一直也没有想法，学生再次斩下最低档暴力。

最后的时间检查了文件等，Day 1 over。

出来先和同校的选手交流了一下，发现自己退背包犯傻了，直接正常退就是对的，但是前后缀合并背包好像是三次方的，三次方只有 50 分，爆爆爆。

同校似乎没有切 T2 的，也没问到 bitset 乱搞，也没有 T3 好多部分分的，我猜一手肯定有人藏分。

之后和福州的选手进行了交流，问到了好多薄纱的成绩，感觉自己 Day 1 烂完了。

我常常追忆 bitset ，为啥不让我会 T2 。

出校门后发现了同校毕业的传奇福州大学 XCPC 领军人物 Calculatelove，他给我们带来了经典一点点奶茶，好评好评。下午直接海底捞启动，爽吃爽吃。

Day 1 如此幽默，Day 2 该何去何从？

Day 2

开赛，发现 T1 T2 都是交互题，神了！

看看 T1，每次可以询问区间 \mathrm{mex} ，然后还原序列，感觉很典的样子。

看看数据范围，经典环节是看成询问次数 \le 6 \times 10^5 即可，然后感觉这个 n \log n 的范围随便做。往下看 pdf 就发现自己看错范围了，需要一个 \le n 的做法。

手玩了半天，没有想法，感觉一车人一眼秒了这个题。搞了半天只会做到操作次数 \le n + \log n ，分析了半天又回到原点了。

感觉这个 n + \log n 是很路边的，但是好像自己怎么都不会 \le n ，于是考虑乱搞。

先考虑 n 这一项，把一步步推用倍增优化一下，这样关键点间隔很大的时候就可以省去很多询问。

再考虑 \log n 这一项，发现只要我每次二分是问出了一个 0 的答案就会很亏，最坏会问出 \log n 个 0 。于是考虑每次随机询问左右区间，这样期望就为 \frac{1}{2} \log n 。

写完之后还在继续想 T1 的正解，但是一直没有想法。中途出去上了洗手间，路上也没啥灵感，于是决定先开 T2。

看完了 T2，想了半天发现自己一个部分分都不会，n \le 8 都没有一个比较好的策略，心情有点烦躁。

不行还是先打打 T3 的暴力，发现 T3 什么幽默长长题面，又是定义一堆莫名其妙的东西然后维护树上 DS 状物。

为什么一群 \emptyset 可以比大小？因为滚木之间亦有分别：\{\emptyset, \emptyset, \emptyset, \{ \emptyset \}, \{ \emptyset, \emptyset, \{ \emptyset \} \} \} 厚重，而 \{\emptyset, \{ \emptyset \} \} 飘渺。

手推了一下发现菊花时每个点的排名 \le 3 ，随便找找规律就能维护了，写之。

事实上菊花图上很多东西（如 LCA）都是可以简化的，但是 wshcl 没有注意到这一点，写了一堆东西去维护，虽然最后好像也没事。

写的时候监考还进来改了样例解释，之后又改了一次，但是我觉得样例二其实没啥看的必要，所以影响不大。

然后发现其实 n \le 10 也不难，但是好像不是很好写，还是去看 T2 吧。

再战 T2 还是发现自己根本不会任何一个档的暴力，但是秉持着不能空题的原则，于是开始想乱搞。

想了一个贪心，每次选择总边数变化量最大且不劣的操作执行，这个随便暴搜一下就出来了，写写写。发现这个算法能过前两个大样例，感觉有点牛。

尝试推广到 n \le 500, k = 3 的情况，此时三个点至多只有一条边。如果是三个点不连通的情况，枚举两个点，然后用 bitset 找到任意一个满足条件的点即可。如果是三个点一条边的情况，枚举这条边，然后就和上面一样了。写写写，发现甚至还能过对应的大样例。

我感觉这个贪心没啥道理啊，最终数据感觉很大概率一分都没有，但是我手头也没有什么好好的想法了，哭哭。

剩下时间不多了，T3 应该是写不完小暴力了，想着检查一下文件啥的就可以 over 了。但是幽默场务在距离考试结束 15 分钟的时候进来告知有延时环节，你早说啊我就去写 T3 小暴力了。

最后还是打算开写 T3 的小暴力，但是直到结束都没有写完，码力不太行。

出来交流了一下，masterhuang 直接闪现到面前和我一起吐槽这个 T2，但是好像在旁边听到了线性基，感觉很有道理啊。

好多人薄纱 T1 了，同校的学弟也薄纱 T1 了，大家都远远强于我。

大家好像都在吐糟这个神人题目，放两个交互，这简直不是人嘛。

下午去吃了烤肉，容三喜悦被幺神的家长夸很会照顾人，原因是他帮我们烤肉的瞬间被捕捉到了。以此为契机，幺神使用豆包展开了对其的强烈追求，并怒喷某学长作为幺神自己原配的价值。

后记

出分：202+104.95，加权之后 FJ 高中省排 16，但是男队只有 13 个，呜呜没队进了。

感觉 OI 彻底要变成智力竞赛了，交互构造还是太神秘了。

化用教练的调侃：算法都没有用大家就都不要学算法了，大家都去摆烂就可以进队了。

这种题目还是场外做有意思，赛时我不评价，因为我不会。

选手的水平越来越强了，FJ 的 OI 事业还在蒸蒸日上！

已严肃转战文化课，期待 wshcl 能够在 whk 的道路上收获更好的结果。