ARTICLE · 1047684
2026 CSP‑S 第一轮真题
一、单项选择题（每题2分，共30分）
第1题
题干：执行下列代码后，cnt 的值是( )
int x = 2026, cnt = 0;while (x) { x &= x - 1; cnt++;}
A. 6 B. 7 C. 11 D. 8
解析x &= x‑1 经典操作：每次消除二进制最右侧的一个1，循环次数等于二进制中1的个数。 2026 = 1024+512+256+128+64+32+8+2，一共8个1。
✅答案：D 💡考点：位运算，统计二进制1的个数。
第2题
题干：用权值{1, 2, 3, 4, 5, 6, 7, 8} 构造哈夫曼树，其带权路径长度是( ) A. 108 B. 96 C. 99 D. 102
解析哈夫曼树规则：每次选取权值最小两个结点合并，合并代价累加计入WPL。 合并过程： 1+2=3 → 3+3=6 → 4+5=9 → 6+6=12 →7+8=15 →9+12=21 →15+21=36 WPL = 3+6+9+12+15+21+36 = 102
✅答案：D 💡考点：哈夫曼树带权路径长度计算。
第3题
题干：把1 到1000 的所有整数按十进制写出，数字“1”总共出现了多少次( ) A. 300 B. 271 C. 301 D. 320
解析｜按数位分别统计
个位：每10个数出现1次，共100次
十位：每100个数出现10次，共100次
百位：100~199，共100次
千位：数字1000的千位为1，计1次
合计：100+100+100+1=301
✅答案：C
第4题
题干：将5 封信随机装入5 个写好地址的信封（每封一个），恰好有2 封装对的方案数是( ) A. 44 B. 24 C. 10 D. 20
解析｜组合+错排
先选出2封装对：C(5,2)=10
剩余3封信全部装错，3个元素错排数 !3=2 总方案：10× 2=20
✅答案：D 💡易错点：剩下的信必须全部错排，不能只简单做全排列。
第5题
题干：3的2026次方 mod 100的值是() A. 29 B. 9 C. 43 D. 81
解析｜欧拉定理3和100互质，φ(100)=40，3^40 ≡1 (mod 100)。 2026 = 40×50+26；3^20 ≡1 (mod 100) 3^26 = 3^20 × 3^6 =1×729 ≡29 (mod 100)
✅答案：A
第6题
题干：有5 堆石子排成一行，重量依次为4, 1, 3, 2, 5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是( ) A. 36 B. 35 C. 34 D. 33
解析｜区间DP石子合并最优合并顺序：
合并1+3=4，代价4；序列变为4,4,2,5
合并4+4=8，代价8；序列变为8,2,5
合并2+5=7，代价7；序列变为8,7
合并8+7=15，代价15
总代价：4+8+7+15=34
✅答案：A 💡提示：相邻石子合并不能用普通哈夫曼，必须区间DP。
第7题
题干：树状数组维护长度 n=16 的序列。查询前缀和sum(11) 与单点修改add(3, x) 分别需要访问树状数组中多少个下标( ) A. 3 和4 B. 4 和4 C. 3 和5 D. 4 和3
解析
sum(11)：11 →10 →8 →0，访问3个下标
add(3)：3 →4 →8 →16 →0，访问4个下标
✅答案：A 💡考点：树状数组lowbit操作，查询、修改访问结点数量。
第8题
题干：有向无环图 G 顶点集为{1, 2, 3, 4}，边集为{(1, 2), (1, 3)}，顶点4 与任何顶点均不相邻。该图不同的拓扑序共有多少种( ) A. 12 B. 8 C. 4 D. 6
解析约束：1必须出现在2、3前面。 {1,2,3}合法排列：123、132，共2种； 孤立点4可以插入序列4个空隙位置。 总数：2× 4=8。
✅答案：B
第9题
题干：某分治算法满足 T(n)=T(n/3)+T(2n/3)+Θ(n) ，T(1)=O(1) ，则 T(n) 是() A. Θ(n log n) B. Θ(n²) C. Θ(n^1.5) D. Θ(n)
解析｜递归树分析递归树每一层总工作量均为Θ(n)； 最长递归路径 n → (2/3)n →(2/3)²n…→1，层数 log(3/2)n。 总时间复杂度 Θ(n log n)。
✅答案：A
第10题
题干：无根树含9 个结点（编号为1‑9），边集为{(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (6, 7), (7, 8), (5, 9)}。该树的直径（以边数计）与重心分别是( ) A. 直径6，重心为结点3 B. 直径7，重心为结点2 C. 直径8，重心为结点1 D. 直径7，重心为结点1
解析
直径路径：4‑2‑1‑3‑6‑7‑8，一共7条边。
重心：删除结点1后，两棵子树大小均为4，都不超过总结点一半（4.5），重心为结点1。
✅答案：D
第11题
题干：一张有向图缩点后得到的有向无环图含6 个顶点，其中入度为0 的顶点有3 个、出度为0 的顶点有4 个。为使原图变成强连通图，至少需要添加多少条有向边( ) A. 7 B. 6 C. 4 D. 3
解析DAG求变为强连通最少加边公式：max(源点数量，汇点数量)。 源点3个，汇点4个，max(3,4)=4。
✅答案：C
第12题
题干：含6 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）( ) A. 42 B. 429 C. 132 D. 720
解析｜卡特兰数n个无标号二叉树形态数为卡特兰数：Cₙ = C(2n,n)/(n+1) C₆ = 924/7 =132
✅答案：C
第13题
题干：字符串S = "ababaabab"，其所有既是真前缀又是真后缀的子串（非空）的长度之和是( ) A. 4 B. 6 C. 7 D. 5
解析｜KMP‑next数组思想遍历全部合法真前缀/后缀：
长度2：前缀ab = 后缀ab ✔
长度4：前缀abab = 后缀abab ✔
其余长度不匹配。总和 2+4=6。
✅答案：B
第14题
题干：归并排序统计逆序对核心代码，若把判断条件a[i] <= a[j]改成a[i] < a[j]，ans统计结果是？
if (a[i] <= a[j]) { tmp[k++] = a[i++];} else { tmp[k++] = a[j++]; ans += mid - i + 1;}
A. 完全不变 B. 变为原来的两倍 C. 变为满足 i<j 且a[i]>=a[j] 的数对个数 D. 变为原来的一半
解析条件改成a[i]<a[j]，相等的元素会进入else分支，被计入答案。 此时统计：所有 i<j，a[i]≥a[j] 的数对，等值数对也被算入。
✅答案：C 💡易错点：区分严格逆序、非严格逆序。
第15题
题干：执行power(2, 100, 1000)，函数返回值是( )
long long power(long long a, long long b, long long p) { long long r = 1 % p; while (b) { if (b & 1) r = r * a % p; a = a * a % p; b >>= 1; return r; }}
A. 576 B. 376 C. 976 D. 176
解析｜快速幂 2^100 mod 10002^80≡176，2^20≡576 176× 576=101376，对1000取模结果 376。
✅答案：B
🔹二、阅读程序题（共40分）
程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题1.5分，选择题3分
阅读程序1｜CRC循环冗余校验
完整源代码
#include <iostream>#include <string>using namespace std;int a[100];string s;int gen[13] = {1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};int main() { cin >> s; for (int i = 0; i < 32; ++i) { a[i] = s[i] - '0'; } for (int i = 32; i < 44; ++i) { a[i] = 0; } for (int i = 0; i < 32; ++i) { if (a[i] == 0) continue; for (int j = 0; j < 13; ++j) { a[i + j] ^= gen[j]; } } for (int i = 32; i < 44; ++i) { cout << a[i]; } cout << endl; return 0;}
说明：输入保证为一个长度恰为32 的'0'/'1' 字符串。 读懂程序：这是标准 CRC 循环冗余校验。把 32 位被除数后面补 12 个 0，用 13 位生成多项式（1100000001111）做模 2 除法，最后输出 12 位余数。
判断题
(1 分)当输入为32 个'0' 时，程序输出12 个0。( )
程序运行结束后，数组a 中下标从0 到31 的元素一定全部为0。( )
若将第12~14 行（为a[32] 到a[43] 补0 的循环）删除，会改变程序输出结果。( )
解析16.（√）输入 32 个 '0'：全 0 串除以任何多项式余数为 0，输出 12 个 0。
17.（×）
18.（×）全局数组默认零初始化，删掉补 0 循环后 a[32..43] 本来就是 0，输出不变。
单选题
关于第6 行定义的数组gen，下列说法正确的是( )。 A. gen 共有12 个元素，表示一个12 位的除数 B. gen 共有13 个元素，表示一个13 位的被除数 C. gen 共有13 个元素，其中gen[0] 是除数的最高位 D. gen 共有13 个元素，其中gen[12] 是除数的最高位
解析:（D）gen 共 13 个元素，其中 gen[12] 是除数的最高位
该程序实现的功能，最准确的说法是( )。 A. 将输入的32 位串看成二进制数 M ，输出 M 与13 位二进制数1100000001111 按位异或的结果 B. 将输入串视为32 位二进制数 M ，在其后补12 个0（即计算 M×2^12 ），再对它用1100000001111 作模 2 除法求余数，并输出12 位余数 C. 对输入的32 位串逐位取反并输出结果 D. 统计输入串中1 的个数，并把该个数用12 位二进制表示后输出
解析:（B）
若将第16 行
if (a[i] == 0) continue;删除，说法正确的是( )。 A. 程序输出的结果不会改变 B. 可能造成程序运行错误 C. 程序能够正常输出一个12 位'0'/'1' 串，但是输出结果与输入的s 无关 D. 程序运行结束后，a[0] 的值一定为0
解析:（C）
阅读程序2｜稀疏表ST求区间GCD
完整源代码
#include <iostream>using namespace std;int n, m, a[100007], L, R, lg[100007], i, j, t, dp[100007][25], pw[25];int gcd(int x, int y) { if (y == 0) return x; return gcd(y, x % y);}int main() { cin >> n >> m; for (i = 1; i <= n; i++) cin >> a[i]; t = 0; pw[0] = 1; for (i = 1; i <= 24; i++) pw[i] = pw[i - 1] * 2; for (i = 1; i <= 100000; i++) if (pw[t + 1] > i) lg[i] = t; else t++, lg[i] = t; for (i = 1; i <= n; i++) dp[i][0] = a[i]; for (j = 1; j <= lg[n]; j++) for (i = 1; i + pw[j] - 1 <= n; i++) { dp[i][j] = gcd(dp[i][j - 1], dp[i + pw[j - 1]][j - 1]); } for (i = 1; i <= m; i++) { cin >> L >> R; cout << gcd(dp[L][lg[R-L+1]],dp[R-pw[lg[R-L+1]]+1][lg[R-L+1]]) << endl; } return 0;}
说明：保证 1≤n≤100000 ，每次查询满足 1≤L≤R≤n ，且数组a 的元素均为正整数。 程序：标准 ST（稀疏表）静态区间查询，dp[i][j] = 从 a[i] 开始连续 2^j 个数的 GCD。查询时两段重叠覆盖 [L,R]。
判断题
22.当 n=5 ， a=4,2,6,3,9 ，且仅有一次查询 L=2 、 R=5 时，输出为1。()
当某次查询的区间长度为1（即 L=R ）时，这次查询的输出一定等于a[L]。( )
任意一次查询的输出结果一定不小于该查询区间内的最小值。( )
解析: 22.（√）n=5, a={4,2,6,3,9}，查询 [2,5] = gcd(2,6,3,9) = 1。
23.（√）查询长度 1 时，两段退化为 a[L] 本身，输出 a[L]。
24.（×）GCD 不超过区间内任何元素，必然 ≤ 最小值，"不小于最小值"错误。
单选题
对于 j≥1 ，数组dp[i][j]保存的是()。 A. 从a[i] 开始连续 j 个数的最大公约数 B. 从a[i] 开始连续 2^j 个数的最大公约数 C. a[i] 与a[j] 的最大公约数 D. 从a[1] 到a[i] 的最大公约数
解析:（B）
若把一次求最大公约数的运算视为 O(1) ，则建表过程的时间复杂度为()。 A. Θ(n) B. Θ(n log n) C. Θ(n²) D. Θ(mn)
解析:（B）
27.设 x 为一次查询的区间长度（即 x=R−L+1 ），则使得 lg[x]=5 的 x 的取值范围是( )。 A. [16, 31] B. [17, 32] C. [32, 63] D. [33, 64]
解析:（A）
阅读程序3｜树形DP求树的直径
完整源代码
#include <iostream>using namespace std;int n,fa[100007],f[100007],ans;int main() { cin >> n; for (int i = 2; i <= n; ++i) { cin >> fa[i]; } for (int i = n; i >= 2; --i) { if (f[fa[i]] + f[i] + 1 > ans) { ans = f[fa[i]] + f[i] + 1; } if (f[i] + 1 > f[fa[i]]) { f[fa[i]] = f[i] + 1; } } cout << ans << endl; return 0;}
说明：输入第一行为结点个数 n ，第二行为 n−1 个整数，依次表示结点 2∼n 的父结点编号，满足 2≤n≤100000 且1≤fa[i]<i ，根结点为1。 读懂程序：自底向上树形 DP。f[i] = 结点 i 到其子树最远距离（向下高度）。每个结点处，用"两条最长子链 + 1"更新 ans——这就是树直径的标准求法。
判断题
28.当 n=5 ， fa[2]∼fa[5]=1,2,3,4 时，程序输出4。()
程序输出前，f[1] 的值一定等于ans 的值。( )
将两处 if 语句的顺序交换后，程序的输出结果不受影响。( )
解析: 28.（√）n=5，链 1‑2‑3‑4‑5，直径 4。
29.（×）f[1] 只是根到最远叶的高度，直径可以跨根的两支，不一定等于 ans。
30.（×）必须先用旧的 f[fa[i]] 算直径，再更新 f[fa[i]]，否则会重复累加同一子树。
单选题
程序输出的ans 表示的是( )。 A. 树中距离最远的两个结点之间路径所经过的边数 B. 根结点1 到最远叶子结点之间路径所经过的边数 C. 树中叶子结点的个数 D. 所有结点的父结点编号之和
解析:31.（A）
32.当 n=7 ， fa[2]~fa[7]=1,1,2,2,3,3 时，输出为()。 A. 2 B. 3 C. 4 D. 5
解析:32.（C）
33.当 n=10 ，满足输出为9的合法输入种类数为()。 A. 0 B. 9 C. 256 D. 512
解析:33.（B）
🔹三、完善程序题（共30分）
完善程序1｜平衡路线
无向图，边分为 +、‑；求s到t路径 |n+ − n−| 的最小权值，BFS+二分图染色。
#include <iostream>constexpr int N = 200005;constexpr int M = 400005;int n, m, s, t;int h[N], e[M << 1], ne[M << 1], w[M << 1], idx;int q[N], d[N], c[N];void add(int a, int b, int z) { e[idx] = b; w[idx] = z; ne[idx] = h[a]; h[a] = idx++;}int main() { std::cin >> n >> m >> s >> t; for (int i = 1; i <= n; i++) h[i] = d[i] = c[i] = -1; for (int i = 0; i < m; i++) { int a, b; char op[2]; std::cin >> a >> b >> op; int z = ① ; add(a, b, z); add(b, a, z); } int hh = 0, tt = 0; int p = 0, ng = 0, ok = 1; q[tt++] = s; d[s] = c[s] = 0; while ( ② ) { int x = q[hh++]; for (int i = h[x]; i != -1; i = ne[i]) { int y = e[i]; if (w[i] > 0) p = 1; if (w[i] < 0) ng = 1; if (d[y] == -1) { d[y] = ③ ; c[y] = c[x] ^ 1; q[tt++] = y; } else if ( ④ ) ok = 0; } } if (d[t] == -1) { std::cout << -1; return 0; } if (!p || !ng) { std::cout << d[t]; return 0; } if ( ⑤ ) std::cout << 0; else std::cout << 1; return 0;}
34.① C. op[0] == '+' ? 1 : -135.② D. hh<tt36.③ B. d[x] + 137.④ A. c[y]==c[x]38.⑤ C. !ok || c[s] == c[t]
完善程序2｜标准答案构造
n个学生，m道AB选择题，构造标准答案，使得 sum |r_i−x_i| 最大，格雷码枚举。
#include <cstdlib>#include <iostream>#include <string>#include <vector>using namespace std;typedef long long ll;typedef unsigned long long ull;int main() { int n, m; cin >> n >> m; vector<ll> x(n), c(n); for (int i = 0; i < n; i++) { cin >> x[i]; c[i] = ① ; } vector<string> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<int> s(n, -1); vector<ll> q(m, 0); ll C = 0, S = 0; for (int i = 0; i < n; i++) { C -= c[i]; for (int j = 0; j < m; j++) { if (a[i][j] == 'A') q[j]--; else q[j]++; } } for (int j = 0; j < m; j++) S += abs(q[j]); ll ans = C + S; ull best = 0, lst = 0; for (ull mask = 1; mask < (1ULL << n); mask++) { ull g = ② ; ull d = g ^ lst; int k = ③ ; C -= ④ ; for (int j = 0; j < m; j++) { ll old = q[j]; int v = (a[k][j] == 'A' ? 1 : -1); q[j] -= 2ll * s[k] * v; S += abs(q[j]) - abs(old); } s[k] = -s[k]; if (C + S > ans) { ans = C + S; best = g; } lst = g; } for (int i = 0; i < n; i++) { if (best >> i & 1) s[i] = 1; else s[i] = -1; } string res(m, 'A'); for (int j = 0; j < m; j++) { ll v = 0; for (int i = 0; i < n; i++) { if (a[i][j] == 'A') v += s[i]; else v -= s[i]; } if ( ⑤ ) res[j] = 'A'; else res[j] = 'B'; } cout << res << endl; return 0;}
39.① C. m‑2*x[i]40.② B. mask ^ (mask >> 1)41.③ D. __builtin_ctzll(d)42.④ A. 2ll * s[k] * c[k]43.⑤ C. v+(n&1)>=0
✨考后总结
CSP‑S初赛这套试卷考点覆盖面广： ✅位运算、哈夫曼树、卡特兰数、组合数学错排 ✅数论欧拉定理、快速幂、数位统计 ✅树论：树直径、树重心、树状数组 ✅图论：拓扑排序、DAG缩点强连通加边 ✅算法复杂度、递归树、分治 ✅字符串KMP、ST稀疏表、CRC校验 ✅贪心、区间DP、BFS、格雷码技巧
很多题目结合数学推导+代码阅读理解，想要拿到高分，既要熟悉C++代码，也要掌握对应的数学模型。