CSP-S 2025 题解

观察：不可能有两个社团同时超过 $\frac{n}{2}$。

因此可以先贪心为每个人找到最大值分配。对于超过的那个社团，我们要将其中一部分人改成第二大值，因此根据 第二大 - 第一大 从大到小排序修改即可。

时间复杂度 $\mathcal O(n\log n)$。

观察 1：$m$ 条边中，只有在最小生成树上的 $n - 1$ 条边有用。

观察 2：对于一个选择改造的乡镇，它一定会连接所有出边中边权最小的一条。

证明：假设我们先固定了原图中的所有边。假设这个乡镇连接了 $A, B$ 两个连通块。如果最小边是和 $A, B$ 中的点连接的，那么把原来一条边断掉换成这条最小边不会影响连通性；如果最小边是在另一个连通块 $C$ 中的，那么必定有另一个乡镇连接了 $C$ 和 $A, B$ 中的一者。这时候不如断开 $A, B$ 中一个，替换成和 $C$ 的连接。

因此可以对于 $k$ 个乡镇，先将所有边排序。枚举 $2^k$ 种改造方案，那么就有 $\mathcal O(nk)$ 条可以使用的边。因为已经固定了和最小边连通，所以可以跑最小生成树。用多路归并可以做到 $\mathcal O(2^knk\alpha(n))$，已经可以通过。

更优秀的做法是，考虑用一个 dfs 的过程去枚举所有状态，维护一个 $n - 1$ 条边的最优解。那么加入一个新点就只需要对 $\mathcal O(n)$ 条边归并。这样做复杂度是 $\mathcal O(2^kn\alpha(n))$ 的。

首先，我们需要特殊处理 $s_1=s_2$ 以及 $|t_1|\neq |t_2|$ 的情况。

观察：我们找到最短的一段子区间 $[l, r]$，包含所有 $t_{1, i} \neq t_{2, i}$ 的位置。那么替换的串一定包含 $[l, r]$。

如果我们对于 $s$ 也找出相应的区间。那么 $s_{1}[l_s, r_s]=t_{1}[l_t,r_t],s_2[l_s,r_s]=t_2[l_t,r_t]$。

因此可以先用哈希对所有的 $s$ 二元组分类，查询时找到对应的类别。那么问题就变成了要求去掉 $[l, r]$ 后，$s_1,t_1$ 的前后缀分别可以匹配。

这里可以感受到前后缀是比较独立的。因此考虑对于每种类别，前后缀分别开一棵 trie 树。查询时，假设 $t_1$ 的前后缀分别对应两棵树上的 $u_1,u_2$，那么答案即为 $root_1\to u_1$ 的链上有多少个 pair 的另一个点在 $root_2\to u_2$ 的链上。

离线处理询问，把对应的点挂在第一棵树上。dfs 一遍第一棵树，用数据结构维护第二棵树，问题转化为单点加，到根链查询，用树状数组维护 dfs 序即可。复杂度 $\mathcal O((n + q)\log L + L)$。

只有 $s_i = 1$ 的位置可能被录取。

考虑特殊性质 B。我们枚举 $2^{18}$ 种情况，计算恰好这些位置是被录取者的方案数。

对于每个位置，我们可以得知前面的人当中，有几个人没被录取（$s_i = 0$ 一定不被录取，$s_i = 1$ 可以根据枚举的状态计算），设为 $p_i$。那么要求无非是 $c_j > p_i$ （被录取）或 $c_j \le p_i$（不被录取）。

如何计算一些限制大于或小于关系的方案数？如果只有小于号，问题变得容易，因为我们可以由紧到松考虑限制，那么方案数就是每个位置的选择数之积。

我们设法解决掉大于号。考虑容斥，钦定一部分大于号必须违反，也就是他们也被修改成了小于等于号，每个被钦定的位置提供 $(-1)$ 的系数；其余的大于号不再有限制，也就是可以随意放。这样的一个状态依旧满足所有有限制的 $p_i$ 是递增的，因此可以直接计算出答案。

枚举所有的容斥组合过于缓慢。可以考虑 dp：设 $f_{i, j}$ 表示目前考虑到前缀 $i$，有 $j$ 个已经确定的限制。如果当前的人被录取，可以选择容斥或跳过；如果没被录取，只能立即选择一个对应的面试者。最后需要乘上 $(n-j)!$，因为这些人可以随意排列。

如果没有性质 B 了，我们无非是再套上一层 dp：设 $f_{i, j, k}$ 表示前 $i$ 个人，录取了 $j$ 个人，已经确定了 $k$ 个限制。转移同样分类是 $s_i = 0$，录取，还是不录取。

时间复杂度 $\mathcal O(n ^ 3)$。