历年CSP-J复赛真题解析 | 2025年CSP-J复赛
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：历年CSP-J复赛真题解析 | 汇总-CSDN博客
P14357 拼数
【题目来源】
洛谷：[P14357 CSP-J 2025] 拼数 / number（民间数据） - 洛谷
【题目描述】
小 R 正在学习字符串处理。小 X 给了小 R 一个字符串 \(s\)，其中 \(s\) 仅包含小写英文字母及数字，且包含至少一个 \(1 \sim 9\) 中的数字。小 X 希望小 R 使用 \(s\) 中的任意多个数字，按任意顺序拼成一个正整数。注意：小 R 可以选择 \(s\) 中相同的数字，但每个数字只能使用一次。例如，若 \(s\) 为 \(\tt 1a01b\)，则小 R 可以同时选择第 \(1,3,4\) 个字符，分别为 \(1,0,1\)，拼成正整数 \(101\) 或 \(110\)；但小 R 不能拼成正整数 \(111\)，因为 \(s\) 仅包含两个数字 \(1\)。小 R 想知道，在他所有能拼成的正整数中，最大的是多少。你需要帮助小 R 求出他能拼成的正整数的最大值。
【输入】
输入的第一行包含一个字符串 \(s\)，表示小 X 给小 R 的字符串。
【输出】
输出一行一个正整数，表示小 R 能拼成的正整数的最大值。
【输入样例】
5
【输出样例】
5
【算法标签】
《洛谷 P14357 拼数》 #贪心# #排序# #CSP-J入门级# #2025# #O2优化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
string s; // 存储输入的数字字符串
int B[15]; // 计数数组，记录每个数字（0-9）出现的次数
int main()
{
// 输入数字字符串
cin >> s;
// 统计每个数字出现的次数
for (int i = 0; i < s.size(); i++)
{
// 将字符转换为数字索引，并增加对应计数
B[s[i] - '0']++;
}
// 从大到小输出数字（9到0）
for (int i = 9; i >= 0; i--)
{
// 如果当前数字出现过
if (B[i] != 0)
{
// 输出该数字的所有出现次数
while (B[i] > 0)
{
cout << i; // 输出当前数字
B[i]--; // 减少计数
}
}
}
// 输出换行符
cout << endl;
return 0;
}
【运行结果】
5
5
P14358 座位
【题目来源】
洛谷：[P14358 CSP-J 2025] 座位 / seat（民间数据） - 洛谷
【题目描述】
CSP-J 2025 第二轮正在进行。小 R 所在的考场共有 \(n \times m\) 名考生，其中所有考生的 CSP-J 2025 第一轮成绩互不相同。所有 \(n \times m\) 名考生将按照 CSP-J 2025 第一轮的成绩，由高到低蛇形分配座位，排列成 \(n\) 行 \(m\) 列。具体地，设小 R 所在的考场的所有考生的成绩从高到低分别为 \(s_1 > s_2 > \dots > s_{n \times m}\)，则成绩为 \(s_1\) 的考生的座位为第 1 列第 \(1\) 行，成绩为 \(s_2\) 的考生的座位为第 \(1\) 列第 \(2\) 行，\(\dots\)，成绩为 \(s_n\) 的考生的座位为第 \(1\) 列第 \(n\) 行，成绩为 \(s_{n+1}\) 的考生的座位为第 \(2\) 列第 \(n\) 行，\(\dots\)，成绩为 \(s_{2n}\) 的考生的座位为第 \(2\) 列第 \(1\) 行，成绩为 \(s_{2n+1}\) 的考生的座位为第 \(3\) 列第 \(1\) 行，以此类推。
例如，若 \(n = 4, m = 5\)，则所有 \(4 \times 5 = 20\) 名考生将按照 CSP-J 2025 第一轮成绩从高到低的顺序，根据下图中的箭头顺序分配座位。
给定小 R 所在的考场座位的行数 \(n\) 与列数 \(m\)，以及小 R 所在的考场的所有考生 CSP-J 2025 第一轮的成绩 \(a_1, a_2, \dots, a_{n \times m}\)，其中 \(a_1\) 为小 R CSP-J 2025 第一轮的成绩，你需要帮助小 R 求出，他的座位为第几列第几行。
【输入】
输入的第一行包含两个正整数 \(n, m\)，分别表示小 R 所在的考场座位的行数与列数。
输入的第二行包含 \(n \times m\) 个正整数 \(a_1, a_2, \dots, a_{n \times m}\)，分别表示小 R 所在的考场的所有考生 CSP-J 2025 第一轮的成绩，其中 \(a_1\) 为小 R CSP-J 2025 第一轮的成绩。
【输出】
输出一行两个正整数 \(c, r\)，表示小 R 的座位为第 \(c\) 列第 \(r\) 行。
【输入样例】
2 2
99 100 97 98
【输出样例】
1 2
【算法标签】
《洛谷 P14358 座位》 #模拟# #数学# #排序# #CSP-J入门级# #2025# #O2优化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
// 蛇形填充规则：
// 1. 如果列数为奇数，行数为n，则列+1
// 2. 如果列数为偶数，行数为1，则列+1
// 3. 如果列数为奇数，行+1
// 4. 如果列数为偶数，行-1
int n, m; // n:行数, m:列数
int a[105]; // 存储所有输入的数字
int b[15][15]; // 蛇形填充后的矩阵
int k; // 要查找的目标数字
// 比较函数：降序排序
bool cmp(int x, int y)
{
return x > y;
}
int main()
{
// 输入行数和列数
cin >> n >> m;
// 输入所有数字
for (int i = 1; i <= n * m; i++)
{
cin >> a[i];
}
// 记录第一个数字作为目标值
k = a[1];
// 对所有数字进行降序排序
sort(a + 1, a + 1 + n * m, cmp);
// 初始化当前位置（从左上角开始）
int r = 1, c = 1; // r:行, c:列
// 蛇形填充矩阵并查找目标数字的位置
for (int i = 1; i <= n * m; i++)
{
// 将当前数字放入矩阵
b[r][c] = a[i];
// 如果找到目标数字，输出其位置（列，行）
if (a[i] == k)
{
cout << c << " " << r << endl;
return 0;
}
// 根据蛇形填充规则移动到下一个位置
// 情况1：当前列为奇数且到达最后一行，向右移动到下一列
if (c % 2 && r == n)
{
c++;
}
// 情况2：当前列为偶数且到达第一行，向右移动到下一列
else if (c % 2 == 0 && r == 1)
{
c++;
}
// 情况3：当前列为奇数，向下移动一行
else if (c % 2)
{
r++;
}
// 情况4：当前列为偶数，向上移动一行
else
{
r--;
}
}
return 0;
}
【运行结果】
2 2
99 100 97 98
P14359 异或和
【题目来源】
洛谷：[P14359 CSP-J 2025] 异或和 / xor（民间数据） - 洛谷
【题目描述】
小 R 有一个长度为 \(n\) 的非负整数序列 \(a_1, a_2, \dots, a_n\)。定义一个区间 \([l, r]\) (\(1 \leq l \leq r \leq n\)) 的权值为 \(a_l, a_{l+1}, \dots, a_r\) 的二进制按位异或和，即 \(a_l \oplus a_{l+1} \oplus \dots \oplus a_r\)，其中 \(\oplus\) 表示二进制按位异或。
小 X 给了小 R 一个非负整数 \(k\)。小 X 希望小 R 选择序列中尽可能多的不相交的区间，使得每个区间的权值均为 \(k\)。两个区间 \([l_1, r_1], [l_2, r_2]\) 相交当且仅当两个区间同时包含至少一个相同的下标，即存在 \(1 \leq i \leq n\) 使得 \(l_1 \leq i \leq r_1\) 且 \(l_2 \leq i \leq r_2\)。
例如，对于序列 \([2, 1, 0, 3]\)，若 \(k = 2\)，则小 R 可以选择区间 \([1, 1]\) 和区间 \([2, 4]\)，权值分别为 \(2\) 和 \(1 \oplus 0 \oplus 3 = 2\)；若 \(k = 3\)，则小 R 可以选择区间 \([1, 2]\) 和区间 \([4, 4]\)，权值分别为 \(1 \oplus 2 = 3\) 和 \(3\)。
你需要帮助小 R 求出他能选出的区间数量的最大值。
【输入】
输入的第一行包含两个非负整数 \(n, k\)，分别表示小 R 的序列长度和小 X 给小 R 的非负整数。
输入的第二行包含 \(n\) 个非负整数 \(a_1, a_2, \dots, a_n\)，表示小 R 的序列。
【输出】
输出一行一个非负整数，表示小 R 能选出的区间数量的最大值。
【输入样例】
4 2
2 1 0 3
【输出样例】
2
【算法标签】
《洛谷 P14359 异或和》 #动态规划DP# #贪心# #哈希hashing# #前缀和# #位运算# #CSP-J入门级# #2025# #O2优化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
/*
* 算法思路：
* 贪心策略：如果当前区间满足要求，就直接单独成段，为后面有用的格子创建空间
* 异或和优化：使用前缀异或和来避免重复计算
* 核心原理：异或和的奇偶性由1的个数决定（奇数个1，异或和为1；偶数个1，异或和为0）
* 查找技巧：利用异或的交换性，查找满足 sa[r] ^ sa[l-1] = k 的区间
*/
#define int long long // 使用长整型防止溢出
const int N = 500005; // 定义最大数组长度
int n, k; // n:数组长度, k:目标异或值
int a[N]; // 原始数组
int sa[N]; // 前缀异或和数组，sa[i] = a[1]^a[2]^...^a[i]
int last_r; // 记录上一个分段的右端点
int ans; // 分段数量
map<int, int> mp; // 哈希表，记录前缀异或和最后一次出现的位置
signed main() // 使用signed代替int（因为定义了#define int long long）
{
// 输入数组长度和目标异或值
cin >> n >> k;
// 计算前缀异或和
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sa[i] = sa[i - 1] ^ a[i]; // 计算前缀异或和
}
// 初始化：前缀和为0的位置在索引0处
mp[0] = 0;
// 遍历数组，寻找最优分段
for (int r = 1; r <= n; r++)
{
// 计算需要查找的前缀和：sa[r] ^ k = sa[l-1]
int t = sa[r] ^ k;
// 检查是否存在满足条件的分割点
if (mp.count(t) && mp[t] >= last_r)
{
// 找到有效的分段点
ans++; // 分段数量加1
last_r = r; // 更新上一个分段的右端点
// 清空哈希表，重新开始记录（贪心策略）
mp.clear();
// 记录当前前缀和的位置
mp[sa[r]] = r;
}
else
{
// 未找到分段点，记录当前前缀和的位置
mp[sa[r]] = r;
}
}
// 输出最大分段数量
cout << ans << endl;
return 0;
}
【运行结果】
4 2
2 1 0 3
2
P14360 多边形
【题目来源】
洛谷：[P14360 CSP-J 2025] 多边形 / polygon（官方数据） - 洛谷
【题目描述】
小 R 喜欢玩小木棍。小 R 有 \(n\) 根小木棍，第 \(i\) (\(1 \leq i \leq n\)) 根小木棍的长度为 \(a_i\)。
小 X 希望小 R 从这 \(n\) 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连拼成一个多边形。小 R 并不知道小木棍能拼成多边形的条件，于是小 X 直接将条件告诉了他：对于长度分别为 \(l_1, l_2, \dots, l_m\) 的 \(m\) 根小木棍，这 \(m\) 根小木棍能拼成一个多边形当且仅当 \(m \geq 3\) 且所有小木棍的长度之和大于所有小木棍的长度最大值的两倍，即 \(\sum_{i=1}^{m} l_i > 2 \times \max_{i=1}^{m} l_i\)。
由于小 R 知道了小木棍能拼成多边形的条件，小 X 提出了一个更难的问题：有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形？你需要帮助小 R 求出选出的小木棍能够拼成一个多边形的方案数。两种方案不同当且仅当选择的小木棍的下标集合不同，即存在 \(1 \leq i \leq n\)，使得其中一种方案选择了第 \(i\) 根小木棍，但另一种方案未选择。由于答案可能较大，你只需要求出答案对 \(998,244,353\) 取模后的结果。
【输入】
输入的第一行包含一个正整数 \(n\)，表示小 R 的小木棍的数量。
输入的第二行包含 \(n\) 个正整数 \(a_1, a_2, \dots, a_n\)，表示小 R 的小木棍的长度。
【输出】
输出一行一个非负整数，表示小 R 选出的小木棍能够拼成一个多边形的方案数对 \(998,244,353\) 取模后的结果。
【输入样例】
5
1 2 3 4 5
【输出样例】
9
【算法标签】
《洛谷 P14360 多边形》 #动态规划DP# #背包DP# #CSP-J入门级# #2025# #O2优化#
【代码详解】
// 40分解法
#include <bits/stdc++.h>
using namespace std;
const int N = 5005; // 定义最大数组长度
const int mod = 998244353; // 模数（未使用）
int n; // 数组元素个数
int a[N]; // 存储输入的数字数组
int ans; // 统计满足条件的子集数量
/**
* 深度优先搜索枚举所有子集
* @param step 当前处理的元素索引
* @param tmx 当前子集中的最大值
* @param sum 当前子集的元素和
* @param cnt 当前子集的元素个数
*/
void dfs(int step, int tmx, int sum, int cnt)
{
// 递归终止条件：已处理完所有元素
if (step > n)
{
// 检查子集是否满足条件：
// 1. 子集元素和 > 2 * 最大值
// 2. 子集元素个数 >= 3
if (sum > 2 * tmx && cnt >= 3)
{
ans++; // 满足条件，计数加1
}
return;
}
// 分支1：选择当前元素加入子集
dfs(step + 1, max(tmx, a[step]), sum + a[step], cnt + 1);
// 分支2：不选择当前元素
dfs(step + 1, tmx, sum, cnt);
}
int main()
{
// 输入数组长度
cin >> n;
// 输入数组元素
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
// 初始化DFS搜索
// 参数说明：
// step=1: 从第一个元素开始
// tmx=-1: 初始最大值为-1（表示没有选择任何元素）
// sum=0: 初始和为0
// cnt=0: 初始元素个数为0
dfs(1, -1, 0, 0);
// 输出满足条件的子集数量
cout << ans << endl;
return 0;
}
// 64分版本
#include <bits/stdc++.h>
using namespace std;
const int N = 5005; // 定义最大数组长度
const int mod = 998244353; // 模数
int n; // 数组元素个数
int a[N]; // 存储输入的数字数组
int ans; // 统计满足条件的子集数量
int c[N][N]; // 组合数数组，存储C(n,k)的值
/**
* 计算组合数表（杨辉三角）
*/
void calc()
{
// 初始化组合数表：C(i,0)=1
for (int i = 0; i <= n; i++)
{
c[i][0] = 1;
}
// 使用递推公式计算组合数：C(i,j) = C(i-1,j) + C(i-1,j-1)
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
}
/**
* 深度优先搜索枚举所有子集
* @param step 当前处理的元素索引
* @param tmx 当前子集中的最大值
* @param sum 当前子集的元素和
* @param cnt 当前子集的元素个数
*/
void dfs(int step, int tmx, int sum, int cnt)
{
// 递归终止条件：已处理完所有元素
if (step > n)
{
// 检查子集是否满足条件：
// 1. 子集元素和 > 2 * 最大值
// 2. 子集元素个数 >= 3
if (sum > 2 * tmx && cnt >= 3)
{
ans++; // 满足条件，计数加1
}
return;
}
// 分支1：选择当前元素加入子集
dfs(step + 1, max(tmx, a[step]), sum + a[step], cnt + 1);
// 分支2：不选择当前元素
dfs(step + 1, tmx, sum, cnt);
}
int main()
{
// 输入数组长度
cin >> n;
// 输入数组元素
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
// 根据数据规模选择不同算法
if (n <= 20)
{
// 小规模数据：使用DFS暴力枚举
dfs(1, -1, 0, 0);
cout << ans << endl;
}
else
{
// 大规模数据：使用组合数近似计算
calc(); // 计算组合数表
// 统计所有大小>=3的子集数量（近似解）
for (int i = 3; i <= n; i++)
{
ans = (ans + c[n][i]) % mod;
}
cout << ans << endl;
}
return 0;
}
// 100分版本
#include <bits/stdc++.h>
using namespace std;
#define int long long // 使用长整型防止溢出
const int N = 5005; // 定义最大数组长度
const int mod = 998244353; // 模数
int n; // 数组元素个数
int a[N]; // 存储输入的数字数组
int dp[N][N]; // 动态规划数组，dp[i][j]表示前i个元素和为j的子集数
int bad_ans; // 统计不满足条件的子集数量
int ans = 1; // 总子集数（2^n），初始化为1
signed main()
{
// 输入数组长度
cin >> n;
// 输入数组元素并计算总子集数（2^n）
for (int i = 1; i <= n; i++)
{
cin >> a[i];
ans *= 2; // 计算2的n次方
ans %= mod; // 取模防止溢出
}
// 对数组进行升序排序，保证从小到大排序
sort(a + 1, a + n + 1);
// 初始化动态规划数组：空集的和为0，有1种方式
dp[0][0] = 1;
// 动态规划：计算子集和分布
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= 5000; j++) // 遍历所有可能的和（0到5000）
{
// dp[i][j]表示选到前i个数，所选数字的和为j的方案数，那么dp方程就是dp[i][j] = dp[i-1][j] + dp[i-1][j-a[i]]
dp[i][j] = dp[i - 1][j];
// 选择当前元素a[i]（需要j>=a[i]）
if (j >= a[i])
{
dp[i][j] = (dp[i][j] + dp[i - 1][j - a[i]]) % mod;
}
// 统计不满足条件的子集：和j <= 当前元素a[i]，
if (j <= a[i])
{
// 对于第i个数，它作为最大值的方案数是前i-1个数，选出来的总和 ≤ a[i]的方案数，对齐进行累加
bad_ans = (bad_ans + dp[i - 1][j]) % mod;
}
}
}
// 计算最终答案：总子集数 - 不满足条件的子集数 - 空集
// 公式：ans = 2^n - bad_ans - 1
cout << (ans - bad_ans - 1 + mod) % mod << endl;
return 0;
}
【运行结果】
5
1 2 3 4 5
9
浙公网安备 33010602011771号