论noip 176的我省选如何打进ZJ队线（仅省选）

wangziyue_AK · 2026-03-14 16:42:59 · 生活·游记

前情提要：

noip176的我省选考前被教练压力，说省选哪怕进不了省队也一定要打好，否则可能被开掉，同学还被下了单省选 rk20- 的死命令。

Day 1:

开场，看 T1，显然有期望线性性，我只要算每条边被覆盖概率，直接 dp_{u,i} 表示 u 子树重链长度为 i，概率是个缺一个的背包。哦，考前刚做 Tree Depth P，直接退背包，分析一下复杂度好像对了。写写就过了。

看 T2，怎么是构造，此时我非常紧张。然后一看，全零好像可以直接 dp，全一好像也行。那就考虑一个个填字符，此时我想到了 节日庆典，按那题的理论严格小于和严格大于后面就不会变了，我只关心大致等于。大致等于要记的好像就是极长匹配，记一下 kmp 自动机上跑到哪里就对完了。直接把信息全记上怎么是 O(nk^3) 的，好像只能 bitset 优化，烂完了（并没有意识到判掉全 0 答案其实是 O(n+\sqrt{k})）。然后我发现一个个填不用把答案当一维，直接 bfs 转移就对完了，严格小于的个数也是自然根号，复杂度直接对了。写写写，调调调，好像连想带写只花了 3h。怎么记前驱被卡空间了，直接 bool/char/short 乱存，这空间稳过啊。怎么结构体有左对齐，算了，不改了，看起来还能过。

看 T3，发现有异或和为 0 的区间似乎会让特殊性质倒闭，好像没办法，暴力跑路。

Day 2:

看 T1，第一反应直接二分 0 在哪，往左右找数，然后就 2n 了。我好像只关心前后缀，加起来只有 n+1 个非零且有两个固定为 pre_{1}=n,suf_{n}=1，那就对完了。此时我发现知道前后缀求构造是原，我还刚在联考做过，糖丸了。

看 T2，不会，看操作次数猜测正解每次操作都使答案增加，结果贪心选增加答案的好像直接假了，只能过 k=3。

看 T3，卧槽，物品怎么是棍母，哦，这不就是括号序树哈希吗，我会好多分。不对，怎么菊花只有一个点，暴力能过似乎只有两个点，r=1 也只有一个点。哦，可以把子孙换儿子不影响比较，树随机所有直接记 string 维护括号然后合并时排序再拼接复杂度是对的。

后两小时坐牢，啥都不会。

结局：