一、 单项选择题

1. 答案：D (8) 解析：x &= x - 1 是经典的位运算操作，用于清除二进制表示中最低位的 1。循环次数即为 x 的二进制中 1 的个数。$2026 = 1024 + 512 + 256 + 128 + 64 + 32 + 8 + 2$，其二进制为 11111101010，共包含 8 个 1，故循环 8 次，cnt 的值为 8。

2. 答案：D (102) 解析：构造哈夫曼树的过程是每次选取权值最小的两个结点合并：

• 合并 1, 2 $\rightarrow$ 3 (代价 3)。集合变为 $\{3, 3, 4, 5, 6, 7, 8\}$
• 合并 3, 3 $\rightarrow$ 6 (代价 6)。集合变为 $\{4, 5, 6, 6, 7, 8\}$
• 合并 4, 5 $\rightarrow$ 9 (代价 9)。集合变为 $\{6, 6, 7, 8, 9\}$
• 合并 6, 6 $\rightarrow$ 12 (代价 12)。集合变为 $\{7, 8, 9, 12\}$
• 合并 7, 8 $\rightarrow$ 15 (代价 15)。集合变为 $\{9, 12, 15\}$
• 合并 9, 12 $\rightarrow$ 21 (代价 21)。集合变为 $\{15, 21\}$
• 合并 15, 21 $\rightarrow$ 36 (代价 36)。 带权路径长度 (WPL) 等于所有非叶子结点的权值之和：$3 + 6 + 9 + 12 + 15 + 21 + 36 = 102$。

3. 答案：C (301) 解析：计算 1 到 1000 中数字 "1" 出现的次数：

• 个位为 1：每 10 个数出现 1 次，共 $1000 / 10 = 100$ 次。
• 十位为 1：每 100 个数出现 10 次，共 $1000 / 100 \times 10 = 100$ 次。
• 百位为 1：每 1000 个数出现 100 次，共 100 次。
• 千位为 1：数字 1000 贡献 1 次。 总计：$100 + 100 + 100 + 1 = 301$ 次。

4. 答案：D (20) 解析：这是一个部分错排问题。

• 第一步：从 5 封信中选出 2 封装对的信，方案数为 $C_5^2 = 10$。
• 第二步：剩余的 3 封信必须全部装错（错排），3 个元素的错排数 $D_3 = 2$。
• 总方案数：$10 \times 2 = 20$ 种。

5. 答案：A (29) 解析：寻找 $3^k \bmod 100$ 的周期。 $3^1=3, 3^2=9, 3^3=27, 3^4=81, 3^5=43, 3^6=29, 3^7=87, 3^8=61, 3^9=83, 3^{10}=49, \dots, 3^{20} \equiv 1 \pmod{100}$。 周期为 20。$2026 \bmod 20 = 6$。 因此 $3^{2026} \equiv 3^6 = 729 \equiv 29 \pmod{100}$。

6. 答案：C (34) 解析：这是经典的区间 DP（石子合并）。设 $dp[i][j]$ 为合并第 $i$ 到第 $j$ 堆的最小代价，$S[i]$ 为前缀和。

• 长度 2：$dp[1][2]=5, dp[2][3]=4, dp[3][4]=5, dp[4][5]=7$
• 长度 3：$dp[1][3]=\min(0+4, 5+0) + 8 = 12$；$dp[2][4]=\min(0+5, 4+0) + 6 = 10$；$dp[3][5]=\min(0+7, 5+0) + 10 = 15$
• 长度 4：$dp[1][4]=\min(0+10, 5+5, 12+0) + 10 = 20$；$dp[2][5]=\min(0+15, 4+7, 10+0) + 11 = 21$
• 长度 5：$dp[1][5]=\min(dp[1][1]+dp[2][5], dp[1][2]+dp[3][5], dp[1][3]+dp[4][5], dp[1][4]+dp[5][5]) + 15 = \min(0+21, 5+15, 12+7, 20+0) + 15 = \min(21, 20, 19, 20) + 15 = 19 + 15 = 34$。

7. 答案：A (3 和 4) 解析：

• sum(11)：$11$ 的二进制为 1011。访问下标依次为 $11 \rightarrow 11 - \text{lowbit}(11) = 10 \rightarrow 10 - \text{lowbit}(10) = 8$。共访问 3 个下标。
• add(3, x)：$3$ 的二进制为 0011。访问下标依次为 $3 \rightarrow 3 + \text{lowbit}(3) = 4 \rightarrow 4 + \text{lowbit}(4) = 8 \rightarrow 8 + \text{lowbit}(8) = 16$。共访问 4 个下标。

8. 答案：B (8) (注：原题号标为9，此处按顺序修正为8) 解析：顶点 1 必须在 2 和 3 之前，2 和 3 的相对顺序任意，故 $\{1, 2, 3\}$ 的合法拓扑序有 2 种（1,2,3 和 1,3,2）。孤立点 4 可以插入到这 3 个元素的 4 个空隙中（包括首尾）。总方案数为 $2 \times 4 = 8$ 种。

9. 答案：A ($O(n \log n)$) (注：原题号标为9) 解析：根据递归树分析，每层的代价之和为 $O(n)$。递归树的最深分支由 $T(2n/3)$ 决定，深度为 $\log_{3/2} n$。总时间复杂度为 $O(n \log n)$。

10. 答案：D (直径 7，重心为结点 1) 解析：画出树的结构：1 连接 2 和 3；2 连接 4 和 5，5 连接 9；3 连接 6，6 连接 7，7 连接 8。

• 最长路径（直径）为 $9-5-2-1-3-6-7-8$，共经过 7 条边，直径为 7。
• 重心是删除该点后，最大连通块最小的点。以 1 为根，其子树大小分别为 4（包含 2,4,5,9）和 4（包含 3,6,7,8），最大子树为 4，是所有结点中最小的，故重心为 1。

11. 答案：C (4) 解析：对于有向无环图（DAG），要使其变为强连通图，至少需要添加的边数为 $\max(\text{入度为0的顶点数}, \text{出度为0的顶点数})$。本题中入度为 0 的有 3 个，出度为 0 的有 4 个，故至少需要添加 $\max(3, 4) = 4$ 条边。

12. 答案：C (132) 解析：$n$ 个结点的不同形态二叉树数量由卡特兰数 $C_n$ 给出。$C_6 = \frac{1}{6+1} \binom{2 \times 6}{6} = \frac{1}{7} \times 924 = 132$。

13. 答案：B (6) 解析：字符串 $S = \text{"ababaabab"}$，长度为 9。寻找既是真前缀又是真后缀的非空子串：

• 长度 2："ab" == "ab" (匹配)
• 长度 4："abab" == "abab" (匹配) 其他长度均不匹配。长度之和为 $2 + 4 = 6$。

14. 答案：C (变为满足 $i<j$ 且 a[i]≥a[j] 的数对个数) 解析：原代码中 a[i] <= a[j] 时不统计逆序对。若改为 a[i] < a[j]，则当 a[i] == a[j] 时，程序会进入 else 分支并执行 ans += mid - i + 1。这相当于把相等的元素也当作逆序对进行了统计，因此统计结果变成了满足 $i < j$ 且 $a[i] \ge a[j]$ 的数对总数。

15. 答案：B (376) 解析：快速幂计算 $2^{100} \bmod 1000$。 $2^{10} = 1024 \equiv 24$ $2^{20} \equiv 24^2 = 576$ $2^{40} \equiv 576^2 = 331776 \equiv 776$ $2^{80} \equiv 776^2 = 602176 \equiv 176$ $2^{100} = 2^{80} \times 2^{20} \equiv 176 \times 576 = 101376 \equiv 376 \pmod{1000}$。

---

二、 阅读程序

（1）CRC 校验码计算

16. 答案：$\checkmark$ (正确) 解析：输入 32 个 '0'，数组 a 全为 0。循环中 if (a[i] == 0) continue; 会跳过所有异或操作，最后输出的后 12 位也全为 0。

17. 答案：$\checkmark$ (正确) 解析：该程序模拟了模 2 除法。由于生成多项式 gen 的最高位 gen[0] 为 1，每次遇到 a[i] == 1 时进行异或，都会将当前的 a[i] 清零。因此处理完前 32 位后，a[0] 到 a[31] 一定全为 0。

18. 答案：$\times$ (错误) 解析：a 是全局数组，C++ 保证全局变量默认初始化为 0。因此即使删除了显式补 0 的循环，a[32..43] 依然是 0，程序的逻辑和输出结果不会发生改变。题目说“会改变”，故该说法错误。

19. 答案：C 解析：gen 数组有 13 个元素，代表一个 13 位的生成多项式（除数），其中 gen[0] 对应最高位（$x^{12}$ 的系数）。

20. 答案：B 解析：程序先将 32 位输入串后补 12 个 0，然后通过模 2 除法（异或操作模拟）除以 13 位的生成多项式，最后输出的正是 12 位的余数（即 CRC 校验码）。

21. 答案：C 解析：删除 continue 后，程序依然会按固定逻辑执行完所有循环，不会发生数组越界或崩溃，因此能正常输出 12 位串。但由于每次无条件异或，破坏了原有的条件分支逻辑，其输出结果失去了与原输入串 $s$ 的有效校验关联。

（2）ST 表求区间 GCD

22. 答案：$\checkmark$ (正确) 解析：查询区间 $[2, 5]$ 对应元素 $\{2, 6, 3, 3\}$。$\gcd(2, 6, 3, 3) = 1$，程序输出 1，正确。

23. 答案：$\checkmark$ (正确) 解析：当 $L=R$ 时，区间长度为 1，lg[1] = 0。查询时计算 $\gcd(dp[L][0], dp[L][0]) = \gcd(a[L], a[L]) = a[L]$，正确。

24. 答案：$\times$ (错误) 解析：一组正整数的最大公约数 (GCD) 一定不大于（小于或等于）这组数中的最小值，而不是“不小于”。

25. 答案：B 解析：ST 表的定义，dp[i][j] 存储的是从下标 $i$ 开始，长度为 $2^j$ 的区间的最大公约数。

26. 答案：B 解析：建表过程包含两层循环，外层 $j$ 从 1 到 $\lfloor \log_2 n \rfloor$，内层 $i$ 遍历 $n$ 个起点，总时间复杂度为 $O(n \log n)$。

27. 答案：D ($[33, 64]$) 解析：根据代码逻辑：if (pw[t + 1] >= i) lg[i] = t; else { t++; lg[i] = t; }。

• 当 $i=32$ 时，$pw[5]=32 \ge 32$ 成立，lg[32] = 4。
• 当 $i=33$ 时，$32 < 33$，进入 else，$t$ 变为 5，lg[33] = 5。
• 当 $i=64$ 时，$pw[6]=64 \ge 64$ 成立，lg[64] = 5。
• 当 $i=65$ 时，$64 < 65$，$t$ 变为 6，lg[65] = 6。 故 lg[x] = 5 的范围是 $[33, 64]$。

（3）求树的直径

28. 答案：$\checkmark$ (正确) 解析：输入构成一条链 $1-2-3-4-5$。逆序遍历更新时，ans 会依次记录经过的边数，最终 ans 累加到 4，输出 4，正确。

29. 答案：$\times$ (错误) 解析：f[1] 记录的是从根结点 1 向下延伸的最长路径长度，而 ans 记录的是整棵树的直径。如果树的直径完全位于某个子树中（不经过根结点 1），则 ans 会大于 f[1]。

30. 答案：$\times$ (错误) 解析：原逻辑是先使用旧的 f[fa[i]] 更新 ans，再更新 f[fa[i]]。若交换顺序，更新 ans 时会使用已经被当前子树更新过的新的 f[fa[i]]，导致计算出的路径不再是经过 fa[i] 的两条不相交子树路径之和，逻辑错误。

31. 答案：A 解析：该算法是经典的树形 DP 求直径方法。ans 维护的是树中距离最远的两个结点之间路径所经过的边数。

32. 答案：C (4) 解析：树的结构为：1 连接 2, 3；2 连接 4, 5；3 连接 6, 7。这是一个深度为 3 的满二叉树。最长路径如 $4-2-1-3-6$，共经过 4 条边，直径为 4。

33. 答案：C (256) 解析：$n=10$ 且直径为 9，说明该树必须是一条链。在满足 $fa[i] < i$ 的约束下构造链：结点 1 固定为端点；结点 2 只能连 1；从结点 3 到结点 10，每个新结点 $k$ 都可以选择连接到当前已形成链的两个端点之一。因此方案数为 $1 \times 2 \times 2 \dots \times 2 = 2^{10-2} = 2^8 = 256$ 种。

---

三、 完善程序

（1）平衡路径

34. 答案：C (op[0] == '+' ? 1 : -1) 解析：后续代码通过 w[i] > 0 和 w[i] < 0 来判断图中是否同时存在 '+' 和 '-' 边，因此需要将字符映射为 1 和 -1。

35. 答案：D (hh < tt) 解析：这是标准 BFS 队列的循环条件，当队头指针小于队尾指针时，说明队列非空，继续遍历。

36. 答案：B (d[x] + 1) 解析：BFS 中，未被访问过的相邻结点 y 的距离等于当前结点 x 的距离加 1。

37. 答案：A (c[y] == c[x]) 解析：c 数组用于二分图染色（0 和 1）。如果相邻结点 y 已被访问过，且其颜色 c[y] 与当前结点 x 的颜色 c[x] 相同，说明图中存在奇环，不是二分图，标记 ok = 0。

38. 答案：C (!ok || c[s] == c[t]) 解析：若图中存在奇环（!ok），则可以通过绕环改变路径奇偶性，总能调整到权值为 0。若图是二分图（ok），则任意两点间的所有路径长度奇偶性相同。若起点和终点同色（c[s] == c[t]），路径长度必为偶数，也可以通过调整达到权值 0。若异色，路径长度必为奇数，最小权值至少为 1。

（2）标准答案

39. 答案：C (m - 2 * x[i]) 解析：目标函数经过数学变换后，可以转化为关于学生状态 $s[i]$ 的线性组合。初始化时，c[i] 存储的是与预期得分 $x_i$ 相关的偏移量系数，推导可得其值为 $m - 2x_i$。

40. 答案：B (mask ^ (mask >> 1)) 解析：这是生成格雷码 (Gray Code) 的标准公式，用于在状态空间中进行相邻状态（仅改变 1 位）的遍历，从而优化状态转移的计算量。

41. 答案：D (__builtin_ctzll(d)) 解析：d = g ^ lst 表示当前状态与上一个状态不同的位。__builtin_ctzll(d) 返回 d 的二进制表示中末尾连续 0 的个数，即发生状态翻转的学生索引 $k$。

42. 答案：A (2ll * s[k] * c[k]) 解析：当学生 $k$ 的状态 $s[k]$ 翻转时，目标函数中的相关项需要更新。由于是从 $-s[k]$ 变为 $s[k]$（或反之），变化量为 $2 \times s[k]$，乘以系数 $c[k]$ 即为对总和 $C$ 的修正量。

43. 答案：A (v >= (n & 1)) 解析：在确定第 $j$ 题的最终答案时，v 代表了选择 'A' 时的某种得分优势。考虑到 $n$ 的奇偶性对平局时的默认选择有影响，条件 v >= (n & 1) 能够完美处理奇偶边界情况（$n$ 为偶数时 v >= 0，$n$ 为奇数时 v >= 1），从而决定最终填入 'A' 还是 'B'。