CSP-S2025 sol
strcmp
·
·
个人记录
T1
每个贪一次最大值。
然后把绝对众数的计数移到次大值上，注意到次大值对应的东西不可能在操作后 > \frac{n}{2}，毕竟我们绝对众数到 \frac{n}{2} 就收手了。
做完了。
T2
对原图跑 MST，现在只有 n - 1 条边。
对额外点，我们枚举前后 $k / 2$ 预处理 $2^{k / 2}$ 个 MST，枚举 $2^k$ 的时候就是前后拼起来。
然后只剩下 $\Theta(n)$ 个额外边，复杂度 $\Theta(n2^k\alpha(n))$。
实际上大样例没跑过直接 Kruskal 的 $\Theta(nk2^k\alpha(n))
T3
考虑 s_1 和 s_2 的 LCP 和 LCS 夹在中间的那一块。
比如考虑 s_1 = x + y + z 和 s_2 = x + y' + z。
并且令 t_1 = a + b + c 和 t_2 = a + b' + c。
令 x 是 a 的后缀，z 是 c 的前缀，y = b 且 y' = b'。
按 y 或者 y' 分组，建立若干字典树数点即可。
复杂度 \Theta(|L| \times |\Sigma| + (n + q) \log |L|)。
T4
考虑王之钦定 trick。
转移讨论 $i$ 是不是在这 $k$ 个人里面，可以做到 $\Theta(1)$ 转移。