CSP-S2025 sol

每个贪一次最大值。

然后把绝对众数的计数移到次大值上，注意到次大值对应的东西不可能在操作后 $> \frac{n}{2}$，毕竟我们绝对众数到 $\frac{n}{2}$ 就收手了。

做完了。

对原图跑 MST，现在只有 $n - 1$ 条边。

$2^k$ 枚举不可避免。

对额外点，我们枚举前后 $k / 2$ 预处理 $2^{k / 2}$ 个 MST，枚举 $2^k$ 的时候就是前后拼起来。

然后只剩下 $\Theta(n)$ 个额外边，复杂度 $\Theta(n2^k\alpha(n))$。

实际上大样例没跑过直接 Kruskal 的 $\Theta(nk2^k\alpha(n))$

考虑 $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|)$。

考虑王之钦定 trick。

$f_{i,\,j,\,k}$ 考虑了前 $i$ 个人，踢走了 $j$ 个，后面钦定 $k$ 个人 $c > j$ 且通过了面试。

转移讨论 $i$ 是不是在这 $k$ 个人里面，可以做到 $\Theta(1)$ 转移。