CSP-S 2025 完整版题解（含源码与官方测试数据）

零、背景

目前我已经做了历年 CSP-J/S 的所有常规算法题目。
CSP-J 题解：2025、2024、2023、2022、2021、2020、2019。
CSP-S 题解：2025、2024、2023、2022、2021、2020。

后来对历年题型做了总结，《CSP-J 题型分析》和《CSP-S 题型分析》。

最后也分享了备考策略与常见算法，如
备考策略：得分技巧、环境准备。
常见算法：二分、线段树、状态最短路、动态规划、数学、常见算法和数据结构。

今天 CSP-S 的官方测试数据终于出来了，这里分享下完整版题解。

PS： CSP-J 和 CSP-S 的题目与所有官方测试数据已经上传到网盘，各种题解的源码也上传到网盘，有需要的可以关注公众号，回复 CSP-2025 获取。

阅读指引：本文按每道题给出「题意→多种算法思路→复杂度与得分→小结图」，必要处补上符号约定与动机，便于完整复现与对比优化路径。

一、社团招新（club）

题意：我们学校的算法协会招募了 n 名新成员，其中 n 是一个偶数。
现在需要将这些新成员分配到协会的三个部门中。
每个新成员对这三个部门都有一个满意度得分。

我们的目标是找到一个分配方案，使得所有成员的满意度之和最大。
但是，分配有一个限制条件：任何一个部门分配到的新成员数量都不能超过 n/2。
简而言之，就是要在限制每个部门人数不超过总人数一半的前提下，最大化总满意度。

算法1：当 n ≤ 200 时的动态规划

状态定义：dp[i][j][k] 表示前 i 名新成员中，分配到部门 1 的人数为 j、分配到部门 2 的人数为 k 时的最大满意度（部门 3 的人数为 i - j - k）。
状态转移方程：枚举第 i 个人分别分配到三个部门的情况。

复杂度：O(n^3)
得分：55 分

算法2：特殊性质 A（仅第一部门有分）
思路：当对所有人有 a[i][2] = a[i][3] = 0 时，只需在 a[*][1] 中选择最大的 n/2 个分配到部门 1，其余分配到其他部门（贡献为 0）。
得分：60 分

算法3：特殊性质 C（独立均匀随机生成）
思路：随机生成的数据下，每人三项满意度的最大值在三个部门间会“平均地”分布（各约 1/3）。直接把每人分配给其最大满意度的部门，再做必要调整通常即可。
得分：70 分

算法4：后悔贪心（标准解法）。

思路：先把每人分配到其满意度最大的部门，然后在超限的部门中“挪人”。
挪动优先级由“后悔代价”决定：把某人从当前部门改到其次优部门所造成的满意度损失，越小越优先调整。
按后悔代价排序，依次把代价最小的人调整出去，直到所有部门人数都不超过 n/2。

复杂度：O(n log n)
得分：100 分

总结

二、道路修复（road）

题意：我们有一个由 N 个城市和 M 条双向道路构成的交通系统。
最初，所有 M 条道路都已损坏，修复第 i 条道路的费用是 w_i。
此外，还有 K 个乡镇可以进行城市化改造。对第 j 个乡镇进行城市化改造的费用是 c_j。
改造后，可以在该乡镇和原有的 N 个城市之间修建道路，乡镇 j 到城市 i 的修建费用是 a_{j,i}。

我们的目标是：选择任意多个乡镇进行城市化改造（可以选择 0 个）。
修复一些原有道路，并修建一些新的乡镇-城市道路。
最终使得原有的 N 个城市两两连通。
求出达成这一目标的最小总费用（乡镇改造费 + 道路修复/新建费）。

算法1：暴力枚举

思路：暴力枚举所有乡镇的选择方案，合并所有边，排序，最后求最小生成树。

复杂度：O(2^K * (M + K * N) * log(E))
得分：40 分

算法2：特殊性质 A

PS：该类测试数据存在描述与实际不一致。
题面称特殊性质 A 中乡镇的“点和边”均为 0，实际数据是“点为 0、边非 0”。

思路：乡镇改造费用为 0，因此可以把任意乡镇先视为“免费可用”的中介点；任意两个城市都可以通过“城市→乡镇→城市”的两条边连通。

if (hasAllZeroCAndA) {
  baseEdges.reserve(m + k * n * n);
  for (int x = 0; x < k; x++) {
    for (int y = 0; y < n; y++) {
      for (int z = 0; z < n; z++) {
        baseEdges.push_back({townEdgeCosts[x][y] + townEdgeCosts[x][z], y, z});
      }
    }
  }
}

复杂度：O((M + K * N^2) * log(E))
得分：52 分

算法3：只合并原图 MST 的边
思路：先求原图的 MST，然后只合并 MST 的边和乡镇相关的边，最后求 MST。
复杂度：O((N + K * N) * log(E))
得分：80 分

算法4：只合并乡镇小于 MST 最大边权的边
思路：先求原图的 MST，记录最大边权 maxW，然后只合并乡镇相关且边权小于 maxW 的边，最后求 MST。
复杂度：O((N + K * N) * log(E))
得分：100 分

算法5：多路排序
思路：利用多路排序优化边的合并过程。
复杂度：O((N + K * N) * log(E))
得分：100 分

总结

三、谐音替换（replace）

题目：小 W 作为一名语言学爱好者，将“谐音替换”现象抽象成一个字符串问题。
核心操作是：给定 n 种替换规则 (s_{i,1}, s_{i,2})，其中 s_{i,1} 和 s_{i,2} 长度相等。
对于一个字符串 s，如果它的一个子串 y 等于某个 s_{i,1}，就可以将这个子串 y 替换成对应的 s_{i,2}，从而得到一个新的字符串 s'。

目标是：回答 q 个询问，每个询问给定两个不同的字符串 t_{j,1} 和 t_{j,2}，求 t_{j,1} 经过恰好一次替换得到 t_{j,2} 的不同方案数。

记一条规则为 (s1, s2)（长度相等），一次询问为 (t1, t2)（不同字符串）。
s1 可以分为三部分：公共前缀 A、替换段 B、公共后缀 C；
s2 分为：公共前缀 A、替换段 D、公共后缀 C。
(t1, t2) 也类似：t1 分为 AA、B、CC；t2 分为 AA、D、CC。

要想满足替换条件，首先必须满足规则对与询问对的替换片段一致，即 (s1, s2) 的 B->D 与 (t1, t2) 的 B->D 相同。
所以，可以根据 B->D 来对数据进行分组。

分组后， (s1, s2) 转化为了 (A, C)，(t1, t2) 转化为了 (AA, CC)。

此时，要满足替换条件，A 必须是 AA 的后缀，C 必须是 CC 的前缀（长度可为 0）。

所以，问题转化为了： 对于每个询问 (AA, CC)，统计有多少个 (A, C) 满足 A 是 AA 的后缀，C 是 CC 的前缀。

算法1：KMP/子串暴力查询
思路：将 (A,C) 二元组拼为 A#C，将 (AA,CC) 拼为 AA##CC，逐个判断 A#C 是否是 AA##CC 的子串（可用 KMP 或直接 strstr）。
复杂度：O(n * L)。

ll res = 0;
for (const string& pat : patterns) {
  if (strstr(s3, pat.c_str()) != nullptr) {
    res++;
  }
}
printf("%lld\n", res);

算法2：AC 自动机解法回顾
思路：算法1已经转化为了 n 个模式串匹配 q 个查询串的问题，直接用 AC 自动机解决。
复杂度：O(n * L)。
补充：假设每次都全部匹配，答案就是 q*n 个，最坏情况下复杂度是 O(q*n)，可能会 TLE。

while (q--) { // q 个询问
  // text 为查询串，例如 text = TA + "#" + TC
  ll res = AC::query(root, text.c_str());
  printf("%lld\n", res);
}

算法3：Trie 树

思路：把左边串取“后缀判定”转为“前缀判定”：将 A 与 AA 先翻转后插入字典树 Trie1（用以判断“是否为后缀”）；把右边的 C 与 CC 直接插入字典树 Trie2（判断“是否为前缀”）。
问题就转化为：统计有多少个 (A, C) 满足 A 在 Trie1 上位于 AA 的根路径上，且 C 在 Trie2 上位于 CC 的根路径上。
这个是典型的二维数点问题，使用扫描线把二维转化为一维问题，然后使用树状数组解决。
复杂度：O(L * log(L))。

详细介绍可以参考文章《CSP-S 2025 第三题字典树 Trie 解法》。

总结

四、员工招聘（employ）

题意：想象一下小 Z 和小 H 正在招聘员工。一共有 n 个人来应聘，他们希望至少能录用 m 个人。

面试会持续 n 天，每天面试一个人，而小 Z 需要决定这 n 个人的面试顺序。
小 H 准备了 n 套面试题，题目的难度是固定的（由一个长度为 n 的字符串 s 决定），其中 '1' 代表简单（当轮来面试者必过并被录用），'0' 代表困难（当轮来面试者必挂）。下文公式中用 S 表示该难度串，S[i] 为第 i 天的难度。

关键在于应聘者的耐心：每个人 i 有一个耐心上限 c[i]。
如果在他来面试之前，已被拒绝或放弃面试的人数“达到或超过” c[i]，那么这个人会直接放弃面试。等价地，要想还能被安排上场，必须有 c[i] > 已挂人数。

目标： 找出有多少种不同的面试顺序（即 1∼n 的排列 p）能够最终录用至少 m 个人。
答案需要对 998244353 取模。

算法1：n<10 暴力排列组合
思路：暴力枚举所有排列组合，模拟面试过程，统计合法方案数。
复杂度：O(n!)。
得分：8 分。

算法2：特殊性质 A，对于所有 i，均有 s[i]=1。
思路：所有人都能被录用，直接贪心计算排列数。
复杂度：O(n)。
得分：8 分。
补充：当存在 c[i]=0 时，上述贪心并不成立；而测试数据中包含此类情况，因此该思路实际不得分。

算法3：显然无解时，直接输出 0
思路：若无论如何最多能录用的人数小于 m，则直接返回 0。
复杂度：O(n)。
得分：12 分。

算法4：动态规划状态压缩
思路：dp[day][nopass][mask] 表示在第 day 天，选择的员工集合为 mask，且已有 nopass 人未通过的方案数。
复杂度：O(n * 2^n * n)。
得分：28 分。

详细介绍见《CSP-S 2025 第二轮比赛题解》。

算法5：三维动态规划

算法4也算是三维动态规划，但是第二个状态是员工集合 mask，导致复杂度爆炸。
n 最大为 500，显然需要抽象为如下的状态 dp[day][nopass][X]，其中 X 是一个不大于 n 的整数。

状态的含义是：在第 day 天已有 nopass 人未通过的方案数里根据 X 进行划分若干个子方案数。

分析状态之间的关系：d[day][nopass][] 与 d[day+1][][] 之间的关系。
为了能够发现规律，这里先看特殊性质 A，所有 S[i]都是 1。

此时，下一天那个人是否录用，只与当前已有 nopass 有关。
如果 c > nopass，则该员工仍会参加当前轮面试（根据 S 的当前位是否为 '1' 决定过/挂）；若 c ≤ nopass，则该员工已放弃，不能被选。
所以，X 的含义是已选择的 i 个人里，有 X 个人的 c > nopass。

完整状态定义:dp[day][nopass][X] 表示在第 day 天，已有 nopass 人未通过且已选择的 day 个人里有 X 个人的 c > nopass 的方案数。

trick：只有 nopass 变化时，才计算“耐心值小于等于 nopass 的人数”的排列/组合贡献。

如果下个人录用，需要选择耐心值“严格大于” nopass 的员工；此时 nopass 不变，不需要计算排列组合数。

dp[day + 1][nopass][X + 1] += dp[day][nopass][X];

如果下个人不录用，说明选择的是耐心值“≤ nopass”的员工，此时 nopass 增加 1，需要计算排列/组合贡献。
其中 (pre[nopass] - (day - nopass)) 代表待选择的耐心值小于等于 nopass 的员工数。

nopass 加 1 后，新的状态是 dp[day+1][nopass+1][?]。
显然，之前已选择的耐心值等于 nopass+1 的员工，需要从 X 中减去。
具体数量未知，因此需要枚举。

for (int t = 0; t <= min(X, c[nopass + 1]); t++) {  // 选择 t 个耐心值等于 j+1 的人
  dp[day + 1][nopass + 1][X - t] += dp[day][nopass][X] * (pre[nopass] - (day - nopass)) * ?;
}

? 代表排列/组合项：从“耐心值等于 nopass+1 的人”里选出 t 个，且这 t 个在“当前可放入的位置”（大小为 X 的集合）中的排列数。

? = C(c[nopass + 1], t) * P(X, t);

至此，特殊性质 A 的状态转移就完成了。

当 S[day+1] = '0' 时，状态转移与上面类似。
由于 S[day+1] 是必败，所以 nopass 会增加 1，仍需枚举 t 个耐心值等于 nopass+1 的员工。

同样，还是分两种情况。
选择小于等于 nopass+1 的员工，则 X = X - t。
选择大于 nopass+1 的员工，则 X = X - t + 1。

for (int t = 0; t <= min(X, c[nopass + 1]); t++) {  // 枚举之前 X 个人中，有多少个耐心值等于 nopass+1
  // 情况1：选择 <= nopass+1 的人，此时 X 变为 X - t
    dp[day + 1][nopass + 1][X - t] += dp[day][nopass][X] * (pre[nopass + 1] - (day - X + t)) * ?;
  // 情况2：选择 > nopass+1 的人，此时 X 变为 X - t + 1
  dp[day + 1][nopass + 1][X - t + 1] += dp[day][nopass][X] * ?;
}

其中 pre[nopass + 1] - (day - X + t) 表示：在“未被选过的人”中，耐心值 ≤ nopass+1 的人数；? 的含义与之前一致。

最终状态是 dp[n][nopass][X]。由于“耐心值大于 nopass 的人”的排列尚未计入，因此需再乘上 P(n - nopass, X)。

dp[0][0][0] = 1;
for (int i = 0; i < n; i++) {
  for (int j = 0; j <= i; j++) {
    for (int k = 0; k <= i; k++) {
      if (S[i + 1] == '1') {
        // 下个人不挂，耐心值 C[i] 需要严格大于 j。j 不变，所以不需要计算排列数
        dp[i + 1][j][k + 1] += dp[i][j][k];
        // 下个人挂，耐心值 C[i] 需要小于等于 j，即在耐心值为 [0, j] 之间选择 1 人
        // 枚举 k 个耐心值大于 j 的人中，有多少个耐心值等于 j+1
        if (pre[j] >= i - k) {
          for (int t = 0; t <= min(k, c[j + 1]); t++) {  // 选择 t 个耐心值等于 j+1 的人
            dp[i + 1][j + 1][k - t] += dp[i][j][k] * (pre[j] - (i - k)) * C(c[j + 1], t) * A(k, t);
          }
        }
      } else {  // S[i+1]='0'，下个人不管如何选择，必挂
        // 必挂，j 需要加 1
        for (int t = 0; t <= min(c[j + 1], k); t++) {  // 枚举之前 k 个人中，有多少个耐心值等于 j+1
          // 情况1：选择 <= j+1 的人，此时 k 变为 k - t
          if (pre[j + 1] >= i - k + t) {
            dp[i + 1][j + 1][k - t] += dp[i][j][k] * (pre[j + 1] - (i - k + t)) * C(c[j + 1], t) * A(k, t);
          }
          // 情况2：选择 > j+1 的人，此时 k 变为 k - t + 1
          dp[i + 1][j + 1][k - t + 1] += dp[i][j][k] * C(c[j + 1], t) * A(k, t);
        }
      }
    }
  }
}

mint ans = 0;
for (int j = 0; j <= n - m; j++) {  //  挂 j 个人，大于等于 j 的人数是 n - pre[j]
  int k = n - pre[j];
  ans += dp[n][j][k] * fac[k];
}
printf("%lld\n", ans.x);

算法6：滚动数组
思路：观察状态转移方程，发现 day 只与 day-1 有关，可以使用滚动数组优化空间（把第一维消掉）。
复杂度：O(n^3)。
得分：100 分。

注：文中记号 A(x, y) 在代码里常用作“排列数”的写法，与 P(x, y) 等价；pre[j] 表示满足 c ≤ j 的人数前缀统计。

总结

五、最后

这次比赛还是比较难的。

如果我参加这次比赛，前两道题可以拿满分，第三题只能拿到 KMP 暴力匹配的40分，第四题可能只能拿到状态压缩的28分。
合起来最高得分是 268 分。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code