提高组 CSP-S 2026 初赛模拟卷 9

第 i 层 $k^{i}$ 个， $\sum_{i=0}^{h} k^{i} = (k^{h+1} - 1)/(k-1)$。

常识。选项 B 是运算器的功能，选项 D 是输入设备的功能，选项 E 是存储器的功能。选项 A、B、D、E 加输出设备是计算机的五个基础组件。

队列不改变元素的出入顺序，所以出栈顺序就是 $e_{2}, e_{4}, e_{3}, e_{6}, e_{5}, e_{1}$。在入栈顺序为从小到大时，栈的最小容量就是出栈序列的最长下降子序列（LDS）长度，这里是 3（如 $e_{6}, e_{5}, e_{1}$）。这是因为任何下降子序列必然同时出现在栈中，而任何时刻栈中的元素一定也是出栈序列中的下降子序列。

完全二叉树至多只有 1 个一度节点，而任何二叉树都满足 $n_{2}=n_{0}+1$（ $n_{i}$ 表示 i 度节点个数），加上 $n_{0}+n_{1}+n_{2}=2019$， $n_{1}=0,1$，解出 $n_{0}=1010$。

针对这个数据规模手动模拟 + 排除法即可，例如简单的选择排序（每次将最小的换到头部）正好只需要 5 次交换。一般性的做法是用最终排名替代每个数，即 35247168，其作为一个置换有 3 个循环节：(132576)(4)(8)，每次交换至多且总可以增加 1 个，最后要变成 8 个，8 - 3 = 5。另外，选项 D 是只能交换相邻两个元素时的答案，也就是逆序对数，也等于冒泡排序的交换次数。

最笨的方法是暴力枚举（也还好）。较好的方法是标数法（参见下页图），相当于从坐标 $(0,0)$ 沿右下方向走到 $(6,6)$，且全程位于直线 y = x 和 y = x - 3 之间的方案数。

除了暴力转进制，讨巧的办法是：整数部分是偶数，故可排除选项 A 和 B；小数部分超过一半（十进制 0.5），也就是四进制的 0.2，故可排除选项 C。

需要记忆 'a' 的 ASCII 码（十进制）为 97，则 'm' 为 109 = 16 × 6 + 13。

哈夫曼数没有1度节点，而2度节点比叶节点少一个。

从一端（假设为 A 种鸟）出发，每经过一个两端不同的线段，就由 A 变 B 或由 B 变 A，而最后变回 A，所以需要偶数次。

唯一获得图灵奖的华裔科学家是姚期智。

常识。ROM 是内存中的只读部分，信息永久保存。

逐个代入验证即可。

因为前序/后序遍历序列 + 中序遍历序列可以确定树结构，所以逐个选项检查即可，画出树结构并验证。选项 C 中，利用前序 + 中序，确定根节点为 1，右子树的 3 个遍历序列是：前序 3576，中序 7563，后序 7563。后序和中序一样，说明右子树只能是一条左向的链，那么前序序列应该是 3657。

类似于满二叉树，只是非叶节点分二叉和三叉，有 10 个叶节点，则倒数第 2 层要么是 5 个二叉节点，要么是 2 个二叉节点 +2 个三叉节点。不管是哪种情况，再往上都只能有 3 个节点了（5 = 2 + 3 或 4 = 2 + 2）。所以只有 2 种可行解：7 或 8。

每轮操作至少会减少两个小写字母，有限次操作后一定会出现第8行的 if 不再命中，于是就会触发 break。

s.size() 是无符号类整数，理论上，如果 s.size()=0，减一会造成错误结果。但这里是 cin 输入的，cin 不可能输入一个空串。

最外层循环最坏情况下会进行 $O(n)$ 轮（例如 $s = "aabbaabbaabb..."$），看似确实是 $O(n^2)$，但注意每次 i 循环到第一段相同字符就 break 了。而后面的前后调换操作将 j 后面的部分挪到首部，相当于下一轮循环实际上接着上一轮的 j 继续枚举。所以实际上原字符串全程只被遍历了一次，这个 for 的复杂度是 $O(n)$。

j-i+1>9 以后，就会出现 '0' ~ '9' 以外的其他字符（包括不可见字符），但不会出错。并且因为 t 的长度总是 2，每轮循环 s 的长度严格减小，所以不会出现死循环。

前面已说明过。

aabbccdd → bbccddA2 → cccddA2B2 → ddA2B2C2 → A2B2C2D2.

输入约束没有限制不存在自环（a=b），如果输入的图只包含自环，那么是不存在任何简单路径的，ans 将保持初始值 0。

语法常识。~ 表示二进制按位取反，包括符号位。~x 如果为 false，说明 x 的每一位都是 1，这表示 -1。

此代码没有做任何搜索优化，所以枚举量随着 n 增大呈指数级增长，n=100 时不可能在 1 秒内运行完成。

连通不代表存在长 n 的简单路径，例如输入是一棵有分岔的无根树，这时候就不可能出现 visited 都为 true 的情况。

因为是暴力枚举所有路径，理论上最坏情况（如完全图）相当于枚举 1..n 的全排列，所以是 n!。

$2 \rightarrow 4 \rightarrow 1 \rightarrow 3$。4个点图的简单路径至多有3条边，这已经是最长的3条且可行，所以就是最优解。

虽然输入在 1..1000000 范围内，但运算过程中会进位，特别是当 popcnt(n) 很小时，将很快进位，并有可能溢出到 int 的符号位。参见下面第 33 题的解析演示。

执行 work(0)，则 s，r，x^~r 都为 0。由于除以 s，直接触发除数为 0，运行时异常，但不会出现死循环。

在 work() 中， r = s + x > x，而结果又是 r 按位与一个数，也不可能变小。但注意，在一些特殊情况下，按题目的输入范围是可能出现溢出的，例如 n=1，k=100。

这里涉及四次运算，其默认优先级为：除法 > 右移 > 按位异或 > 按位或。而要求的顺

序为：按位异或＞右移＞除法＞按位或。所以最内层、中间层的括号必须保留以反转优先级；最外层的可以去掉，因为除法和按位或的相对优先级与默认的一致。当然，在实际编码中，对于这种复杂运算是推荐把括号都写全的。

n=1 的效果是每次 work() 会乘 2（可以直接模拟证明），100 次 int 早就溢出了，unsigned int 溢出相当于模 $2^{32}$，所以 n 会变成 0，而这又会触发第 29 题中所述的除数为 0 的情况。

从 00000011 执行 14 次，过程如下。

$$00000011$$$$00000110$$$$00001001$$$$00001010$$$$00010001$$$$00010010$$$$00011000$$$$00100001$$$$00100010$$$$00110000$$

当前深度与目前得到的最深深度相同，则最深的个数加一。

循环求 a[left]..a[right] 的最小值 min，下标为 a[j]，找到更新的更新到 j。

左子树为 left, j-1 这段，进入一棵子树深度加一。

类似上题。

初始时，中序遍历为整个序列 a[1]..a[n]。根据 for (int i=left; i<=right; i++)

left, right 两端是都包含的，所以传入 1,n。而 deep 的初始值为根节点的深度，题目说了是 1。

此处是链式前向星加边，边（u, v）会被插入到头指针 hd[u] 前面（虽然是无向图，但后面一句是 hd[u]，所以只能视 u 为起点，v 为终点）。

前向星的终点，nxt 指针一般取值为 0 或 -1，本题中 nxt（从 hd 获得的值）并没有初始化为 -1 等操作，所以默认值是 0。这里当 i 非零时则继续循环。

因为输入是双向图，所以需避免沿进入的边走回到父节点去。注意本题因为保证没有重边，所以这样写才是对的。如果有重边（2阶环），这么写会误跳过重边。这时候 fa 应该传边的 id 进来，才能区分 v==fa 是反向边还是重边。

这里 v 是 u 的祖先，从 v 到 u 沿途的节点（包括 u, v）构成环，所以环上的节点数等于深度差加一。

主函数应从根节点开始调用，因为前面写的是 d[1]=1，所以这里 1 是根节点，第一个参数要传 1。第二个参数是父节点编号，但根节点没有父节点，根据 ③ 处的选项，这里只要传入一个 1..n 之外的数就行。