联合省选2026 游记

进场，T1 考期望？T2 字符串，T3 神秘题。

T1 首先可以设 $f_{x,i}$ 表示考虑 $x$ 的子树，$x$ 所在重链长度为 $i$ 的期望，然后就可以直接 $O(n^2)$ 算答案了？非常兴奋以为自己秒了 T1，然后才发现自己根本不会转移 $f$。

前后缀卷合并？显然可以卡到 $O(n^3)$。

缺一分治？$O(n^2\log n)$ 很难过 $n=5000$ 吧。

撤销背包？完全不会怎么撤销，告辞了。

尝试若干做法，一看时间 90min 了，我写了 0kb 的代码。上个厕所清醒了下，先把 $O(n^3)$ 代码胡上去，135min 调完。

试图优化，罚坐半小时，再上个厕所回来突然灵光一现，想到了 CF1810G 的 trick，这个 dp 不就可以反推贡献系数优化？然后就对完了？遂直接写，220min 过了全部大样例。

然后只剩 80min，这时间我写你吗 T2T3。思考 30min，会了 $30+12$。

12:40 开写 T3。

12:55 写完 T3 8分。

13:00 写完 T3 12分。

13:15 T2 爆搜写挂了。

13:16 调不出来，13:17 调不出来，13:18 调不出来，13:19 调不出来，13:20 调不出来，13:21 调不出来，13:22 调不出来，13:23 调不出来，13:24 调不出来，13:25 调不出来，13:26 调不出来，13:27 调不出来， 13:28 调不出来，13:29 调不出来。13:30 调不出来。

期望：$100+0+12$

奇异搞笑写 30min 爆搜，获得 0 pts。

出考场，神秘大神直接破解了压缩包，自己造数据一测发现 LN 一万个人过了 T1？？？？？？？？？布什戈门前后缀暴力卷能过？？？？？？？

T1 是交互？？T2 是交互？？T3 是滚木？？

T1 考虑 A 性质，可以直接从左往右查，尝试扩展到正解，一个做法是先二分找到 $0$ 的位置，再不断往左右较小的数扩展，这样期望是 $1.5n + \log n$。

然后罚坐 150min，完全不会优化，不管了先写后面暴力。

T2 这是啥？完全刻画不出任何操作，拼劲全力获得 0 pts。

T3 这是啥？怎么滚木和滚木还能排序的？想不到任何非平凡分数，拼了菊花，$r \le 1$ 和 $n \le 10$ 上去，有 16 pts。

剩 50min 回来想 T1，突然发现之前的做法是从 $0$ 向左右扩展，反过来改成从左右往中间扩展，是不是就对完了？

12:40 开写。

12:50 假了。

13:00 重新开写。

13:?? 写挂了。心态爆炸直接开摆。

13:?? 宣布加时 15min，心态+1，直接开调。

13:31 调不出来。13:32 调不出来。13:33 调不出来。13:34 调不出来。13:35 调不出来。13:36 调不出来。13:37 调不出来。13:38 调不出来。13:39 调不出来。13:40 调不出来。

13:41 不写了，检查代码。

期望：$?+0+12$

不会 T1 是什么梗 不会 T1 是什么梗 不会 T1 是什么梗 不会 T1 是什么梗 不会 T1 是什么梗 不会 T1 是什么梗 不会 T1 是什么梗 不会 T1 是什么梗 不会 T1 是什么梗