2026联合省选 游记

· · 生活·游记

2026联合省选 游记

省流：分数比较随机

坐标 SC，高二，是最后一次省选。

Day -1

本来计划复习 DS，结果打开网页的时候不小心输成了 generals.io。晚上打了会儿球，回家又不小心点开了无畏契约，最后看了会儿板子和博客，大概 23:00 睡觉了。

Day 1

考场和去年一样在石室，到的比较晚就直接进去了，然后到位置之后开始睡觉。

开考看 T1，发现是最擅长的计数/期望类题目，将贡献拆到每个点，然后设 f_{u,i} 表示子树 u 内重链长为 i 的概率，直接转移似乎是 \mathcal{O}(n^3) 的。然后发现先做一遍背包之后，再对每个儿子做撤销背包即可，复杂度跟树上背包相同，多项式求逆需要找到第一个非零位，复杂度 \mathcal{O}(n^2)，大概写了半个多小时过了所有大样例。

然后发现 T2T3 咋全都是构造。先看 T2，没有任何头猪，然后想了会儿会了全 0 和全 1 的特殊性质，发现拓展到原问题没有任何前途。想到了 10:00，发现如果从左往右填，那么只需要记录有几个后缀一定比原串小，当前的 border 是啥以及有没有出现过原串就够了，设 f_{i,j,k,0/1,p} 表示填了 i 位，有 j 个后缀一定比原串小，border 为 k，是否出现过原串，答案能不能为 p，最后一维是 bitset。

然后发现 j 是根号级别，有个小剪枝就是 i 越小越好，所以直接一直转移直到不能拓出新状态，复杂度未知，最后一个大样例跑了 3.3s，得分应该是 90~100（一个比较唐的事情是我发现了 i 越小越好但是没有想到换维）。

写完 T2 已经是 12:00 了。开 T3，因为时间不多所以我就想以拼部分分为主，先拼了 n\le 16,m=1，然后发现我完全不知道 ABCD 性质是在干嘛，于是从 m\le 2 入手。如果考虑每个 a_i 最终对哪个 b_j 有贡献的话，那么一定长成 112211 或 221122 这样，直接 dp 即可。如果 m>2 大概就是 334455112233 这种东西，但是这并不是充要条件。

发现题目中的操作很能跟 \bmod 3 扯上关系，找一个分界点，将右边数权值设为 1，左边数权值设为 2，那么要求所有数权值和 \bmod 3 相同。然后还发现出现一次的数必须是个区间，猜测这些已经是充要条件了，枚举分界点后 dp 得到一个 \mathcal{O}(n^3m) 的做法。这个时候是 13:00，我在写上述做法和写 m\le 2 的做法之间犹豫了一会儿选择了前者，最后几乎卡点写完。但是因为时间来不及了所以构造方案是乱构造的，过了小样例，测第二个样例时发现 WA 了一些但没管了，后面的来不及测了不知道能过多少。

估分：100+[90,100]+[12,68]=[202,268]

出场随机问了几个也是 200 左右，感觉这个分数还行。

下午晚上依旧打瓦。最后也是 23:00 睡的，但明显感觉到睡得比前一天好。

Day2

依旧到位置后开始睡觉。8:25 下发密码，打开题目浏览一下直接没有绷住，怎么有两个交互？？

T1 操作次数是 n 感觉不会太困难，想了十多分钟后发现求出 a_0,a_{n-1} 之后分讨两个的大小关系递归下去即可，大概写了半个小时通过，感觉问题不大就没写对拍。

T2 也是非常神秘，传统题出成交互格式。看了下只会 k=3，部分分似乎没任何提示，然后做了一个小时没找到任何突破。也是想到了 10:00，发现操作 4 次可以翻转一个四元环，于是跟 k=3 一样操作，可以让边数达到上界 -eps，一开始还要根据 k 的奇偶性分讨，写完之后发现有些点跟答案相差 1\sim 3。然后就开始尝试微调，在所有操作前再塞一两次操作，最后尝试了各种办法终于过掉了所有大样例，操作次数大概是 n^2，发现有 67 分。

开 T3 已经是 12:40 了，一开始看题还不懂如果叶子是空集那不是所有点都是空集吗，一看样例解释发现一堆滚木在比大小，说了句 wtf 被旁边同学瞪了一眼。前两个点比较简单，然后发现滚木比大小实际上是将儿子节点排序后，依次看子树是否同构，不同就递归下去，写了个树哈希，总复杂度 \mathcal{O}(n^3)，能过 n\le 10。最后也是卡点写完了的，但这次来得及测了一个样例。（所以为啥有的省延时 15min 我们没有）

估分：100+67+16=183

出场发现我考的有点好，主要是 T2 拿到了非平凡分数，回家没有看任何有关讨论，直接开摆了。

Day3

下午在机房自习时获得了代码，在 qoj 上测试后发现 D1T2 获得了在 [90,100] 间获得了 100，D1T3 在 [12,68] 间获得了 46，运气有点好。所以 D1T3 我的结论应该是对的，但是构造错了，所以过掉了 m\le 2 所有分和 n\le 50 的一半的分。

所以最后是 100+100+46+100+67+16=429，感觉是这辈子发挥最好的一次比赛了，但 NOIP 296 有一点点遗憾。

最后祝退役的 oier 文化课顺利，也祝进队的在 NOI2026 中取得好成绩。

什么叫 D2T2 把所有操作塞到线性基里面那有用的就只有 \frac{n(n-1)}2 个？