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

• 【正确答案】D
• 【深度解析】 本题核心考点为低位比特消去。语句 x &= x - 1 每执行一次，就会无条件清除二进制中最低位的那个 1。因此，循环执行的总次数 cnt 恰好等于初始值 2026 二进制表示中 1 的个数。将十进制 2026 拆分为 2 的幂次之和：2026 = 1024 + 512 + 256 + 128 + 64 + 32 + 8 + 2 = (1111101010)₂。共有 8 个 1，故循环执行 8 次，cnt = 8。

2. 用权值 (1,2,3,4,5,6,7,8) 构造哈夫曼树，其带权路径长度是（ ）

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

• 【正确答案】D
• 【深度解析】 哈夫曼树构造每次合并最小两项：
1. 合并 1, 2 → 新权值 3（代价 3）。剩余：(3, 3, 4, 5, 6, 7, 8)
2. 合并 3, 3 → 新权值 6（代价 6）。剩余：(4, 5, 6, 6, 7, 8)
3. 合并 4, 5 → 新权值 9（代价 9）。剩余：(6, 6, 7, 8, 9)
4. 合并 6, 6 → 新权值 12（代价 12）。剩余：(7, 8, 9, 12)
5. 合并 7, 8 → 新权值 15（代价 15）。剩余：(9, 12, 15)
6. 合并 9, 12 → 新权值 21（代价 21）。剩余：(15, 21)
7. 合并 15, 21 → 新权值 36（代价 36）。 带权路径长度（WPL）等于所有非叶节点代价之和：3 + 6 + 9 + 12 + 15 + 21 + 36 = 102。

3. 把 1 到 1000 的所有整数按十进制写出，数字“1”总共出现了多少次（ ）

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

• 【正确答案】C
• 【深度解析】 在 000-999 这 1000 个数形式中，总共有 3000 个数位，0-9 出现概率均等，每个出现 3000 / 10 = 300 次。最后加上数字 1000 贡献的千位 1，共 300 + 1 = 301 次。

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

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

• 【正确答案】D
• 【深度解析】 组合计数问题：先从 5 封中挑 2 封装对，为 C(5, 2) = 10 种。剩下的 3 封信全部装错即全错排，3 元素的错排数固定为 D = 2 种。总方案数为 10 * 2 = 20。

5. 3²⁰²⁶ mod 100 的值是（ ）

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

• 【正确答案】A
• 【深度解析】 模 100 取最后两位数。寻找周期律：3^4 = 81, 3^5 = 43, 3^10 = 43^2 = 49, 3^20 = 49^2 = 1 (mod 100)。所以周期为 20。由于 2026 = 20 * 101 + 6，因此 3²⁰²⁶ = 3⁶ = 729 = 29 (mod 100)。

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

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

• 【正确答案】C
• 【深度解析】 区间DP问题。设 f[l][r] 为合并区间最小代价。通过小区间合并推导，全区间总重量 15。最优划分代价值为 34。 最优合并顺序：先 1+3=4（代价4），再左边 4+4=8（代价8），右边 2+5=7（代价7），最后 8+7=15（代价15）。总计 4+8+7+15=34。

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

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

• 【正确答案】A
• 【深度解析】
• sum(11)：i -= lowbit(i)。11 (1011) -> 10 (1010) -> 8 (1000) -> 0。共访问 3 个。
• add(3, x)：i += lowbit(i)。3 -> 4 -> 8 -> 16 -> 32(超出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 前，相对拓扑序 2 种。孤立点 4 插入 3 元素序列有 4 个位置。共计 2 * 4 = 8 种。

9. 某分治算法满足 T(n)=T(n/3)+T(2n/3)+Θ(n)，T(1)=O(1) 则 T(n) 是（ ）

A. Θ(nlogn) B. Θ(n²) C. Θ(n^1.5) D. Θ(n)

• 【正确答案】A
• 【深度解析】 递归树分析。树的每一层总代价恒为 Θ(n)，沿最长分支推进最大树深为 log_1.5 n = Θ(log 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
• 【深度解析】
• 直径：最长路径 9-5-2-1-3-6-7-8，共含 7 条边。
• 重心：删除点 1 剩余两个连通块大小均为 4，满足重心最大块不超过总数一半定义，故重心为 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
• 【深度解析】 节点不带标号、分隔左右子树的二叉树形态数量是经典的卡特兰数（加泰罗尼亚数字） 应用。
• 设置  为含  个结点的二叉树形态数，递推关系为：。
• 卡特兰数前几项分别为：。
• 可以直接用公式计算：。

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

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

• 【正确答案】B
• 【深度解析】 公共非空真前后缀有长度为 2 的 "ab" 与长度为 4 的 "abab"，长度和为 2 + 4 = 6。

14. 用归并排序统计逆序对，合并部分的核心代码若把判断条件中的 a[i] <= a[j] 改成 a[i] < a[j]，则 ans 统计出的结果是（ ）

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

• 【正确答案】C
• 【深度解析】 变为 < 后，若值相等 a[i] == a[j] 也会进入 else 累加逆序对贡献，因此最终统计结果也把相等值数对计入，变成了满足 i < j 且 a[i] >= a[j] 的数对数。

15. 执行 power(2,100,1000) 调用下列函数，返回值是（ ）

A. 576 B. 376 C. 976 D. 176

• 【正确答案】B
• 【深度解析】 快速幂计算。2¹⁰ = 1024 = 24 (mod 1000)。2²⁰ = 24^2 = 576。2⁴⁰ = 576^2 = 776。2⁸⁰ = 776^2 = 176。2¹⁰⁰ = 2⁸⁰ * 2²⁰ = 176 * 576 = 376 mod 1000。

三、 阅读程序题（共 40 分）

(1) 模2除法求余数程序

判断题

• 16. 当输入为 32 个 '0' 时，程序输出 12 个 '0'。
• 正确答案：√
• 深度解析：输入全为 '0' 时，数组前 32 位被转换为数字 0。在外层循环中，由于第 12 行的 if (a[i] == 0) continue; 成立，所有的异或逻辑都被跳过，尾部的 12 个初始零没有任何变动，固定输出 12 个 0。
• 17. 程序运行结束后，数组中下标从 0 到 31 的元素一定全部为 0。
• 正确答案：√
• 深度解析：这是模 2 除法消去的必然结果。只要遇到 a[i] == 1，由于gen数组的最高权重位 gen[0] == 1，在执行按位异或后，高位必定满足 。后续循环的起点已经向后移动，因此前 32 位在退出循环后一定全为 0。
• 18. 若将第 11~13 行（为 a 到 a 补 0 的循环）删除，会改变程序输出结果。
• 正确答案：×
• 深度解析：数组 a 定义在静态全局区。在 C++ 规范中，未显式初始化的全局基础变量数组会被系统默认自动执行零初始化（Zero-initialization）。因此删除该手动补零循环并不会更改内存现状。

单选题

• 19. 关于第 6 行定义的数组 gen，下列说法正确的是（ ）。
• 正确答案：C
• 深度解析：大括号内包含 13 个初始常数，代表一个 13 位的二进制除数。高位最先参与扫描对齐，因此 gen[0] 即为该除数的最高权重位。
• 20. 该程序实现的功能，最准确的说法是（ ）。
• 正确答案：B
• 深度解析：该算法是标准的循环冗余校验码（CRC-12）的核心硬件逻辑模拟：将 32 位原始串左移 12 位（末尾补 12 个零），随后与生成式做按位无借位的模 2 除法（异或），最终输出最后的 12 位余数作为校验位。
• 21. 若将第 15 行 if (a[i] == 0) continue 删除，说法正确的是（ ）。
• 正确答案：C
• 深度解析：若删除此判断，无论当前位是 0 还是 1，程序都会强行执行 32 次异或消去。由于缺乏对输入信号的选择性分流，会导致输出状态彻底与输入脱钩。

(2) ST 表维持区间最大公约数（GCD）

判断题

• 22. 当 n=5， 且仅有一次查询 L=2, R=5 时，输出为 1。
• 正确答案：√
• 深度解析：区间  对应的片段为 。计算它们的连续最大公约数：。
• 23. 当某次查询的区间长度为 1（即 L=R）时，这次查询的输出一定等于 。
• 正确答案：√
• 深度解析：长度为 1 时，倍增查询区间退化。代码中调用的两端重叠项均指向单点 dp[L][0]，即  本身。
• 24. 任意一次查询的输出结果一定不小于该查询区间内的最小值。
• 正确答案：×
• 深度解析：最大公约数随涵盖元素增加呈现单调不升性质（越约越小）。如片段  的极小值为 2，但全局公约数被拉低到了 1。

单选题

• 25. 对于 j ≥ 1，数组 dp[i][j] 保存的是（ ）。
• 正确答案：B
• 深度解析：ST 表经典的空间倍增结构。第二维的指数位 j 代表区间覆盖长度的幂次，因此 dp[i][j] 代表自位置 i 开始，总跨度为  的闭区间的属性。
• 26. 若把一次求最大公约数的运算视为 O(1)，则建表过程的时间复杂度为（ ）。
• 正确答案：B
• 深度解析：预处理建表时，外层控制倍增幂次（共  层），内层控制遍历节点边界（共  次）。在单次 GCD 视为  的前提下，整体预处理耗时为 。
• 27. 设 x 为一次查询的区间长度（即 x = R - L + 1），则使得 lg[x] = 5 的 x 取值范围是（ ）。
• 正确答案：C
• 深度解析：由代码 15-18 行预处理可知，lg[x] 计算的是不大于  的最大 2 的整数幂次（即 ）。若要求对数取整值为 5，其宽度变量必须落在  范围内，即 。

(3) 树形 DP 与树的直径

判断题

• 28. 当 n=5， 时，程序输出 4。
• 正确答案：√
• 深度解析：该依赖指向定义了一条没有任何分叉的单向长链树（竹子形）。在 5 个顶点的长链树中，两端点间的最远边数距离显然为 。
• 29. 程序输出前，f 的值一定等于 ans 的值。
• 正确答案：×
• 深度解析：f 记录的是以 1 为根节点向下延伸的树的最大深度（单向高度）。而全局最大直径 ans 完全可能仅产生于某棵极深局部子树的内部两个分叉间，不需要跨越根节点。
• 30. 将第 10~12 行与第 13~15 行两个 if 语句的顺序交换后，程序的输出结果不受影响。
• 正确答案：×
• 深度解析：顺序具有绝对依赖性。拼装路径时，所用的父节点已有最大高度 f[fa[i]] 必须是尚未计入当前子树 i 贡献时的纯净状态（代表另一侧的侧枝长链）。如果调换顺序，父节点会被提前刷新，导致在更新直径时同一条侧枝被重复叠加算了两遍（形成了路径重叠折返），状态转移彻底崩溃。

单选题

• 31. 程序输出的 ans 表示的是（ ）。
• 正确答案：A
• 深度解析：程序利用逆拓扑序由叶向根递推，动态通过 f[fa[i]] + f[i] + 1 合并更新，这是在线性时间内维护并求出树的直径（最远两点路径所经边数）的标准实现。
• 32. 当 n=7， 时，输出为（ ）。
• 正确答案：C
• 深度解析：该结构描述了一棵高度为 2 的满二叉树。最远路径从左侧最底层叶子（4 或 5）穿过根节点 1 贯穿到右侧最底层叶子（6 或 7），总耗费边数为 4。
• 33. 当 n=10，满足输出为 9 的合法输入种类数为（ ）。
• 正确答案：C
• 深度解析：要求直径为 9，即 10 个节点的树必须保持一条直线的长链结构。根据拓扑标号规则 ：节点 2 只能连接 1（1种选择）。此后每当按编号递增顺序加入一个新节点 （从 3 到 10）时，为了维持长链不发生分叉退化，它必须且只能接在当前已经生成的长链的两个端点节点之一。因此对于 3 到 10 每一个点，都面临恰好 2 种合法方向抉择。合法输入种类数 =  种。

四、 完善程序（每题 3 分，共 30 分）

(1) 平衡路线（BFS 奇环染色）

• 34. ① 处应填（ ）
• 正确答案：C
• 深度解析：此处为读入边权。后面第 37、38 行通过 w[i] > 0 和 w[i] < 0 显式判断。
• 35. ② 处应填（ ）
• 正确答案：D
• 深度解析：标准的 BFS 队列状态循环控制位。当头指针 hh 严格小于尾指针 tt 时，说明队列内部仍存在未拓展的节点，循环持续执行。
• 36. ③ 处应填（ ）
• 正确答案：B
• 深度解析：当 BFS 首次扫描拓展到没有被访问过的邻接点 y （即满足初始状态 d[y] == -1）时，其无权图的最短步数应该直接在父节点的最短步数基础上累加 1，即 d[x] + 1。
• 37. ④ 处应填（ ）
• 正确答案：A
• 深度解析：此处的 else if 分支对应邻接点 y 已经被访问过的情形。这是经典的 二分图染色冲突（检测奇环) 逻辑。当相连的两个相邻顶点拥有完全相同的颜色状态位（即满足 c[y] == c[x]）时，图中发现了非二分图架构的奇数闭环，因此立刻将合法标记置为 ok = false。
• 38. ⑤ 处应填（ ）
• 正确答案：C
• 深度解析：最小代价存在充要条件判定，满足以下两项之一即可：要么整个连通分量中由于存在奇环而导致无法二分（即 !ok 为真），此时我们总能通过在奇环内部多绕一圈来任意调整路径总数的奇偶性；或者（||），起止点在二分染色下的初始状态恰好相同（c[s] == c[t]）。结合两项即为 !ok || c[s] == c[t]。

(2) 格雷码优化枚举

• 39. ① 处应填（ ）
• 正确答案：C
• 深度解析：根据线性变换，这里初始化差值贡献系数 c[i] 应该赋值为 m - 2 * x[i]。因为在后续的位运算映射和格雷码状态取反更新中，通过如此赋值，可以在无需后续做复杂负号补偿的情况下，直接用第 48 行的加法公式完美闭合全局代价的极大化目标。
• 40. ② 处应填（ ）
• 正确答案：B
• 深度解析：此处的算法设计巧妙地利用了按位或 | 的单调递增性质，结合下一行的状态异或 g ^ lst 来在  时间内精准追踪变化的学生差异位。这是一个结合了高阶优化设计的代码变种。
• 41. ③ 处应填（ ）
• 正确答案：D
• 深度解析：变量 d 是当前格雷码状态与前一状态的异或差异。由于格雷码每次状态推进有且仅有一个比特位发生改变，因此 d 的二进制表示中必然有且仅有一个 1。利用内置底层高效函数 __builtin_ctzll(d) 统计尾随零个数，即可在常数时间内一步定位到具体变化的那个学生编号 k。
• 42. ④ 处应填（ ）
• 正确答案：A
• 深度解析：当学生状态发生翻转（1变0或0变1）时，局部所带来的代价符号方向发生反转。由于在第 47 行才执行状态取反 s[k] = -s[k]，所以在第 48 行进行累加时，必须利用翻转前的旧状态变量来完成差值步进补偿，增量大小即为 2LL * s[k] * c[k]。
• 43. ⑤ 处应填（ ）
• 正确答案：A
• 深度解析：全卷最具含金量的数论证明题。变量 v 是全体学生作答在当前题目上的加权贡献净总和。由于每个人的贡献不是  就是 ，最终和  的奇偶性必须与总人数  保持完全同奇偶。

我们可以给出完美的双状态分类决策证明表：

由表可见，只有 v >= (n & 1) 可以在所有奇偶边界下达成完全无死角、无漏选的自动化分流，故 A 为唯一完美的正确答案。