CSP-S 2025 题解

· · 个人记录

推荐做题时长：2 小时。

T1 club

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

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

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

T2 road

观察 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)) 的。

T3 replace

首先，我们需要特殊处理 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)。

经过大手子指出，到根链查询直接暴力就可以 \mathcal O(L) 了，所以复杂度线性。

T4 employ

只有 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)。