CSP-S 2025 第二轮比赛题解

零、背景

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

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

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

今天是 2025 年 11 月 2 日，CSP-S 第二轮算法比赛已于昨日结束；下面分享我的题解。

第一题，难度为普及+/提高，后悔贪心，难度还好，即使不会可以得到 70 分。
第二题，难度为提高+/省选−，剪枝或者多路合并，就会卡主不少人，不过可以得 80 分。
第三题，难度为省选/NOI−，哈希与 AC 自动机会简单一些，暴力可以得 80 分。
第四题，难度为省选/NOI−，三维动态规划，难度非常大，属于 noi 级别的题目了，暴力只能得 28 分。

这样看来，暴力可以得 70+80+80+28=258 分。

PS1：我觉得第四条应该有 NOI 级别了，毕竟即使是三维动态规划，还涉及到排列组合，太复杂了。
PS2：比赛pdf题目已经上传网盘，有需要的可以关注公众号号，回复 CSP-S-2025 获取。
PS3：后面我会基于这次比赛的题型，来展开介绍最小生成树、字符串、动态规划等相关算法专题。

一、社团招新（club）

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

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

最优解：后悔贪心

思路1：动态规划

状态定义：dp[i][j][k] 表示前 i 名新成员中，分配到部门 1 的人数为 j、分配到部门 2 的人数为 k 时的最大满意度（注意部门 3 的人数为 i - j - k）。

状态转移方程：第 i 个人枚举分配到哪个部门（下面用 j,k 表示部门 1/2 的人数，c 表示部门 3）：

// 假设 c = i - j - k
dp[i][j][k] = -INF; // 或者初始化为 -1 表示不可达
// 选择 A（部门1）
if (j > 0 && dp[i - 1][j - 1][k] != -1) {
  dp[i][j][k] = max(dp[i - 1][j - 1][k] + a1, dp[i][j][k]);
}
// 选择 B（部门2）
if (k > 0 && dp[i - 1][j][k - 1] != -1) {
  dp[i][j][k] = max(dp[i - 1][j][k - 1] + a2, dp[i][j][k]);
}
// 选择 C（部门3）
int c = i - j - k;
if (c > 0 && dp[i - 1][j][k] != -1) {
  dp[i][j][k] = max(dp[i - 1][j][k] + a3, dp[i][j][k]);
}

答案：枚举所有情况，求最大值。

for (int a = 0; a <= n; a++) {
  for (int b = 0; b <= n; b++) {
    ans = max(ans, dp[n][a][b]);
  }
}

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

特殊性质 A：a2 和 a3 全为 0 思路：在这种情况下只需从 a1 中选择最大的 n/2 个，其余分配为 0。得分：60 分

// 特殊性质 A: a2 和 a3 全为 0
if (sum2 == 0 && sum3 == 0) {  
  // a1 中选择最大的 n/2 个，其他选 0
  sort(a.begin(), a.end(), greater<tuple<ll, ll, ll>>());
  ll ans = 0;
  for (int i = 0; i < n / 2; i++) {
    ans += get<0>(a[i]);
  }
  printf("%lld\n", ans);
}

特殊性质 C：独立均匀随机生成思路：当样本是独立均匀随机生成时，直接对每个人选择三项中的最大值（不考虑 n/2 限制）通常能取得较好结果。得分：70 分

// 特殊性质 C：贪心选择
ll ans = 0;
for (auto& [a1, a2, a3] : a) {
  ans += max(a1, max(a2, a3));
}
printf("%lld\n", ans);

最优解：后悔贪心

根据容忍与鸽巢原理，可以得到几个性质。

性质1：最多有一个部门的人数超过 n/2（若两部门都超过 n/2，则两者之和 > n，矛盾）。性质2：如果将某个超过 n/2 的部门通过调整（按最小代价把多余成员转出）降到 n/2，则调整结束后不会让其他部门超过 n/2（因为总人数固定为 n）。

根据上面的两个性质，可以先贪心，在反悔贪心。

贪心：不考虑 n/2 限制，贪心选择最大值。
反悔：对于超过 n/2 的人，选择一些返回选择这个部门，改为选择其他部门（选择哪个不重要，根据性质2其他部门不会超过限制）。

所以这里就需要决策哪些人反悔。

定义反悔代价：假设当前部门的满意度是 a1，另外两个部门的满意度是 a2 和 a3，那么反悔代价就是 a1 - max(a2, a3)。

显然，需要选择反悔代价最小的那些人，直到该部门人数不超过 n/2。
复杂度：O(n log(n))
得分：100 分

vector<ll> g[3];
// g[0].push_back(a1 - max(a2, a3));
// 输入与贪心选择，代码省略

// 后悔贪心, 找到超过 n/2 的部门 i
int sz = g[i].size();
sort(g[i].begin(), g[i].end());
for (int j = 0; j < sz - n / 2; j++) {
  ans -= g[i][j];
}

二、道路修复（road）

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

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

最优解：最小生成树+剪枝

思路1：暴力枚举

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

关于如何枚举所有子集，我之前在《动态规划》文章的状态压缩小节介绍过。

const int MASK = (1 << k) - 1;
for (int sub = MASK; sub; sub = (sub - 1) & MASK) {
  townSelectEdges = baseEdges;
  ll subCost = 0;
  int selectNum = 0;
  for (int i = 0; i < k; i++) {
    if ((sub >> i) & 1) {
      selectNum++;
      // 选择第 i 个乡镇
      subCost += townCosts[i];
      townSelectEdges.insert(townSelectEdges.end(), 
                             townEdgeCosts[i].begin(),
                             townEdgeCosts[i].end());
    }
  }
  sort(townSelectEdges.begin(), townSelectEdges.end());
  ll totalCost = MinimumSpanningTree(selectNum, subCost, townSelectEdges);
  ans = min(ans, totalCost);
}

复杂度：O(2^K * (M + K*N) * log(E))
得分：56 分（逆天，暴力的分数竟然这么高）

优化1：原图中的边集合优化

显然，加入乡村后，原图的最小生成树未被选择的边，以后也永远不会被选择。
即只有最小生成树的边，未来才会被选择。

所以，第一次求最小生成树时，可以记录下被选中的边。
枚举乡村时，直接使用被选中的边，边的数量就会从 M 降低到 N-1。

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

const int MASK = (1 << k) - 1;
for (int sub = MASK; sub; sub = (sub - 1) & MASK) {
  townSelectEdges = selectEdges;
}

优化2：乡镇的边集合优化
假设原图最小生成树的最大边权为 maxW。
乡镇新增边中权重大于 maxW 的边显然不会被选入最终最优解，因此可以剪枝过滤这些边。

证明：假设答案生成树中存在这样一个边权 maxW + ε（ε>0）。
删除这个乡镇的边权后，答案生成树就变成两个联通分支。
之后，可以在原图最小生成树的边集合中，选择某个边，使得两个联通分支连通，从而得到更小的生成树。
故，假设不成立，不存在这样的边权。

有了这个性质后，可以在枚举乡镇时，直接过滤掉大于 maxW 的边。
复杂度：O(2^K * (N + K*E') * log(E'))，其中 E' 是过滤后的边数。
得分：100 分

PS: 可以发现，数据比较弱，这个边权优化并没有降低最坏复杂度，但是可以拿到满分了。

const int MASK = (1 << k) - 1;
for (int sub = MASK; sub; sub = (sub - 1) & MASK) {
  baseEdges.clear();
  ll subCost = 0;
  for (int i = 0; i < k; i++) {
    if ((sub >> i) & 1) {
      // 选择第 i 个乡村
      subCost += townCosts[i];
      for (int j = 0; j < n; j++) {
        auto [w, v] = townEdgeCosts[i][j];
        int u = n + i;
        if (w > maxEdge) break;      // 剪枝优化
        baseEdges.push_back({w, u, v});
      }
    }
  }
  sort(baseEdges.begin(), baseEdges.end());
  ll totalCost = MinimumSpanningTree(subCost, baseEdges);
  ans = min(ans, totalCost);
}

优化3：多路合并最小堆

上面复杂度比较高的原因是我们需要合并原树与 k 个乡村的边集，然后排序。
最后才能从小到大遍历这些边，通过并查集来计算出最小生成树。

如果我们能不合并也能从小到大遍历这些边呢？

多个集合，如何快速选出一个最小值？
这不就是文件的多路排序吗？

具体来说，每个集合预处理保证有序。
假设当前选择了 k 个乡镇，维护一个大小为 k+1 的最小堆，堆的值为 {w, listIndex, listOffset}，表示第 listIndex 个集合的第 listOffset 个元素，值为 w。

好吧，这个优化最坏复杂度依旧没有降低。
不过少了合并与排序，常数会降低的比较低。

min_queue<tuple<ll, int, int>> que; // {w, listIndex, listOffset}
//多路合并，每次弹出堆顶元素，并将对应集合的下一个元素加入堆
tuple<ll, int, int> PopQue() {
  const auto [w, k, index] = que.top();
  que.pop();
  int edgesSize = townEdgeCosts[k].size();
  if (index + 1 < edgesSize) {
    que.push({get<0>(townEdgeCosts[k][index + 1]), k, index + 1});
  }
  return townEdgeCosts[k][index];
}

// 基于多路合并的最小生成树
ll MinimumSpanningTree(ll cost) {
  dsu.Init(n + K);
  int groupNum = n + K;
  while (!que.empty()) {
    auto [w, u, v] = PopQue();
    if (dsu.Find(u) != dsu.Find(v)) {
      groupNum--;
      dsu.Union(u, v);
      cost += w;
    }
    if (cost >= ans || groupNum == 1) {
      return cost; // 剪枝
    }
  }
  return cost;
}

三、谐音替换（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} 的不同方案数。

方案数定义：
两种替换方案不同，当且仅当：被替换的子串 y 的起始位置不同。
用于替换的二元组 (s_{i,1}, s_{i,2}) 的下标 i 不同。

最优解：AC自动机+哈希
PS: 据说也可以 Trie+哈希，后面我研究下在分享。

首先是理解题意并进行预处理，分析之后，可以发现，每个二元组可以拆分为三部分：前缀A + 替换部分B + 后缀C。
其中前缀A和后缀C是不变的，只有替换部分B会变化。

此时可以发现，不可能存在相同的方案数。
因为如果一个二元组可以发生替换，替换的位置是固定的，这已经满足二元组下标不同的要求了。

二元组如何分组呢？
可以发现，替换部分的二元组 {B-S1， B-S2} 是用来分组的唯一标识。
字符串操作成本比较大，所以可以合并后使用哈希值作为标识。

unordered_map<ll, vector<pair<A, B>>> mp;
ll h = hash("B-S1", "$", "B-S2");
mp[h].push_back({A, C});  

之后，对于每个询问二元组 T1, T2，先拆分为 TA, TB, TC。
然后合并替换比分计算出哈希值 h，在 mp 中找到对应的分组。

这时候，需要找到所有的二元组 {SA,SC}，使得 SA 是 TA 的后缀，SC 是 TC 的前缀。

两个子串不方便匹配，所以一般使用特殊字符连接后匹配。

这个时候，带匹配的二元组就是 SA#SC，带匹配的查询串就是 TC#TA，需要询问 SA#SC 是否是 TC#TA 的子串。

子串问题，可以使用 kmp 来做。
一次匹配复杂度为 O(|TC| + |TA| + |SA| + |SC|)。
总复杂度为 O(Q * (|TC| + |TA|) + Σ(|SA| + |SC|))。
得分：75 分

// 设 text 为构造的查询串（例如 text = TA + "#" + TC）
ll res = 0;
for (const string& pat : mp[h]) {
  if (KMP::kmp(text.c_str(), pat.c_str(), pat.length()) != -1) {
    res++;
  }
}
printf("%lld\n", res);

可以发现，匹配时对 SA#SC 重复计算了很多次 next 数组。
所以可以预处理所有 SA#SC 的 next 数组。
得分：80 分。

// 使用预处理过的 next 数组进行匹配（text 为查询串）
ll res = 0;
for (const auto& [pat, nextVec] : mp[h]) {
  if (KMP::kmp(text.c_str(), pat.c_str(), pat.length(), nextVec) != -1) {
    res++;
  }
}
printf("%lld\n", res);

PS：直接使用 strstr 竟然也是 80 分。

vector<string>& patterns = mp[h];
ll res = 0;
for (const string& pat : patterns) {
  if (strstr(text.c_str(), pat.c_str()) != nullptr) {
    res++;
  }
}
printf("%lld\n", res);

多模式匹配，其实就是 AC 自动机的模版题，直接套 AC 自动机模版即可。
得分：100 分。

scanf("%d%d", &n, &q);
for (int i = 0; i < n; i++) {
  scanf("%s%s", s1, s2);
  int len = strlen(s1);
  ll h = MergeS1S2(len);
  if (ACIndex.count(h) == 0) {
    ACIndex[h] = AC::NextNode(); // 创建一个 AC 自动机
  }
  // 插入 AC 自动机（插入构造出来的 pattern，例如 pattern = SA + "#" + SC）
  // string pattern = SA + "#" + SC;
  AC::insert(ACIndex[h], pattern.c_str());
}

// 构建 AC 自动机
for (auto& [_, root] : ACIndex) {
  AC::build(root);
}

// q 个询问
while (q--) {
  scanf("%s%s", s1, s2);
  int len1 = strlen(s1);
  int len2 = strlen(s2);
  if (len1 != len2) {
    printf("0\n");  // 长度不同，直接输出 0
    continue;
  }
  ll h = MergeS1S2(len1);
  if (ACIndex.count(h) == 0) {
    printf("0\n");  // 不存在该模式串，直接输出 0
    continue;
  }
  int root = ACIndex[h];
  // text 为查询串，例如 text = TA + "#" + TC
  ll res = AC::query(root, text.c_str());
  printf("%lld\n", res);
}

四、员工招聘（employ）

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

面试会持续 n 天，每天面试一个人，而小 Z 需要决定这 n 个人的面试顺序。
小 H 准备了 n 套面试题，题目的难度是固定的（由一个 n 长度的字符串 s 决定），其中 ‘1’ 代表简单（所有应聘者都能做出并被录用），’0’ 代表困难（所有应聘者都做不出并被拒绝）。

关键在于应聘者的耐心：每个人 i 有一个耐心上限 c[i]。
如果在他来面试之前，已经被拒绝或放弃面试的人数达到了 c[i]，那么这个人就会直接放弃面试。

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

最优解：动态规划。

这道题是一个复杂的计数问题，涉及排列、组合和动态约束条件（耐心上限）。

思路1：暴力排列组合
得分： 8分

vector<int> P;  // 排列，标记是否选择
ll Dfs(int p, int cnt) {  // cnt 代表之前已经选择了 cnt 个员工
  if (p == n + 1) {
    return cnt >= m ? 1 : 0;
  }

  ll ret = 0;
  const int c = (p - 1) - cnt;    // 前 p-1 天中未被录用的人数（即已被拒绝或放弃的人数）
  for (int i = 1; i <= n; i++) {  // 第 p 天选择一个员工
    if (P[i] == 0) {              // 员工 i 未被选择，尝试选择
      P[i] = 1;                   // 选择员工 i
      if (S[p] == '1' && c < C[i]) {
        ret += Dfs(p + 1, cnt + 1);
      } else {
        ret += Dfs(p + 1, cnt);
      }
      P[i] = 0;  // 回溯，取消选择员工 i
    }
  }
  return ret;
}

if (n <= 10) {
  P.resize(n + 1, 0);
  ans = 0;
  Dfs(1, 0);
  printf("%lld\n", ans);
  return;
}

特殊性质 A: 对于所有 i，均有 s[i]=1。
思路：全排列，都是答案
得分： 12 分

PS: 有三组 case，其他组存在 C[i] 为 0，所以只得到一组的分。

if (sum == n) {
  // 特殊性质 A: 对于所有 i，均有 s[i]=1。
  ans = 1;
  for (int i = 1; i <= n; i++) {
    ans = (ans * i) % Comb::mod;
  }
  printf("%lld\n", ans);
  return;
}

贪心：如果必然未录取的员工不足 m 个，直接返回 0。
得分：16 分

// 这里 C0 与 sum 在实现中需要提前计算：
// C0: 已确定不会被录取的人数（例如耐心为 0 的人）；
// sum: S 中 '1' 的数量（即可能被录取的人数）。
if (n - C0 < m || sum < m) {
  printf("0\n");
  return;
}

性质：n=18，显然可以使用状态压缩。

状态定义：dp[day][mask][nopass] 表示在第 day 天，选择的员工集合为 mask，且已有 nopass 人未通过/已参与面试的方案数。
得分：28 分。

状态转移方程：枚举第 i 天的员工的结果。

int dp[19][1 << 18][19];

int Dfs(int day, int mask, int nopass) {  //
  // 状态记忆与出口...
   
  ret = 0;
  // 枚举第 day 天选择的员工
  for (int i = 0; i < n; i++) {
    if (mask & (1 << i)) {                   // 员工 i 被选择
      const int prevMask = mask ^ (1 << i);  // 去掉员工 i
      int prevNoPass = nopass;
      if (S[day] == '0') {  // 这天不可能招聘通过
        ret = (ret + Dfs(day - 1, prevMask, prevNoPass - 1)) % Comb::mod;
      } else {
        if (prevNoPass < C[i + 1]) {  // 假设这名员工通过
          ret = (ret + Dfs(day - 1, prevMask, prevNoPass)) % Comb::mod;
        }
        if (prevNoPass > 0 && prevNoPass - 1 >= C[i + 1]) { // 假设这名员工未通过
          ret = (ret + Dfs(day - 1, prevMask, prevNoPass - 1)) % Comb::mod;
        }
      }
    }
  }

  return ret;
}

if (n <= 18) {
  ll ans = 0;
  memset(DP::dp, -1, sizeof(DP::dp));
  for (int pass = m; pass <= n; pass++) {
    ans = (ans + DP::Dfs(n, (1 << n) - 1, n - pass)) % Comb::mod;
  }
  printf("%lld\n", ans);
  return;
}

总结

针对 n=10的 case ，可以使用暴力排列组合。
针对 n=18的 case ，可以使用状态压缩动态规划。
针对必然没答案的情况，可以直接返回 0。
针对 s[i]=1 的特殊情况，可以直接计算全排列。
针对其他情况，n=500，显然需要三维动态规划。

三维动态规划比较复杂，我还在想怎么介绍，后面会单独写一篇文章介绍这道题的三维动态规划。

五、最后

这次比赛还是比较难的。

第一题，后悔贪心，难度还好，即使不会可以得到 70 分。
第二题，剪枝或者多路合并，就会卡主不少人，不过可以得 80 分。
第三题，哈希与 AC 自动机会简单一些，暴力可以得 80 分。
第四题，三维动态规划，难度非常大，属于 noi 级别的题目了，暴力只能得 28 分。
这样看来，暴力可以得 70+80+80+28=258 分。

《完》

-EOF-

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

本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。