CSP-J 2025 第二轮比赛题解

零、背景

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

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

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

今天是 2025年11月1日，CSP-J 第二轮算法比赛已经结束了，我来分享一下比赛的题解。

PS：比赛pdf题目已经上传网盘，有需要的可以关注公众号号，回复 CSP-J-2025 获取。

一、拼数（number）

题目：给一个至少包含一个正整数的字符串，问选择一些数字，可以组成的最大数是多少？

思路：贪心

想要数字最大，显然是选出所有数字，大的在前面，小的在后面。
所以我们只需要从字符串中提取出所有数字，然后排序输出即可。

注意事项：正常情况下需要考虑数字前导零的问题，但本题无需担心——题目保证字符串中至少有一位非零数字，因此降序排列后首位必为非零。

小技巧：C++ 中字符串排序后是从小到大排列的，我们可以先排序再反转，或者使用 greater 进行排序。

空间优化技巧：由于 dp[i][j] 只和 dp[i-1][j] 有关，所以我们可以参考 0/1 背包的做法，将 dp 数组压缩为一维。

const int maxn = 1e6 + 10;
char str[maxn];
void Solver() {  //
  string ans;
  scanf("%s", str);
  int len = strlen(str);
  for (int i = 0; i < len; i++) {
    char c = str[i];
    if (c >= '0' && c <= '9') {
      ans.push_back(c);
    }
  }
  sort(ans.begin(), ans.end());
  std::reverse(ans.begin(), ans.end());
  printf("%s\n", ans.c_str());
}

二、座位（seat）

题意：给你 n*m 个学生乱序的成绩表，其中每个学生有一个独立无二的成绩。
现在要把学生按成绩从高到低排成 n 行 m 列的座位表。
要求 S 形排列，即第一列从上到下，第二列从下到上，第三列从上到下，依此类推。
问成绩表中第一个学生在排好序的座位表中处于什么位置？

思路：排序 + 模拟/数学计算

显然，我们需要先对成绩表进行排序，然后根据 S 形排列的规则计算出第一个学生的位置。

这里有两个方法：

第一个方法是模拟法：直接模拟 S 形排列的过程，找到第一个学生的位置。

const int x = a[0];
sort(a.begin(), a.end());
std::reverse(a.begin(), a.end());
int index = 0;
for (int col = 1; col <= m; col++) {
  if (col % 2 == 1) {  // 从上到下
    for (int row = 1; row <= n; row++) {
      g[row][col] = a[index++];
    }
  } else {  // 从下到上
    for (int row = n; row >= 1; row--) {
      g[row][col] = a[index++];
    }
  }
}
// 找x的位置
for (int row = 1; row <= n; row++) {
  for (int col = 1; col <= m; col++) {
    if (g[row][col] == x) {
      printf("%d %d\n", col, row);
      return;
    }
  }
}

第二个方法是数学法：在排序后的数组中用 lower_bound 找到第一个学生的位置（升序），再转换为从高到低的排名，然后根据 S 形排列的规律直接取模计算位置。

小技巧：对于数学方法，需要进行取模运算，所以需要先把下标从 0 开始计数。
为了避免计算错误，建议所有下标都从 0 开始，最后输出答案时再加 1。

const int x = a[0];
sort(a.begin(), a.end());
int pos = lower_bound(a.begin(), a.end(), x) - a.begin(); 
pos = n * m - 1 - pos; // 转换为从高到低的排名
int col = pos / n; // 列号, 0-based
int row = pos % n; // 行号, 0-based
if (col % 2 == 1) {
  row = n - 1 - row; // S 形，根据奇偶性翻转
}
printf("%d %d\n", col + 1, row + 1);

小提示：本文约定输出顺序为「列 行」（col row）。

三、异或和（xor）

题意：给你一些非负数字序列，问可以选择多少个无重叠的子区间，使得每个子区间的异或值都等于 K。

思路：前缀异或+动态规划

这是一个很经典的动态规划与前缀问题。

我在《常见算法和数据结构》的前缀和中提到：更多的时候，前缀和会和哈希表结合使用，用于解决一些子数组和问题。
这里由于是求无重叠的子数组，所以还需要结合动态规划来解决。

状态定义：dp[i] 表示前 i 个数字中，最多可以选择多少个无重叠的子区间，使得每个子区间的异或值都等于 K。

状态转移： dp[i] = max(dp[i-1], dp[j] + 1)。
其中， j < i 且 prefixXor[j] ^ K == prefixXor[i]。

解释：如果我们不选择以 i 结尾的子区间，那么答案就是 dp[i-1]。
如果我们选择以 i 结尾的子区间，那么我们需要找到一个 j，使得从 j+1 到 i 的子区间的异或值等于 K。
这意味着 prefixXor[j] ^ prefixXor[i] == K，即 prefixXor[j] == prefixXor[i] ^ K。

满足要求的 j 可能不止一个，但显然，j越大越好。
因此，我们在哈希表中维护每个前缀异或值出现的最大下标即可。

时间复杂度：O(n)
空间复杂度：O(n)

ll n, k;
vector<ll> a;
vector<ll> dp;
unordered_map<ll, ll> mp;  // xor->maxIndex
void Solver() {            //
  scanf("%lld%lld", &n, &k);
  a.resize(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  dp.resize(n + 1, 0);
  ll pre = 0;
  mp[0] = 0; // 空前缀的下标（方便处理从 1 开始的子数组）
  for (int i = 1; i <= n; i++) {
    const ll v = a[i];
    pre ^= v;
    if (mp.find(pre ^ k) != mp.end()) {
      const ll index = mp[pre ^ k];
      dp[i] = max(dp[i - 1], dp[index] + 1);
    } else {
      dp[i] = dp[i - 1];
    }
    mp[pre] = i; // 更新前缀异或值对应的最大下标
  }
  printf("%lld\n", dp[n]);
}

四、多边形（polygon）

题意：给一些木棍，选择一些木棍组成多边形，问有多少种不同的选择方案。

思路：线性动态规划

题目已经告诉什么时候可以组成多边形了，即边数大于等于 3 且所有小木棍的长度之和大于所有小木棍的长度最大值的两倍。
等价换算一下，就是所有小木棍的长度之和减去最大值要大于最大值。

所以，我们可以先对木棍进行排序，然后使用动态规划来计算有多少种选择方案。

状态定义：dp[i][j] 表示前 i 根木棍中，选择一些木棍使得长度和为 j 的方案数。

状态转移：dp[i][j] = dp[i-1][j] + dp[i-1][j - a[i]]。

大部分同学应该都能想到上面的状态定义和状态转移。

难点：每个木棍最大长度 5000，共 5000 个木棍，长度和最大 250 万。
此时空间复杂度和时间复杂度都为 O(n * sum)，所以无法通过。

分析数据范围，如下 ，可以通过前 20 组数组，拿到 80 分。

第一组： n<=3 且 max<=10，最大长度为 30， AC。
第二组： n<=10 且 max<=100，最大长度为 1000， AC。 第三组： n<=20 且 max<=100，最大长度为 2000， AC。
第四组： n<=500 且 max<=100，最大长度为 50000， AC。
第五组： n<=500 且 max<=1，最大长度为 500， AC。
第六组： n<=5000 且 max<=1，最大长度为 5000， AC。
第七组： n<=5000 且 max<=5000，最大长度为 25000000， TLE。

时间优化技巧：对于第 i 根木棍，我们的目标是求大于 a[i] 的方案数，即求 dp[i-1][j] 中 j > a[i] 的所有方案数。
a[i] 最大 5000，所以我们只需要维护 dp[j] 中 j 从 0 到 5000 的部分。
至于大于 5000 的部分，可以统一存在 50001 位置。

这样，最大长度就压缩到了 5001，时间复杂度和空间复杂度都变成了 O(n * 5001)，从而可以通过这道题。

空间优化技巧：由于 dp[i][j] 只和 dp[i-1][j] 有关，所以我们可以参考 0/1 背包的做法，将 dp 数组压缩为一维。
具体来说，加入第 i 根木棍时，会更新后面的状态，所以需要从后往前更新。

ll n;
vector<ll> a;
const ll modV = 998244353;
void Solver() {  //
  scanf("%lld", &n);
  a.resize(n);
  ll maxV = 0;  // 特殊标记：子集和 > maxV 的统一汇总到 dp[maxV+1]
  for (int i = 0; i < n; i++) {
    scanf("%lld", &a[i]);
    maxV = max(maxV, a[i]);
  }
  maxV = maxV + 1;
  sort(a.begin(), a.end());
  ll ans = 0;

  vector<ll> dp(maxV + 1, 0);     // dp[S] 表示子集和为 S 的方案数
  dp[0] = 1;                      // 空集
  for (int i = 1; i <= n; i++) {  // a[i] 作为最大边
    const ll v = a[i - 1];
  // 第 i 条边作为最大边，统计前面边的子集和 > v 的方案数
    for (int V = v + 1; V <= maxV; V++) {
      ans = (ans + dp[V]) % modV;
    }
    // 第 i 条边加入子集
    for (int V = maxV; V >= 0; V--) {
      const ll sum = V + v;
      if (sum >= maxV) {
        dp[maxV] = (dp[maxV] + dp[V]) % modV;
      } else {
        dp[sum] = (dp[sum] + dp[V]) % modV;
      }
    }
  }
  printf("%lld\n", ans);
}

五、最后

以上就是 2025 年 CSP-J 第二轮算法比赛的全部题解。

总结一下：
第一题：难度为普及-，贪心，提取数字排序输出。
第二题：难度为普及-，排序 + 模拟/数学计算。
第三题：难度为普及/提高−，前缀异或 + 动态规划。
第四题：难度为普及/提高−，线性动态规划 + 状态压缩 + 时间优化。

第四题的时间优化可能会有些难度，其他题目都比较常规。

《完》

-EOF-

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