GoHack 真题速览
2026 CSP-S 第一轮提高级 真题
完整题目 · 参考答案 · 简短点评
S组覆盖位运算、哈夫曼树、区间动态规划、图论、字符串与快速幂；程序阅读和完善程序部分更看重能否识别算法结构与维护的状态。
一｜单项选择
第1题
1. 执行下列代码后，cnt 的值是（ ）。
int x = 2026, cnt = 0;
while (x) {
x &= x - 1;
cnt++;
}
A． 6
B． 7
C． 11
D． 8
参考答案：D｜8
每轮清除最低位的一个 1，循环次数等于 2026 的二进制 1 的个数。
第2题
2. 用权值 {1,2,3,4,5,6,7,8} 构造哈夫曼树，其带权路径长度是（ ）。
A． 108
B． 96
C． 99
D． 102
参考答案：D｜102
反复合并当前最小的两个权值，合并代价总和为 102。
第3题
3. 把 1 到 1000 的所有整数按十进制写出，数字“1”总共出现了多少次（ ）。
A． 300
B． 271
C． 301
D． 320
参考答案：C｜301
百、十、个位各贡献 100 次，数字 1000 再贡献 1 次。
第4题
4. 将 5 封信随机装入 5 个写好地址的信封（每封一个），恰好有 2 封装对的方案数是（ ）。
A． 44
B． 24
C． 10
D． 20
参考答案：D｜20
先选两个固定点，再使其余三封全错：C(5,2)×!3=20。
第5题
5. 3^2026 mod 100 的值是（ ）。
A． 29
B． 9
C． 43
D． 81
参考答案：A｜29
利用模 100 的幂循环，化简指数后得到 29。
第6题
6. 有 5 堆石子排成一行，重量依次为 4,1,3,2,5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（ ）。
A． 36
B． 35
C． 34
D． 33
参考答案：C｜34
用区间动态规划比较不同合并顺序，最优总代价为 34。
第7题
7. 树状数组维护长度 n=16 的序列。查询前缀和 sum(11) 与单点修改 add(3,x) 分别需要访问树状数组中多少个下标（ ）。
A． 3 和 4
B． 4 和 4
C． 3 和 5
D． 4 和 3
参考答案：A｜3 和 4
沿 lowbit 跳转分别访问 3 个和 4 个下标。
第8题
8. 有向无环图 G 顶点集为 {1,2,3,4}，边集为 {(1,2),(1,3)}，顶点 4 与任何顶点均不相邻。该图不同的拓扑序共有多少种（ ）。
A． 12
B． 8
C． 4
D． 6
参考答案：B｜8
在 1、2、3 的合法顺序中插入孤立点 4，共 8 种。
第9题
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 n)
每层分治的总代价为 Θ(n)，层数为 Θ(log n)。
第10题
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
参考答案：D｜直径 7，重心为结点 1
最远两端距离为 7 条边；删去结点 1 后各连通块均不超过一半。
第11题
11. 一张有向图缩点后得到的有向无环图含 6 个顶点，其中入度为 0 的顶点有 3 个、出度为 0 的顶点有 4 个。为使原图变成强连通图，至少需要添加多少条有向边（ ）。
A． 7
B． 6
C． 4
D． 3
参考答案：C｜4
非单点缩点图的最少加边数为源点数与汇点数的最大值。
第12题
12. 含 6 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（ ）。
A． 42
B． 429
C． 132
D． 720
参考答案：C｜132
对应第六个卡特兰数，值为 132。
第13题
13. 字符串 S="ababaabab"，其所有既是真前缀又是真后缀的子串（非空）的长度之和是（ ）。
A． 4
B． 6
C． 7
D． 5
参考答案：B｜6
相等的真前后缀长度为 2 和 4，总和为 6。
第14题
14. 用归并排序统计逆序对，合并部分的核心代码为
// 归并a[l..mid] 与 a[mid+1..r]，同时累加逆序对
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． 变为原来的一半
参考答案：C｜变为满足 i < j 且 a[i]>=a[j] 的数对个数
相等元素会转入右支并被计数，得到原逆序对加上相等数对。
第15题
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
参考答案：B｜376
按平方取模计算，结果为 376。
二｜阅读程序
第16—21题共用模2除法程序；第22—27题共用区间最大公约数稀疏表；第28—33题共用树直径程序。
第16—21题共用题面与程序
（1）输入保证为一个长度恰为 32 的 0/1 字符串。
#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;
}
第16题
16. 当输入为 32 个 0 时，程序输出 12 个 0。（ ）
A． 正确
B． 错误
参考答案：正确（A）
全零输入不会触发异或，尾部 12 位保持零。
第17题
17. 程序运行结束后，数组 a 中下标从 0 到 31 的元素一定全部为 0。（ ）
A． 正确
B． 错误
参考答案：正确（A）
从左到右遇到首位 1 就异或首项为 1 的生成多项式，处理过的位置归零。
第18题
18. 若将第 12～14 行（为 a[32] 到 a[43] 补 0 的循环）删除，会改变程序输出结果。（ ）
A． 正确
B． 错误
参考答案：错误（B）
数组为全局变量，未赋值位置本来初始化为零。
第19题
19. 关于第 6 行定义的数组 gen，下列说法正确的是（ ）。
A． gen 共有 12 个元素，表示一个 12 位的除数
B． gen 共有 13 个元素，表示一个 13 位的被除数
C． gen 共有 13 个元素，其中 gen[0] 是除数的最高位
D． gen 共有 13 个元素，其中 gen[12] 是除数的最高位
参考答案：C｜gen 共有 13 个元素，其中 gen[0] 是除数的最高位
gen 有 13 项，gen[0] 对齐当前被除位置，是最高位。
第20题
20. 该程序实现的功能，最准确的说法是（ ）。
A． 将输入的 32 位串看成二进制数 M，输出 M 与 13 位二进制数 1100000001111 按位异或的结果
B． 将输入串视为 32 位二进制数 M，在其后补 12 个 0（即计算 M×2^12），再对它用 1100000001111 作模 2 除法求余数，并输出 12 位余数
C． 对输入的 32 位串逐位取反并输出结果
D． 统计输入串中 1 的个数，并把该个数用 12 位二进制表示后输出
参考答案：B｜将输入串视为 32 位二进制数 M，在其后补 12 个 0（即计算 M×2^12），再对它用 1100000001111 作模 2 除法求余数，并输出 12 位余数
这是补 12 个零后的模 2 除法，输出 12 位余数。
第21题
21. 若将第 16 行 if (a[i] == 0) continue; 删除，说法正确的是（ ）。
A． 程序输出的结果不会改变
B． 可能造成程序运行错误
C． 程序能够正常输出一个 12 位 0/1 串，但是输出结果与输入的 s 无关
D． 程序运行结束后，a[0] 的值一定为 0
参考答案：C｜程序能够正常输出一个 12 位 0/1 串，但是输出结果与输入的 s 无关
每个位置都会异或一次固定模式，结果不再随输入变化。
第22—27题共用题面与程序
（2）保证 1≤n≤100000，每次查询满足 1≤L≤R≤n，且数组 a 的元素均为正整数。
#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;
}
第22题
22. 当 n=5，a={4,2,6,3,9}，且仅有一次查询 L=2、R=5 时，输出为 1。（ ）
A． 正确
B． 错误
参考答案：正确（A）
gcd(2,6,3,9)=1。
第23题
23. 当某次查询的区间长度为 1（即 L=R）时，这次查询的输出一定等于 a[L]。（ ）
A． 正确
B． 错误
参考答案：正确（A）
两段查询都指向同一项，gcd(a[L],a[L])=a[L]。
第24题
24. 任意一次查询的输出结果一定不小于该查询区间内的最小值。（ ）
A． 正确
B． 错误
参考答案：错误（B）
最大公约数通常不超过各元素，更不会保证大于最小值。
第25题
25. 对于 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｜从 a[i] 开始连续 2^j 个数的最大公约数
它存储从 i 开始连续 2ʲ 个数的最大公约数。
第26题
26. 若把一次求最大公约数的运算视为 O(1)，则第 17～22 行建表过程的时间复杂度为（ ）。
A． Θ(n)
B． Θ(n log n)
C． Θ(n²)
D． Θ(mn)
参考答案：B｜Θ(n log n)
约 log n 层，每层遍历 O(n) 个起点。
第27题
27. 设 x 为一次查询的区间长度（即 x=R−L+1），则使得 lg[x]=5 的 x 的取值范围是（ ）。
A． [16,31]
B． [17,32]
C． [32,63]
D． [33,64]
参考答案：C｜[32,63]
lg[x] 是⌊log₂x⌋，因此 32≤x≤63。
第28—33题共用题面与程序
（3）输入第一行为结点个数 n，第二行为 n−1 个整数，依次表示结点 2～n 的父结点编号，满足 2≤n≤100000 且 1≤fa[i]<i，根结点为 1。
#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;
}
第28题
28. 当 n=5，fa[2]～fa[5]={1,2,3,4} 时，程序输出 4。（ ）
A． 正确
B． 错误
参考答案：正确（A）
该程序累计树上最远两点距离；五结点链的直径为 4。
第29题
29. 程序输出前，f[1] 的值一定等于 ans 的值。（ ）
A． 正确
B． 错误
参考答案：错误（B）
f[1] 是从根向下的最大深度，ans 是整棵树的直径。
第30题
30. 将第 10～12 行与第 13～15 行两个 if 语句的顺序交换后，程序的输出结果不受影响。（ ）
A． 正确
B． 错误
参考答案：错误（B）
若先更新父节点深度，再算路径，可能把同一分支重复计入。
第31题
31. 程序输出的 ans 表示的是（ ）。
A． 树中距离最远的两个结点之间路径所经过的边数
B． 根结点 1 到最远叶子结点之间路径所经过的边数
C． 树中叶子结点的个数
D． 所有结点的父结点编号之和
参考答案：A｜树中距离最远的两个结点之间路径所经过的边数
逆序处理子树并合并两条下行链，记录树的直径。
第32题
32. 当 n=7，fa[2]～fa[7]={1,1,2,2,3,3} 时，输出为（ ）。
A． 2
B． 3
C． 4
D． 5
参考答案：C｜4
两侧最深叶子之间的路径经过 4 条边。
第33题
33. 当 n=10，满足输出为 9 的合法输入种类数为（ ）。
A． 0
B． 9
C． 256
D． 512
参考答案：C｜256
直径为 9 条边意味着整棵树是一条链；逐个加入结点时只能接在链的两端，共 2⁸ 种。
三｜完善程序
第34—38题补全带正负边的平衡路线程序；第39—43题补全格雷码枚举与标准答案构造程序。
第34—38题共用题面与程序
（1）（平衡路线）给定一张有 n 个顶点、m 条边的无向图，每条边带有符号 + 或 -。路线允许重复经过顶点和边；若经过的 + 边数和 - 边数分别为 n+、n-，路线权值为 |n+−n-|。求从 s 到 t 的最小权值，不连通则输出 −1。输入 n,m,s,t 和 m 条边，满足 2≤n≤2×10^5，1≤m≤4×10^5，s≠t，允许重边。
#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题
34. ①处应填（ ）。
A． op[0] == '+' ? 0 : 1
B． op[0] == '+'
C． op[0] == '+' ? 1 : -1
D． op[0] == '-' ? 1 : 0
参考答案：C｜op[0] == '+' ? 1 : -1
把 '+' 边编码为 1、'-' 边编码为 −1。
第35题
35. ②处应填（ ）。
A． hh < n
B． tt < n
C． hh <= tt
D． hh < tt
参考答案：D｜hh < tt
只要队首下标小于队尾下标，队列里仍有待处理结点。
第36题
36. ③处应填（ ）。
A． d[y] + 1
B． d[x] + 1
C． d[x]
D． d[x] - 1
参考答案：B｜d[x] + 1
新顶点距离等于当前顶点距离加 1。
第37题
37. ④处应填（ ）。
A． c[y] == c[x]
B． w[i] == 1
C． c[y] != c[x]
D． d[y] + 1 != d[x]
参考答案：A｜c[y] == c[x]
一条边连接同色顶点时，二分图染色条件被破坏。
第38题
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｜!ok || c[s] == c[t]
存在奇环或 s、t 同色时，可调整路线使正负边数相抵。
第39—43题共用题面与程序
（2）（标准答案）n 名学生回答 m 道只有 A/B 选项的题，第 i 人答案串为 a_i，目标分数为 x_i。构造标准答案，使各人实际分数 r_i 与目标分数的绝对差之和最大。1≤n≤20，1≤m≤300，0≤x_i≤m。__builtin_ctzll(x) 返回非零整数 x 的末尾连续 0 的个数；__builtin_popcountll(x) 返回其二进制表示中 1 的个数。
#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题
39. ①处应填（ ）。
A． 2 * x[i] - m
B． -m + 2 * x[i] + 1
C． m - 2 * x[i]
D． m + 2 * x[i]
参考答案：C｜m - 2 * x[i]
把 |rᵢ−xᵢ| 展开后，对应系数为 m−2xᵢ。
第40题
40. ②处应填（ ）。
A． mask | (mask >> 1)
B． mask ^ (mask >> 1)
C． mask & (mask >> 1)
D． mask ^ ((mask >> 1) + 1)
参考答案：B｜mask ^ (mask >> 1)
格雷码公式为 mask 异或 mask 右移一位。
第41题
41. ③处应填（ ）。
A． __builtin_ctzll(d) + 1
B． __builtin_popcountll(d)
C． __builtin_ctzll(g)
D． __builtin_ctzll(d)
参考答案：D｜__builtin_ctzll(d)
对异或差值 d 使用 __builtin_ctzll(d)。
第42题
42. ④处应填（ ）。
A． 2ll * s[k] * c[k]
B． s[k] * c[k]
C． 2ll * (s[k] - c[k])
D． 2ll * c[k]
参考答案：A｜2ll * s[k] * c[k]
该人的贡献从 −s[k]c[k] 变为相反数，差为 −2s[k]c[k]。
第43题
43. ⑤处应填（ ）。
A． v >= (n & 1)
B． v > (n & 1)
C． v + (n & 1) >= 0
D． v * (n & 1) >= 0
参考答案：A｜v >= (n & 1)
按代码给定的奇偶阈值比较 v 与 n&1，决定该列取 A 或 B。
给家长的一句提醒
答案仅供参考，核对完答案后，先看孩子在哪类题上连续失分：基础概念、程序跟踪，还是算法补全。具体分数与晋级结果仍以官方公布为准。
