2026 CSP-S 初赛真题及答案解析（完整版）｜43 题逐题详解

2026 年 CSP-S 提高组第一轮认证真题来了！本文按单项选择题、阅读程序、完善程序三大题型，逐题给出完整题目、答案与详细解析，覆盖 43 道小题。S 组难度显著高于入门组，考点横跨位运算、哈夫曼、区间 DP、树状数组、Catalan 数、KMP、快速幂、CRC 校验、ST 表、树的直径、二分图、格雷码……建议收藏后慢慢消化。

获取 2026 CSP-S初赛真题及解析.pdf

请关注状元编程公众号，回复  2026csp-s

一、单项选择题（共 15 题，每题 2 分，共 30 分）

第 1 题：执行下列代码后，cnt 的值是（ ）。

int x = 2026, cnt = 0;while (x) {    x &= x - 1;    cnt++;}

A. 6　　B. 7　　C. 11　　D. 8

答案：D

x &= x - 1 的作用是消掉二进制里最低位的那个 1，所以循环次数 = 2026 的二进制中 1 的个数。2026 = 2¹⁰+2⁹+2⁸+2⁷+2⁶+2⁵+2³+2¹，共 8 个 1。

考点：位运算 x & (x-1) 消最低位 1、数二进制中 1 的个数。

第 2 题：用权值 {1, 2, 3, 4, 5, 6, 7, 8} 构造哈夫曼树，其带权路径长度是（ ）。

A. 108　　B. 96　　C. 99　　D. 102

答案：D

每次合并权值最小的两个，累加所有合并代价：3+6+9+12+15+21+36 = 102。带权路径长度 WPL 等于所有合并代价之和。

考点：哈夫曼树的构造与 WPL 计算。

第 3 题：把 1 到 1000 的所有整数按十进制写出，数字 "1" 总共出现了多少次（ ）。

A. 300　　B. 271　　C. 301　　D. 320

答案：C

把 0~999 都补成三位数，每一位出现 1 的次数都是 100 次，三位合计 300；再加 1000 里的那个 1，共 301 次。

考点：数位统计。

第 4 题：将 5 封信随机装入 5 个写好地址的信封（每封一个），恰好有 2 封信装对的方案数是（ ）。

A. 44　　B. 24　　C. 10　　D. 20

答案：D

先选哪 2 封装对：C(5,2) = 10；剩下 3 封必须全部装错（错排）D(3) = 2。10×2 = 20。

考点：组合计数 + 错排。

第 5 题：3²⁰²⁶ mod 100 的值是（ ）。

A. 29　　B. 9　　C. 43　　D. 81

答案：A

3 的幂模 100 周期为 20（3²⁰ 末两位是 01）。2026 mod 20 = 6，3⁶ = 729，末两位 29。

考点：模运算的周期性 / 快速幂。

第 6 题：有 5 堆石子排成一行，重量依次为 4, 1, 3, 2, 5。每次只能合并相邻两堆，代价为两堆重量之和。合并成一堆的最小总代价是（ ）。

A. 36　　B. 35　　C. 34　　D. 33

答案：C

只能合并相邻两堆，是区间 DP（不是哈夫曼）：dp[i][j] = min{ dp[i][k] + dp[k+1][j] } + 区间总重量，按区间长度从小到大推，得 dp[1][5] = 34。

考点：区间 DP（石子合并）。

第 7 题：树状数组维护长度 n=16 的序列，查询前缀和 sum(11) 与单点修改 add(3, x) 分别需要访问多少个下标（ ）。

A. 3 和 4　　B. 4 和 4　　C. 3 和 5　　D. 4 和 3

答案：A

查询前缀和不断减 lowbit：11→10→8→0，访问 3 个；单点修改不断加 lowbit：3→4→8→16，访问 4 个。查询递减、修改递增。

考点：树状数组（Fenwick）的实现细节。

第 8 题：有向无环图 G 顶点 {1,2,3,4}，边 {(1,2), (1,3)}，顶点 4 与任何顶点均不相邻。该图不同的拓扑序共有（ ）。

A. 12　　B. 8　　C. 4　　D. 6

答案：B

唯一约束是 1 排在 2、3 前，4 不受限。4 个数全排列 24 种，"1 在 2、3 前"概率 1/3，故 24÷3 = 8。

考点：拓扑排序计数。

第 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)

答案：A

两个子问题规模不同，主定理不适用，画递归树：每层合并代价 Θ(n)，深度由最慢缩小的分支决定（约 log_{3/2} n），总代价 Θ(n log n)。

考点：递归树分析分治复杂度。

第 10 题：无根树 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

答案：D

最长路径 9-5-2-1-3-6-7-8，共 7 条边。重心要逐个删点比较最大连通块：删 1 后最大连通块 4（最小），故重心为结点 1。

考点：树的直径、树的重心。

第 11 题：有向图缩点后得到的 DAG 含 6 个顶点，入度为 0 的有 3 个，出度为 0 的有 4 个。为使原图变强连通，至少需添加（ ）条有向边。

A. 7　　B. 6　　C. 4　　D. 3

答案：C

把 DAG 变强连通，最少加边数 = max(入度为 0 的点数, 出度为 0 的点数) = max(3, 4) = 4。

考点：强连通分量 / 缩点后加边。

第 12 题：含 6 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（ ）。

A. 42　　B. 429　　C. 132　　D. 720

答案：C

n 个结点不同形态二叉树 = 第 n 个 Catalan 数：C(12,6)/7 = 924/7 = 132。

考点：Catalan 数。

第 13 题：字符串 s = "ababaabab"，其所有既是真前缀又是真后缀的非空子串长度之和是（ ）。

A. 4　　B. 6　　C. 7　　D. 5

答案：B

沿 KMP 失配链取所有 border：π[9]=4（"abab"），π[4]=2（"ab"），π[2]=0 结束。长度和 = 4+2 = 6。

考点：KMP 前缀函数（border）。

第 14 题：用归并排序统计逆序对，合并时 if (a[i] <= a[j]) 取左半，否则 ans += mid - i + 1。若把条件改成 a[i] < a[j]，则 ans 统计的是（ ）。

A. 完全不变　　B. 变为原来的两倍　　C. 变为满足 i<j 且 a[i]>=a[j] 的数对个数　　D. 变为原来的一半

答案：C

原条件统计 a[i] > a[j]（严格逆序对）。改成 < 后，a[i]==a[j] 也落入 else 被累加，统计范围扩大到 a[i] ≥ a[j] 的数对个数。

考点：归并排序求逆序对、相等元素处理。

第 15 题：执行 power(2, 100, 1000)，返回值是（ ）。

longlongpower(longlong a, longlong b, longlong p){longlong 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

答案：B

快速幂求 2¹⁰⁰ mod 1000。用 CRT：2¹⁰⁰ mod 8 = 0，2¹⁰⁰ mod 125 = 1（欧拉定理 φ(125)=100）。解得 x ≡ 0 (mod 8) 且 x ≡ 1 (mod 125)，在 0~999 内 x = 376。

考点：快速幂、中国剩余定理。

二、阅读程序（3 大题，共 40 分）

阅读程序（一）：二进制多项式模 2 除法（CRC 校验）

#include<iostream>#include<string>usingnamespace std;int a[100];string s;int gen[13] = {1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};intmain(){    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;return0;}

程序把 32 位输入串当成二进制数，后面补 12 个 0，用 13 位 gen = 1100000001111 做模 2 除法（^ 即不进位加法），输出 12 位余数——这是 CRC 校验思路。

第 16 题（判断）：当输入为 32 个 '0' 时，程序输出 12 个 0。（　）

答案：√。a[0..31] 全 0，每一轮都 continue，不做任何异或，a[32..43] 保持 0。

第 17 题（判断）：程序运行结束后，数组 a 中下标 0 到 31 的元素一定全部为 0。（　）

答案：√。每位要么是 0（continue 不变），要么是 1（异或 gen[0]=1 变 0），处理完必全 0。

第 18 题（判断）：若将为 a[32] 到 a[43] 补 0 的循环删除，会改变程序输出结果。（　）

答案：×。a 是全局数组，默认初值就是 0，删不删补零结果相同。

第 19 题（单选）：关于第 6 行定义的数组 gen，下列说法正确的是（ ）。

A. gen 共有 12 个元素，表示 12 位除数　　B. gen 共有 13 个元素，表示 13 位被除数　　C. gen 共有 13 个元素，其中 gen[0] 是除数的最高位　　D. gen 共有 13 个元素，其中 gen[12] 是除数的最高位

答案：C。初始化列表共 13 个元素，表示除数（生成多项式），下标 0 对应最高位（从 a[i+0] 开始往高位异或）。

第 20 题（单选）：该程序实现的功能，最准确的说法是（ ）。

A. 输出 M 与 1100000001111 按位异或的结果　　B. 将 M 补 12 个 0 后对 1100000001111 做模 2 除法求余数并输出　　C. 逐位取反输出　　D. 统计 1 的个数用 12 位二进制输出

答案：B。"补 12 个 0"= 左移 12 位（乘 2¹²），用 13 位除数做不进位除法即模 2 除法，输出 12 位余数。

第 21 题（单选）：若将 if (a[i] == 0) continue; 删除，说法正确的是（ ）。

A. 输出不变　　B. 可能运行错误　　C. 能正常输出 12 位串，但结果与输入 s 无关　　D. 运行结束后 a[0] 一定为 0

答案：C。删掉 continue 后每一位都无条件执行固定异或，计算与输入脱钩，输出变成固定 12 位串（不会越界，下标最大 43）。

阅读程序（二）：倍增 GCD（稀疏表 ST 表）

#include<iostream>usingnamespace std;int n, m, a[100007], L, R, lg[100007], i, j, t, dp[100007][25], pw[25];intgcd(int x, int y){if (y == 0) return x;returngcd(y, x % y);}intmain(){    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;    }return0;}

预处理 dp[i][j] = 从 a[i] 起连续 2^j 个数的 gcd，再用两个长 2^k 的区间拼起来覆盖查询区间——稀疏表把区间 gcd 查询做到 O(1)。

第 22 题（判断）：当 n=5、a={4,2,6,3,9}，仅一次查询 L=2、R=5 时，输出为 1。（　）

答案：√。a[2..5]={2,6,3,9}，最大公约数为 1。

第 23 题（判断）：当某次查询区间长度为 1（L=R）时，输出一定等于 a[L]。（　）

答案：√。lg[1]=0，两个区间都退化成长度 1，dp[L][0] = a[L]。

第 24 题（判断）：任意一次查询的输出结果一定不小于该区间内的最小值。（　）

答案：×。输出是 gcd，gcd 一定不大于区间最小值。如 {4,6}，最小值 4，但 gcd=2 < 4。

第 25 题（单选）：对于 j≥1，dp[i][j] 保存的是（ ）。

A. 从 a[i] 起连续 j 个数的 gcd　　B. 从 a[i] 起连续 2^j 个数的 gcd　　C. a[i] 与 a[j] 的 gcd　　D. 从 a[1] 到 a[i] 的 gcd

答案：B。转移把两段 2^(j-1) 区间拼成 2^j。

第 26 题（单选）：若把一次 gcd 视为 O(1)，建表过程的时间复杂度为（ ）。

A. Θ(n)　　B. Θ(n log n)　　C. Θ(n²)　　D. Θ(mn)

答案：B。外层 j 到 lg[n]（约 log n 层），内层 i 到 n，共 Θ(n log n)。

第 27 题（单选）：设 x 为查询区间长度，使 lg[x]=5 的 x 取值范围是（ ）。

A. [16,31]　　B. [17,32]　　C. [32,63]　　D. [33,64]

答案：C。lg[x]=⌊log₂x⌋，2⁵=32 ≤ x < 2⁶=64，即 [32,63]。

阅读程序（三）：树上递推求最长路径（直径）

#include<iostream>usingnamespace std;int n, fa[100007], f[100007], ans;intmain(){    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;return0;}

倒序（i 从 n 到 2）遍历，f[] 记"从该结点向下能走多远"，用 f[fa[i]]+f[i]+1 更新答案。因父结点编号 < 子结点编号，倒序保证了处理 i 时它的孩子都已处理完。

第 28 题（判断）：当 n=5，fa[2..5]={1,2,3,4} 时，程序输出 4。（　）

答案：√。对应一条 1-2-3-4-5 的链，最长路径 4 条边。

第 29 题（判断）：程序输出前，f[1] 的值一定等于 ans 的值。（　）

答案：×。星形树（fa={1,1,1,1}）时 ans=2 而 f[1]=1，两者不等。

第 30 题（判断）：将两个 if 语句的顺序交换后，程序的输出结果不受影响。（　）

答案：×。原程序先用旧 f[fa[i]] 更新答案，再更新 f[fa[i]]；交换后会先把 i 的贡献并入父结点，等于同一条路径算两次，结果变大。

第 31 题（单选）：程序输出的 ans 表示的是（ ）。

A. 树中距离最远的两个结点之间路径经过的边数　　B. 根到最远叶子的边数　　C. 叶子结点个数　　D. 所有父结点编号之和

答案：A。ans 是"经过某结点的两条最长向下路径之和"的最大值，即树的直径。

第 32 题（单选）：当 n=7，fa[2..7]={1,1,2,2,3,3} 时，输出为（ ）。

A. 2　　B. 3　　C. 4　　D. 5

答案：C。树形：1 带 2、3；2 带 4、5；3 带 6、7。最长路径 4-2-1-3-6 共 4 条边。

第 33 题（单选）：当 n=10，满足输出为 9 的合法输入种类数为（ ）。

A. 0　　B. 9　　C. 256　　D. 512

答案：C。n=10 时合法输入共 9! = 362880 种，枚举后输出为 9 的共 256 种。

三、完善程序（2 大题，共 30 分）

完善程序（一）：平衡路线

给定一张 n 个顶点 m 条边的无向图，每条边带符号 + 或 −。从 s 到 t 的路线（可重复经过点边）权值为 |n⁺ − n⁻|（+ 边数与 − 边数之差的绝对值）。求 s 到 t 的最小权值，不存在则输出 −1。

#include<iostream>constexprint N = 200005;constexprint 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];voidadd(int a, int b, int z){    e[idx] = b; w[idx] = z; ne[idx] = h[a]; h[a] = idx++;}intmain(){    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, 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;            } elseif (____④____) ok = 0;        }    }if (d[t] == -1) { std::cout << -1; return0; }if (!p || !ng) { std::cout << d[t]; return0; }if (____⑤____) std::cout << 0;else std::cout << 1;return0;}

BFS 求跳数 d[]，同时做二分图染色 c[]，用 p、ng 记录是否出现过 +/− 边，最后分情况输出。

第 34 题：① 处应填（ ）。A. op[0]=='+'?0:1　B. op[0]=='+'　C. op[0]=='+'?1:-1　D. op[0]=='-'?1:0　→ 答案：C

'+' 边记权值 1，'−' 边记 −1。

第 35 题：② 处应填（ ）。A. hh<n　B. tt<n　C. hh<=tt　D. hh<tt　→ 答案：D

队列元素在 q[hh..tt−1]，循环条件是 hh < tt。

第 36 题：③ 处应填（ ）。A. d[y]+1　B. d[x]+1　C. d[x]　D. d[x]-1　→ 答案：B

d[y] 记从 s 到 y 的跳数，比 d[x] 多一跳。

第 37 题：④ 处应填（ ）。A. c[y]==c[x]　B. w[i]==1　C. c[y]!=c[x]　D. d[y]+1!=d[x]　→ 答案：A

遇到已访问的 y 且相邻同色 c[y]==c[x]，说明存在奇环，非二分图，ok 置 0。

第 38 题：⑤ 处应填（ ）。A. ok && c[s]==c[t]　B. ok && c[s]!=c[t]　C. !ok || c[s]==c[t]　D. !ok && c[s]!=c[t]　→ 答案：C

正负边都出现时答案只能是 0 或 1：!ok（有奇环）或 c[s]==c[t]（路径长为偶）时取 0，否则取 1。

完善程序（二）：标准答案（格雷码枚举）

n 名学生、m 道选择题（每题 A/B）。构造一份标准答案使 Σ|rᵢ − xᵢ| 最大（rᵢ 为学生 i 得分，xᵢ 为目标分）。n ≤ 20，m ≤ 300。

#include<cstdlib>#include<iostream>#include<string>#include<vector>usingnamespace std;typedeflonglong ll;typedefunsignedlonglong ull;intmain(){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;return0;}

把每个 |rᵢ−xᵢ| 用 max 展开后，目标函数拆成"每名学生独立选符号 sᵢ"+"每道题独立选符号"两部分；n ≤ 20 用格雷码遍历所有 2^n 个子集，每次翻转一个人、增量更新。

第 39 题：① 处应填（ ）。A. 2*x[i]-m　B. -m+2*x[i]+1　C. m-2*x[i]　D. m+2*x[i]　→ 答案：C

每名学生的常数项 c[i] = m − 2·x[i]。

第 40 题：② 处应填（ ）。A. mask|(mask>>1)　B. mask^(mask>>1)　C. mask&(mask>>1)　D. mask^((mask>>1)+1)　→ 答案：B

格雷码 = mask ^ (mask >> 1)，相邻两值只差一位，所以 d = g ^ lst 只有一位是 1。

第 41 题：③ 处应填（ ）。A. __builtin_ctzll(d)+1　B. __builtin_popcountll(d)　C. __builtin_ctzll(g)　D. __builtin_ctzll(d)　→ 答案：D

d 是 2 的幂，ctzll(d) 取末尾连续 0 的个数 = 变化位的下标 k。

第 42 题：④ 处应填（ ）。A. 2ll*s[k]*c[k]　B. s[k]*c[k]　C. 2ll*(s[k]-c[k])　D. 2ll*c[k]　→ 答案：A

翻转第 k 名学生符号，常数项变化量 = 2ll·s[k]·c[k]。

第 43 题：⑤ 处应填（ ）。A. v>=(n&1)　B. v>(n&1)　C. v+(n&1)>=0　D. v*(n&1)>=0　→ 答案：A

v 是第 j 题所有学生带符号贡献之和，v≥(n&1) 统一了 n 为偶（v≥0）和 n 为奇（v≥1 即 v>0）两种情况。

四、参考答案速查表

本文基于 2026 年 CSP-S 第一轮认证真题整理，答案与解析由公开资料归纳，最终以 CCF 官方发布为准。祝各位同学提高组初赛顺利！