📌 本文导航
Part 0 答案速查表 Part 1 单选 1—15（每题 2 分） Part 2 阅读程序 16—33（CRC 校验 / ST 表 GCD / 树直径） Part 3 完善程序 34—43（平衡路线 BFS / 标准答案构造） ⚠️ 说明：题目据官方原卷照片整理；答案为网传参考答案（1—38 核对一致）。提高组难度高于入门组，建议对照代码逐行复盘，最终以 CCF 官方发布为准。
Part 0｜答案速查表
一、单项选择（每题 2 分）
| D | D | C | D | A | C | A | B | A | D | C | C | B | C | B |
二、阅读程序
三、完善程序（每空 3 分）
Part 1｜单项选择题（每题 2 分）
第 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，循环次数就是二进制中 1 的个数。2026 = 1024+512+256+128+64+32+8+2，共 8 个 1。
第 2 题
用权值 {1,2,3,4,5,6,7,8} 构造哈夫曼树，其带权路径长度是（ ）
A. 108 B. 96 C. 99 D. 102
答案：D
解析：哈夫曼每次取最小两堆合并，合并和累加即 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。
第 3 题
把 1 到 1000 的所有整数按十进制写出，数字"1"总共出现了多少次（ ）
A. 300 B. 271 C. 301 D. 320
答案：C
解析：按位统计。
个位：每 10 个数出现 1 次 → 100 次 十位：每 100 个数出现 10 次 → 100 次 百位：100~199 共 100 次 千位：1000 的千位 1 出现 1 次 合计 100+100+100+1 = 301
第 4 题
将 5 封信随机装入 5 个写好地址的信封（每封一个），恰好有 2 封装对的方案数是（ ）
A. 44 B. 24 C. 10 D. 20
答案：D
解析：先选哪 2 封装对：C(5,2)=10；剩下 3 封全错排，错排数 !3=2。合计 10×2 = 20。
第 5 题
3²⁰²⁶ mod 100 的值是（ ）
A. 29 B. 9 C. 43 D. 81
答案：A
解析：3 与 100 互质，φ(100)=40，3⁴⁰≡1 mod 100。2026 = 40×50+26。
3²⁰≡1 mod 100（3¹⁰=49，平方得 2401→1） 3²⁶ = 3²⁰×3⁶ = 1×729 → 29
第 6 题
有 5 堆石子排成一行，重量依次为 4,1,3,2,5。每次只能把相邻的两堆合并成一堆，代价为两堆重量之和。将所有石子合并成一堆的最小总代价是（ ）
A. 36 B. 35 C. 34 D. 33
答案：C
解析：相邻合并用区间 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
第 7 题
树状数组维护长度 n=16 的序列。查询前缀和 sum(11) 与单点修改 add(3,x) 分别需要访问树状数组中多少个下标（ ）
A. 3 和 4 B. 4 和 4 C. 3 和 5 D. 4 和 3
答案：A
解析：
sum(11)：11→10→8→0，访问 a[11]、a[10]、a[8]，共 3 个； add(3)：3→4→8→16→0，访问 a[3]、a[4]、a[8]、a[16]，共 4 个。
第 8 题
有向无环图 G 顶点集 {1,2,3,4}，边集 {(1,2),(1,3)}，顶点 4 与任何顶点均不相邻。该图不同的拓扑序共有多少种（ ）
A. 12 B. 8 C. 4 D. 6
答案：B
解析：1 必须排在 2、3 之前。{1,2,3} 满足"1 在最前"的排列有 2 种（123、132）；孤立点 4 可插入 4 个位置。2×4 = 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)，最长路径 n→2n/3→(2/3)²n→…→1 共 log_{3/2} n 层，故 T(n) = **Θ(n log n)**。
第 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
解析：直径：叶 4/9 → 2 → 1 → 3 → 6 → 7 → 8，最长路径 7 边。 重心：删去结点 1 后两个子树各 4 个结点，均 ≤ 9/2，故重心是 1。
第 11 题
一张有向图缩点后得到的有向无环图含 6 个顶点，其中入度为 0 的顶点有 3 个、出度为 0 的顶点有 4 个。为使原图变成强连通图，至少需要添加多少条有向边（ ）
A. 7 B. 6 C. 4 D. 3
答案：C
解析：DAG 变强连通，最少加边数 = max(源点数, 汇点数) = max(3, 4) = 4。
第 12 题
含 6 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（ ）
A. 42 B. 429 C. 132 D. 720
答案：C
解析：n 个结点的二叉树形态数 = 卡特兰数 Cₙ = C(2n,n)/(n+1)。C₆ = 924/7 = 132。
第 13 题
字符串 s = "ababaabab"，其所有既是真前缀又是真后缀的非空子串的长度之和是（ ）
A. 4 B. 6 C. 7 D. 5
答案：B
解析：逐一比较长度 1—8：
长度 2：前缀 "ab" = 后缀 "ab" ✓ 长度 4：前缀 "abab" = 后缀 "abab" ✓ 其余长度不等。和 = 2+4 = 6。
第 14 题
用归并排序统计逆序对，合并代码为
if(a[i]<=a[j])取左半、否则ans += mid-i+1。若把a[i]<=a[j]改成a[i]<a[j]，则 ans 结果是（ ）A. 完全不变 B. 变为原来的两倍 C. 变为满足 i<j 且 a[i]>=a[j] 的数对个数 D. 变为原来的一半
答案：C
解析：改后相等元素走 else 分支被累计，即把"相等"也计入，最终统计的是所有 i<j 且 a[i]>=a[j] 的数对（含等值对）。
第 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
解析：快速幂求 2¹⁰⁰ mod 1000。2⁸⁰≡176、2²⁰≡576，176×576 = 101376 → 376。
Part 2｜阅读程序题（共 40 分）
程序一：CRC 模 2 除法（16—21）
#include <iostream>
#include <string>
using namespace std;
int a[100];
string s;
int gen[13] = {1, 1, 0, 0, 0, 0, 0, 0, 1, 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 位余数。
16.（√） 输入 32 个 '0'：全 0 串除以任何多项式余数为 0，输出 12 个 0。✓
17.（√） 长除法结束后，前 32 位被除数被逐位消成 0，余数留在 a[32..43]。
18.（×） 全局数组默认零初始化，删掉补 0 循环后 a[32..43] 本来就是 0，输出不变。
19.（C） gen 共 13 个元素，其中 gen[0] 是除数的最高位（异或从 gen[0] 开始对齐）。
20.（B） 功能：32 位串后补 12 个 0（即 M×2¹²），用 1100000001111 作模 2 除法求余，输出 12 位余数。
21.（C） 删掉 continue 后，无论 a[i] 是什么都执行异或，输出成为固定结果，与 s 无关。
程序二：ST 表求区间 GCD（22—27）
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;
}
读懂程序：标准 ST（稀疏表）静态区间查询，dp[i][j] = 从 a[i] 开始连续 2ʲ 个数的 GCD。查询时两段重叠覆盖 [L,R]。
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 不超过区间内任何元素，必然 ≤ 最小值，"不小于最小值"错误。
25.（B） dp[i][j] 是从 a[i] 开始连续 2ʲ 个数的 GCD。
26.（B） 建表 j 层、i 层，共 O(n log n)。
27.（D） lg[x]=5 即 2⁵ ≤ x < 2⁶，x ∈ [32, 63]。
程序三：树的直径 DP（28—33）
#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;
}
输入第二行为结点 2—n 的父结点，1 ≤ fa[i] < i，根为 1。
读懂程序：自底向上树形 DP。f[i] = 结点 i 到其子树最远距离（向下高度）。每个结点处，用"两条最长子链 + 1"更新 ans——这就是树直径的标准求法。
28.（√） n=5, fa={1,2,3,4} 即链 1-2-3-4-5，直径 4。✓
29.（×） f[1] 只是根到最远叶的高度，直径可以跨根的两支，不一定等于 ans。
30.（×） 两个 if 不能交换顺序——必须先用旧的 f[fa[i]] 算直径，再更新 f[fa[i]]，否则会重复累加同一子树。
31.（A） ans 是树中距离最远两结点间路径的边数，即树的直径。
32.（C） n=7, fa={1,1,2,2,3,3}：树 1 下分两支 2、3，各挂叶。最长路径 4-2-1-3-6 = 4 边。
33.（C） n=10 直径为 9 时，树必须接近一条全链（根 1 两端挂链），满足条件的合法输入种类为 256。
Part 3｜完善程序题（每空 3 分，共 30 分）
第一题：带符号边的最短平衡路线（34—38）
题目：无向图每条边带
+或-。一条路线权值 = |n⁺ − n⁻|（经过的正、负边数之差的绝对值）。求 s 到 t 的最小权值，不存在输出 −1。以下程序用 BFS 求解。
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() {
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];
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;
} elseif (④ ____)
ok = 0;
}
}
if (d[t] == -1) { cout << -1; return 0; }
if (!p || !ng) { cout << d[t]; return 0; }
if (⑤ ____) cout << 0; else cout << 1;
return 0;
}
34.（C）op[0] == '+' ? 1 : -1：正边记 +1、负边记 −1，用于累计 n⁺−n⁻。
35.（D）hh < tt：队列非空循环条件。
36.（B）d[x] + 1：BFS 按层扩展，新点层数 = 父点层数 +1。
37.（A）c[y] == c[x]：搜到已访问点且两边染色相同，说明存在同号环，置 ok=0。
38.（C）!ok || c[s] == c[t]：存在同号环，或 s、t 染色相同，答案为 0；否则为 1。
第二题：构造标准答案（39—43）
题目：n 名学生、m 道判断题（A/B）。已知每人目标分数 xᵢ，要构造一份标准答案，使 Σ|rᵢ − xᵢ| 最大。n ≤ 20，m ≤ 300。程序用枚举符号的方法求解。
vector<ll> x(n), c(n);
for (int i = 0; i < n; i++) {
cin >> x[i];
c[i] = ① ____;
}
vector<string> a(n);
// ...读入每人答案 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;
}
// ...按 best 输出每题答案
39.（C）m - 2 * x[i]：把 |rᵢ − xᵢ| 线性化后的系数。
40.（B）mask ^ (mask >> 1)：格雷码枚举，每次只翻转一个学生的符号，便于增量更新。
41.（D）__builtin_ctzll(d)：取两版格雷码差异的最低位，即本次翻转的学生编号 k。
42.（A）2ll * s[k] * c[k]：翻转学生 k 后，C 的增量。
43.（A）v >= 0：每题累计得分 v 非负则选 A，否则选 B。
写在最后｜提高组复盘要点
CSP-S1 比入门组明显更"硬核"——这次考了：
数据结构：ST 表、树状数组、树直径 DP、BFS 分层； 数学：哈夫曼、卡特兰、错位排列、快速幂、模运算、gcd； 算法理解：CRC 模 2 除法、归并逆序对、格雷码增量枚举。
点「在看」+「收藏」，这份提高组真题+解析随时能翻出来复盘。 关注本号，后续晋级线、复赛攻略持续更新。
评论区聊聊：提高组比想象中难吗？你卡在哪一题？
