2026联合省选游记

· · 生活·游记

两天的T1都用了近似于全部的时间，都失败了。

Day 1

T1

首先第一次卡的点在到根路径能否拆到每条边上，因为我忘记了期望的可加性是否要满足各个部分独立了，后面手推了一下，发现没问题。然后问题就转成了问每条边是重边的概率，考虑设状态 F_{u,i} 表示在 u 的子树里面，重链长度为 i 的概率，这个东西的转移是 F_{u,i}=\sum_v F_{v,i-1}\sum_k \frac{i-1}{i-1+k}G_{v,k}，其中 G_{v,k}代表 v 的兄弟重链长度和为 k 的概率。我一开始误以为直接求 F 是 O(n^3)，而求 G 是 O(n^2) 的（后面发现两个反了），然后就糟糕了，我一直在想 F 这个式子怎么优化，想了好久，决定破罐子破摔打 n^3 了，然后打到一半，发现求 G 也是 n^3，而且更难优化，然后我就只能硬着头皮打下去了。不知道为啥这东西这么难调，调了好久，打完的时候已经没时间了。发现自己最后的一个大样例跑了0.6s，因为加了很多卡常剪枝，不知道能拿多少。

T2

赛时没时间了，打了个状压就跑了。

赛后发现，这东西是一个kmp自动机上的dp，就是说注意到如果t的一个子串的字典序严格小于s的条件是什么，可以分两种情况讨论，第一种是有一位小于s，前面都相同，这种情况无论如何后面怎么填都是小于s的，第二种是s的前缀。我们设dp状态是 dp_{i,j,k,0/1}，表示当前kmp匹配到i，有j个左端点开头的后缀是小于s的，小于s的串有k个，是否有s这个子串的答案。由于转移边权是1，可以用bfs，复杂度 O(nk^2)，j是 O(\sqrt k)的，所以是 O(nk^{1.5}) 的。

Day 2

T1

交互题，一开始从 p_0=0 开始突破，发现这个情况就是一直往右扩展就行了，当前缀 \mathrm{mex} 变化时，说明这个值是可以确定的，然后中间跳过的值随便填就行了。然后我首先发现了单谷的 n+\log n 做法，就是找到 0，然后将已知数的区间向两边扩展，哪边能扩就扩哪边，其实可以省掉找 0，直接从大到小缩区间也是可行的就变成 n 的了。综合这两个部分分，我就想到了 2n+\log n 的做法，加了记忆化就能变成 1.5n，也是先找到0，然后像第2种情况一样先看左边还是右边能扩展，然后像第1种情况一步一步扩展就行了。但是这种做法每一步要多一次找方向，于是我就一直在想如何减少这一步，结果还是没搞出来。然后我开始分析数列的性质，注意到有值的序列一定是单谷的，但是我当时没想到办法来求出这个单谷的序列，所以到最后还是没想出来。实际上，如果反应到了 \mathrm{mex} 等于补集的 \min 这个性质的话，这题就很好做了。首先跑出前缀 \min，找到 0，然后从 0 开始找后缀 \min，这个序列就找出来了，填其他数也是一样。考试的时候，我还是太高估这题的难度了，没办法，有点被样例误导了。

T2

一道假装交互的传统题，由于这道题太不可做了，所以直接跑了。后面才知道，像这种不可做题肯定是有结论的，也是得到了一点经验吧。

T3

后记

感觉省选好奇怪啊，根本不知道自己的定位和题目的难度，去年也是这样，导致我没打多少暴力还T1做不出来。 感觉自己打代码还是太烂了，基本上打完T1高分暴力后面就没时间做了。而且每次大赛总是在无关紧要的一些地方想来想去，后面发现完全没有用，又浪费了很多时间，可能要对思维的方式进行优化。

出分

什么叫暴力 O(n^3) 过了，什么叫所有T2T3没分。181菜完。