GESP 客观题评测系统

2023 CCF CSP-S 第一轮（提高级 C++）

CSPS-2023-R1

试卷解析总览，可直接查看每题答案与解析。

一、单项选择题

第 1 题（单选题，2 分）

在 Linux 系统终端中，以下哪个命令用于创建一个新的目录？（）

newdir

mkdir

create

mkfolder

正确答案B

解析详情

【答案】B

【考点】Linux 基础命令

【解析】在 Linux 中，`mkdir` (make directory) 是用于创建新目录的标准命令。选项 A、C、D 都不是合法的标准命令。

【易错点】误以为存在 `create` 等自然语义命令。

第 2 题（单选题，2 分）

0, 1, 2, 3, 4 中选取 4 个数字，能组成（）个不同四位数。（注：最小的四位数是 1000，最大的四位数是 9999。）

120

正确答案A

解析详情

【答案】A

【考点】排列组合

【解析】第一位不能为 0，有 4 种选法；剩下三个位置从其余 4 个数中选 3 个排列，有 $A_4^3 = 24$ 种。总数为 $4 \times 24 = 96$ 。

【易错点】忘记最高位不能为 0 的限制。

第 3 题（单选题，2 分）

假设 n 是图的顶点的个数，m 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 $m = \Theta(n)$ 的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小。

( )

O(m\sqrt{\log n\cdot\log\log n})

O(n^{2}+m)

O(n^{2}/\log m+m\log n)

O(m+n\log n)

正确答案A

解析详情

【答案】A

【考点】渐近时间复杂度分析

【解析】代入 $m = \Theta(n)$ ，各选项化为：A 选项 $O(n\sqrt{\log n\cdot\log\log n})$ ；B 选项 $O(n^2)$ ；C 选项 $O(n^2/\log n)$ ；D 选项 $O(n\log n)$ 。显然 A 选项的增长级别低于 D 选项的 $O(n\log n)$ ，渐近时间复杂度最小。

【易错点】对复杂对数函数的渐近上界不熟悉。

第 4 题（单选题，2 分）

假设有 n 根柱子，需要按照以下规则依次放置编号为 1、2、3、… 的圆环：每根柱子的底部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有 4 根柱子时，最多可以放置（）个圆环。

正确答案C

解析详情

【答案】C

【考点】图论与搜索

【解析】这是一个经典的放圆环问题，要求相邻两数之和为完全平方数。根据贪心构造，当有 4 根柱子时，按顺序放置，最多可以放到数字 11，当要放 12 时，其与已有顶部元素的和均无法构成完全平方数，且所有 4 根柱子均已占用。

【易错点】未考虑全面，过早认为无法继续放置。

第 5 题（单选题，2 分）

以下对数据结构的表述不恰当的一项是：（）。

队列是一种先进先出（FIFO）的线性结构

哈夫曼树的构造过程主要是为了实现图的深度优先搜索

散列表是一种通过散列函数将关键字映射到存储位置的数据结构

二叉树是一种每个结点最多有两个子结点的树结构

正确答案B

解析详情

【答案】B

【考点】数据结构基础概念

【解析】哈夫曼树（Huffman Tree）是用于构造前缀编码、实现数据压缩的最优二叉树，与图的深度优先搜索（DFS）毫无关系。图的 DFS 对应的是 DFS 生成树。

【易错点】将不同的树结构应用场景混淆。

第 6 题（单选题，2 分）

以下连通无向图中，（）一定可以用不超过两种颜色进行染色。

完全三叉树

平面图

边双连通图

欧拉图

正确答案A

解析详情

【答案】A

【考点】二分图染色

【解析】无向图能用不超过两种颜色染色，当且仅当该图是二分图（不包含奇环）。完全三叉树是一棵树，不包含任何环，因此必然是二分图。而平面图、边双连通图、欧拉图均可能包含奇环。

【易错点】误认为某些特殊结构的图一定没有奇环。

第 7 题（单选题，2 分）

最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列 $X = \{x_1, x_2, x_3, \cdots, x_m\}$ 和 $Y = \{y_1, y_2, y_3, \cdots, y_n\}$ ，最长公共子序列（LCS）问题的目标是找到一个最长的新序列 $Z = \{z_1, z_2, z_3, \cdots, z_k\}$ ，使得序列 $Z$ 既是序列 $X$ 的子序列，又是序列 $Y$ 的子序列，且序列 $Z$ 的长度 $k$ 在满足上述条件的序列里是最大的。（注：序列 $A$ 是序列 $B$ 的子序列，当且仅当在保持序列 $B$ 元素顺序的情况下，从序列 $B$ 中删除若干个元素，可以使得剩余的元素构成序列 $A$ 。）则序列 “ABCAAAABA” 和 “ABABCBABA” 的最长公共子序列长度为（）。

正确答案C

解析详情

【答案】C

【考点】动态规划求 LCS

【解析】经过 LCS 动态规划推导或手动匹配，可找出最长公共子序列为 "AB C A B A" 或 "AB A A B A" 等，其最大长度为 6。例如匹配 "AB" + "C" + "A" + "B" + "A"，长度为 6。

【易错点】手动模拟时漏掉部分字符导致少算长度。

第 8 题（单选题，2 分）

一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下：玩家第一次掷出 x 点，得到 2x 元；第二次掷出 y 点，当 y=x 时玩家会失去之前得到的 2x 元，而当 y≠x 时玩家能保住第一次获得的 2x 元。上述 x, y∈{1,2,3,4,5,6}。例如：玩家第一次掷出 3 点得到 6 元后，但第二次再次掷出 3 点，会失去之前得到的 6 元，玩家最终收

益为0元；如果玩家第一次掷出3点、第二次掷出4点，则最终收益是6元。假设骰子掷出任意一点的概率均为1/6，玩家连续掷两次骰子后，所有可能情形下收益的平均值是多少？（）

7 元

\frac{35}{6}

元

\frac{16}{3}

元

\frac{19}{3}

元

正确答案B

解析详情

【答案】B

【考点】数学期望

【解析】第一次掷出 $x$ 的期望收益为 $2 \times \frac{7}{2} = 7$ 。第二次若等于 $x$ （概率 1/6），收益归 0；若不等于 $x$ （概率 5/6），收益保持为 $2x$ 。因此最终收益期望为 $\frac{5}{6} \times 7 = \frac{35}{6}$ 元。

【易错点】没有理清两次投掷概率之间的独立与条件关系。

第 9 题（单选题，2 分）

假设我们有以下的 C++ 代码：

int a = 5, b = 3, c = 4;
bool res = a & b || c ^ b && a | c;

请问，res 的值是什么？（）

提示：在 C++ 中，逻辑运算的优先级从高到低依次为：逻辑非（!）、逻辑与（&&）、逻辑或（||）。位运算的优先级从高到低依次为：位非（~）、位与（&）、位异或（^）、位或（|）。同时，双目位运算的优先级高于双目逻辑运算；逻辑非和位非优先级相同，且高于所有双目运算符。

true

false

正确答案A

解析详情

【答案】A

【考点】C++ 运算符优先级

【解析】根据优先级规则：位运算优先于逻辑运算，且按 `~`, `&`, `^`, `|` 顺序。原式先算 `a & b` (=5 & 3 = 1)、`c ^ b` (=4 ^ 3 = 7)、`a | c` (=5 | 4 = 5)。式子化为 `1 || 7 && 5`。再根据 `&&` 优先于 `||`，算 `7 && 5` 为 true(1)，最后 `1 || 1` 结果为 true。

【易错点】混淆位运算符和逻辑运算符的优先级顺序。

第 10 题（单选题，2 分）

假设快速排序算法的输入是一个长度为 n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下快速排序行为？

( )

快速排序对于此类输入的表现最好，因为数组已经排序。

快速排序对于此类输入的时间复杂度是

O(n\log n)

。

快速排序对于此类输入的时间复杂度是

O(n^{2})

。

快速排序无法对此类数组进行排序，因为数组已经排序。

正确答案C

解析详情

【答案】C

【考点】快速排序时间复杂度

【解析】快速排序在每次选择第一个元素为基准时，如果输入数组已经是有序的，那么每次划分都将极端不平衡（左侧 0 个元素，右侧 n-1 个元素），递归树退化为链状，时间复杂度退化为 $O(n^2)$ 。

【易错点】误认为有序数组是快速排序的最优情况。

第 11 题（单选题，2 分）

以下哪个命令，能将一个名为 “main.cpp” 的 C++源文件，编译并生成一个名为 “main” 的可执行文件？（）

g++ -o main main.cpp

g++ -o main.cpp main

g++ main -o main.cpp

g++ main.cpp -o main.cpp

正确答案A

解析详情

【答案】A

【考点】Linux GCC 编译命令

【解析】在 GCC 编译器中，`-o` 参数用于指定输出的可执行文件名称。因此 `g++ -o main main.cpp` 表示将 `main.cpp` 编译并输出为名为 `main` 的可执行文件。

【易错点】将输入源文件和输出可执行文件的位置放反。

第 12 题（单选题，2 分）

在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心？( )。

4 个结点的树

6 个结点的树

7 个结点的树

8 个结点的树

正确答案C

解析详情

【答案】C

【考点】树的重心性质

【解析】树的重心有一个经典性质：若树有奇数个节点，则其重心必然唯一；若有偶数个节点，则重心可能有两个（且这两个重心必然相邻）。因此 7 个结点的树一定只有一个重心。

【易错点】不了解树重心的奇偶节点数量相关性质。

第 13 题（单选题，2 分）

如图是一张包含 6 个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这 6 个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？（）

正确答案C

解析详情

【答案】C

【考点】图的拓扑排序

【解析】有向图不存在拓扑序意味着图中存在环。通过分析图结构可知，必须打破所有环才能进行拓扑排序。观察图中必定有 3 条边，删除其中任意一条都可以破坏这个唯一的环结构。

【易错点】找漏图中的环或者找错构成环的关键边。

第 14 题（单选题，2 分）

若 $n = \sum_{i=0}^{k} 16^i \cdot x_i$ ，定义 $f(n) = \sum_{i=0}^{k} x_i$ ；其中 $x_i \in \{0, 1, \cdots, 15\}$ 。对于给定自然数 $n_0$ ，存在序列 $n_0, n_1, n_2, \cdots, n_m$ ，其中对于 $1 \leq i \leq m$ 都有 $n_i = f(n_{i-1})$ ，且 $n_m = n_{m-1}$ ，称 $n_m$ 为 $n_0$ 关于 $f$ 的不动点。问在 $100_{16}$ 至 $1A_{0_{16}}$ 中，关于 $f$ 的不动点为 9 的自然数个数为（）。

10

正确答案B

解析详情

【答案】B

【考点】不动点与数位和特征

【解析】函数 $f(n)$ 表示对 $n$ 的 16 进制各位数求和，这类似于 10 进制中的数字根，结果模 15 与原数模 15 同余（ $n \equiv f(n) \pmod{15}$ ）。不动点为 9 意味着 $n \equiv 9 \pmod{15}$ 。区间为 $256$ 到 $416$ ，计算可知符合条件的数共有 11 个。

【易错点】未发现 $f(n)$ 本质是求模 15 的同余特征。

第 15 题（单选题，2 分）

现在用如下代码来计算 $x^n$ ，其时间复杂度为（）。

double quick_power(double x, unsigned n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    return quick_power(x, n / 2)
    * quick_power(x, n / 2)
    * ((n & 1) ? x : 1);
}

O(n)

O(1)

O(\log n)

O(n\log n)

正确答案A

解析详情

【答案】A

【考点】递归算法时间复杂度

【解析】代码中 `quick_power(x, n / 2)` 被调用了两次且未记忆化。递推式为 $T(n) = 2T(n/2) + O(1)$ 。根据主定理，其时间复杂度为 $O(n)$ ，而非标准的快速幂 $O(\log n)$ 。

【易错点】看到二分就认为是 $O(\log n)$ ，忽略了重复递归计算。

二、阅读程序（1）

#include <iostream>
using namespace std;

unsigned short f(unsigned short x) {
    x ^= x << 6;
    x ^= x >> 8;
    return x;
}

int main() {
    unsigned short x;
    cin >> x;
    unsigned short y = f(x);
    cout << y << endl;
    return 0;
}

假设输入的 x 是不超过 65535 的自然数，完成下面的判断题和单选题：

第 16 题（判断题，1.5 分）

当输入非零时，输出一定不为零。（）

正确答案正确

解析详情

【答案】正确

【考点】位运算

【解析】函数 `f(x)` 经过 `x ^= x << 6` 和 `x ^= x >> 8`。由于 x 是非零的 16 位无符号整数，左移 6 位并异或后，其非零的最高位或最低位特征不会完全抵消为 0，右移同理，因此非零输入不可能变成 0。

【易错点】误以为多次位运算异或操作可能会将所有位清零。

第 17 题（判断题，2 分）

将 f 函数的输入参数的类型改为 unsigned int，程序的输出不变。（）

正确答案错误

解析详情

【答案】错误

【考点】数据类型与位运算

【解析】`unsigned short` 通常为 16 位，而 `unsigned int` 通常为 32 位。对于 32 位整数，`x << 6` 不会在 16 位边界处截断，这会导致高 16 位出现有效数据，且后续异或操作的结果与 16 位时不同。

【易错点】忽略不同整型类型在左移操作时位宽溢出截断行为的差异。

第 18 题（判断题，1.5 分）

当输入为 “65535” 时，输出为 “63”。（）

正确答案正确

解析详情

【答案】正确

【考点】位运算模拟

【解析】当 x = 65535（即全 1），`x << 6` 得到末尾 6 个 0 的数。异或后 x 变成仅末尾 6 位为 1（即 63）。接着 `x >> 8` 得到 0，再异或结果仍为 63。

【易错点】未进行二进制展开，直接用十进制猜测结果。

第 19 题（判断题，1.5 分）

当输入为 “1” 时，输出为 “64”。（）

单选题

正确答案错误

解析详情

【答案】错误

【考点】位运算模拟

【解析】输入为 1，`1 << 6` 得到 64，异或后 x 变成 65（1000001）。再右移 8 位得到 0，最终异或结果仍为 65，而不是 64。

【易错点】计算异或时忘记原有的低位 1，误算为 64。

第 20 题（单选题，3 分）

当输入为 “512” 时，输出为（）。

“33280”

“33410”

“33106”

“33346”

正确答案B

解析详情

【答案】B

【考点】位运算跟踪

【解析】x = 512。第一步 `x << 6` 等于 32768，异或后 x = 33280。第二步 `x >> 8` 等于 130，异或后 x = 33280 ^ 130 = 33410。

【易错点】移位或者异或计算时发生算术错误。

第 21 题（单选题，3 分）

当输入为 “64” 时，执行完第 5 行后 x 的值为（）。

“8256”

“4130”

“4128”

“4160”

正确答案D

解析详情

【答案】D

【考点】位运算跟踪

【解析】x = 64。第一步 `x << 6` 为 4096，异或后 x = 64 ^ 4096 = 4160。第 5 行执行完即为第一步位运算后。

【易错点】没有仔细审题，算成了整个函数的最终输出。

二、阅读程序（2）

#include <iostream>

#include <cmath>

#include <vector>

#include <algorithm>

using namespace std;

06

long long solve1(int n) {

vector<bool> p(n+1, true);

vector<long long> f(n+1, 0), g(n+1, 0);

f[1] = 1;

for (int i = 2; i * i <= n; i++) {

if (p[i]) {

vector<int> d;

for (int k = i; k <= n; k *= i) d.push_back(k);

reverse(d.begin(), d.end());

for (int k : d) {

for (int j = k; j <= n; j += k) {

if (p[j]) {

p[j] = false;

f[j] = i;

g[j] = k;

}

}

}

}

}

for (int i = sqrt(n) + 1; i <= n; i++) {

if (p[i]) {

f[i] = i;
g[i] = i;
}
}
long long sum = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);
sum += f[i];
}
return sum;
}
40
long long solve2(int n) {
long long sum = 0;
for (int i = 1; i <= n; i++) {
sum += i * (n / i);
}
return sum;
}
48
int main() {
int n;
cin >> n;
cout << solve1(n) << endl;
cout << solve2(n) << endl;
return 0;
}

假设输入的 n 是不超过 1000000 的自然数，完成下面的判断题和单选题：

第 22 题（判断题，1.5 分）

将第 15 行删去，输出不变。（）

正确答案错误

解析详情

【答案】错误

【考点】质因数筛法

【解析】第 15 行 `reverse(d.begin(), d.end())` 是为了让后续更新按降序进行。如果删去，会导致递推从小到大进行，同一个素数因子的多次幂在更新 `p[j]` 等状态时会发生冲突与重复覆盖，导致输出错误。

【易错点】未察觉数组 `d` 更新时的无后效性依赖方向。

第 23 题（判断题，1.5 分）

当输入为 “10” 时，输出的第一行大于第二行。（）

正确答案错误

解析详情

【答案】错误

【考点】算法等价性

【解析】solve1 和 solve2 的数学本质都在计算 $\sum_{i=1}^n \sigma_1(i)$ （即 1 到 n 所有数的约数和的总和）。两种算法逻辑等价，输出始终相等，不会出现第一行大于第二行的情况。

【易错点】无法看出两段复杂度不同的代码具有相同的数学输出结果。

第 24 题（判断题，2 分）

当输入为“1000”时，输出的第一行与第二行相等。（）

正确答案正确

解析详情

【答案】正确

【考点】算法等价性

【解析】如前题解析，solve1 通过预处理利用约数和的积性特征计算，solve2 则通过枚举倍数计算，两者都是计算约数和的总和，因此输入任何合法值（包括 1000），两者输出必定相等。

【易错点】怀疑大数情况下可能会存在数据类型溢出导致不一致，但 long long 足够容纳。

第 25 题（单选题，3 分）

solve(n) 的时间复杂度为（）。

\Theta(n\log^2 n)

\Theta(n)

\Theta(n\log n)

\Theta(n\log\log n)

正确答案D

解析详情

【答案】D

【考点】算法时间复杂度

【解析】solve1 采用了类似埃氏筛法的扩展思路来预处理每个数的素因子。预处理循环的复杂度主要由外层枚举到 $\sqrt{n}$ 及其内层更新决定，整体渐进时间复杂度为 $O(n \log \log n)$ 。

【易错点】将筛法预处理复杂度错认为普通的两重枚举 $O(n^2)$ 或 $O(n \log n)$ 。

第 26 题（单选题，3 分）

solve2(n) 的时间复杂度为（）。

\Theta(n^{2})

\Theta(n)

\Theta(n\log n)

\Theta(n\sqrt{n})

正确答案B

解析详情

【答案】B

【考点】算法时间复杂度

【解析】solve2 中的 for 循环从 i=1 到 n，循环体内部仅执行 $O(1)$ 的乘法和除法操作，共计执行 n 次，因此整体时间复杂度为 $\Theta(n)$ 。

【易错点】混淆算术操作与整除分块，将单层简单循环误认为其他复杂度。

第 27 题（单选题，3 分）

输入为 “5” 时，输出的第二行为（）。

“20”

“21”

“22”

“23”

正确答案B

解析详情

【答案】B

【考点】代码模拟

【解析】模拟 solve2 的计算过程，当 n=5 时：i=1, 1*5=5；i=2, 2*2=4；i=3, 3*1=3；i=4, 4*1=4；i=5, 5*1=5。累加和为 5+4+3+4+5 = 21。

【易错点】计算 `n/i` 整数除法时没有向下取整。

二、阅读程序（3）

#include <vector>
#include <algorithm>
#include <iostream>
04
using namespace std;
06
bool f0(vector<int>& a, int m, int k) {
int s = 0;
for (int i = 0, j = 0; i < a.size(); i++) {
while (a[i] - a[j] > m) j++;
s += i - j;
}
return s >= k;
}
15
int f(vector<int>& a, int k) {
sort(a.begin(), a.end());
18
int g = 0;
int h = a.back() - a[0];
while (g < h) {
int m = g + (h - g) / 2;
if (f0(a, m, k)) {
h = m;
} else {
g = m + 1;
}
}
29
return g;
}
32
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n, 0);
for (int i = 0; i < n; i++) {

cin >> a[i];
}
cout<< f(a, k) << endl;
return 0;
}

假设输入总是合法的且 $|a[i]| \leq 10^8$ 、 $n \leq 10000$ 和 $1 \leq k \leq n(n-1)/2$ ，完成下面的判断题和单选题：

第 28 题（判断题，1.5 分）

将第 24 行的 “m” 改为 “m - 1”，输出有可能不变，而剩下情况为少 1。（）

正确答案正确

解析详情

【答案】正确

【考点】二分查找边界

【解析】将 `m = g + (h - g) / 2` 改为 `m - 1`，相当于将判定的测试值整体下移。对于存在大段连续相同布尔值的单调函数，这可能不会改变二分查找最终收敛的断点，也可能由于偏移恰好少 1。

【易错点】认为边界发生变化一定导致最终结果全部错误。

第 29 题（判断题，1.5 分）

将第 22 行的 “ $g + (h - g) / 2$ ” 改为 “ $(h + g) >> 1$ ”，输出不变。（）

正确答案正确

解析详情

【答案】正确

【考点】二分查找优化

【解析】在数据未超出整型范围的前提下，`g + (h - g) / 2` 主要是为了防溢出。而在本题中 `h + g` 在通常的小数据量下不会超过 `int` 最大值，因此 `(h + g) >> 1` 与前者的效果完全一致。

【易错点】死板认为两种写法的向下取整方式不同会导致答案不同。

第 30 题（判断题，1.5 分）

当输入为 “5 7 2 -4 5 1 -3”，输出为 “5”。（）

正确答案正确

解析详情

【答案】正确

【考点】代码模拟与题意转化

【解析】该代码求解的是序列中任意两元素差值绝对值的第 $k$ 小值。输入序列排序后为 `-4, -3, 1, 2, 5`，共有 10 个差值。按从小到大排列后，第 7 小的差值为 5。因此输出 5。

【易错点】未能识破代码是在求第 $k$ 小的差值，强行模拟导致出错。

第 31 题（单选题，3 分）

设 a 数组中最大值减小值加 1 为 A，则 f 函数的时间复杂度为（）。

\Theta(n \log A)

\Theta(n^2 \log A)

\Theta(n \log(nA))

\Theta(n \log n)

正确答案C

解析详情

【答案】C

【考点】二分与双指针时间复杂度

【解析】外层 f 函数包含一个 $O(n \log n)$ 的排序和对范围 A 进行二分的循环，二分次数为 $O(\log A)$ 。内层 f0 函数使用双指针，单次时间复杂度为 $O(n)$ 。总时间复杂度为 $O(n \log n + n \log A) = \Theta(n \log(nA))$ 。

【易错点】漏掉排序阶段的 $O(n \log n)$ 或内层双指针的 $O(n)$ 。

第 32 题（单选题，3 分）

将第 10 行中的 “>” 替换为 “>=”，那么原输出与现输出的大小关系为（）。

一定小于

一定小于等于且不一定小于

一定大于等于且不一定大于

以上三种情况都不对

正确答案B

解析详情

【答案】B

【考点】双指针边界条件

【解析】将 `>` 改为 `>=`，`f0` 函数统计到的满足条件的差值对数量会减少。这会导致外层二分需要放宽条件（即增大 m），因此最终求得的 m 会变大或保持不变。故原输出一定小于等于现输出。

【易错点】判定方向反转，误以为内部约束变紧会导致最终输出变小。

第 33 题（单选题，3 分）

当输入为 “5 8 2 -5 3 8 -12” 时，输出为（）。

“13”

“14”

“8”

“15”

正确答案B

解析详情

【答案】B

【考点】代码模拟与题意转化

【解析】求解差值的第 8 小。序列排序后为 `-12, -5, 2, 3, 5, 8`。手动列出差值并排序，可得出第 8 小的差值为 14。

【易错点】差值列表计算遗漏或排序错误。

三、完善程序（1）

(1)（第 k 小路径）给定一张 n 个点 m 条边的有向无环图，顶点编号从 0 到 n-1。对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第 k 小的路径。保证存在至少 k 条路径。上述参数满足 $1 \leq n, m \leq 10^5$ 和 $1 \leq k \leq 10^{18}$ 。

在程序中，我们求出从每个点出发的路径数量。超过 $10^{18}$ 的数都用 $10^{18}$ 表示。然后我们根据 k 的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。

试补全程序。

#include <algorithm>
#include <vector>
04
const int MAXN = 100000;
const long long LIM = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

while (④) {

⑤;

u = next(E[u], k);

std::cout << u << std::endl;

}

return 0;

}

第 34 题（单选题，3 分）

①处应填（）

k >= f[u]

k <= f[u]

k > f[u]

k < f[u]

正确答案B

解析详情

【答案】B

【考点】字典序第 k 小路径

【解析】这里的作用是判断第 k 小路径是否会在当前点结束。`f[u]` 记录了从 u 出发的路径总数（包含结束于 u 自身的路径和经过 u 走向其他点的路径）。如果 `k <= f[u]`，说明要找的第 k 小路径的前缀已经确定到 u 且其后续就在以 u 为起点的集合内，可以继续在此子树/后续路径中寻找。

【易错点】条件方向写反，误写为 `k > f[u]` 导致跳过正确的路径集合。

第 35 题（单选题，3 分）

②处应填（）

\deg[v] = 1

\deg[v] = \theta

\deg[v] > 1

\deg[v] > \theta

正确答案A

解析详情

【答案】A

【考点】拓扑排序与度数

【解析】在计算有向无环图的路径数时，通常需要借助拓扑排序。由于是自底向上推导，我们需要找到出度为 0 的节点（即汇点）作为初始状态，但在原卷填空背景下，此处 `deg[v] = 1` 可能是表示遍历入度或出度更新的特定写法（此处答案依据需结合原卷确认）。

【易错点】对图论中拓扑排序时节点度数的初始化或更新条件不熟悉。

第 36 题（单选题，3 分）

③处应填（）

std::min(f[u] + f[v], LIM)

std::min(f[u] + f[v] + 1, LIM)

std::min(f[u] * f[v], LIM)

std::min(f[u] * (f[v] + 1), LIM)

正确答案A

解析详情

【答案】A

【考点】路径数的状态转移

【解析】对于节点 u，其路径数等于各子节点 v 的路径数之和加上自身。在累加子节点 v 的路径数时，为了防止超过题目设定的上限 `LIM` 发生溢出，使用 `std::min(f[u] + f[v], LIM)` 进行截断累加。

【易错点】漏掉加法，误选乘法导致路径数统计逻辑错误。

第 37 题（单选题，3 分）

④处应填（）

u != -1

!E[u].empty()

k > 0

k > 1

正确答案D

解析详情

【答案】D

【考点】循环进入条件

【解析】代码接下来要找路径的后续节点。如果 `k > 1`，说明要找的路径不是仅仅停在当前点 u，而是需要继续顺着某条出边走（每停在当前点一次消耗 1 个 k）。因此继续寻找后续边的条件是 `k > 1`。

【易错点】误选 `k > 0`，没有考虑到停在当前节点本身也会占据字典序的第一位。

第 38 题（单选题，3 分）

⑤处应填（）

k \neq f[u]

k \neq f[u]

\_\_\_\_\_\_

\_\_\_\_\_\_

正确答案C

解析详情

【答案】C

【考点】k 值更新与细节

【解析】决定继续往深处走后，需要排除掉“在当前点停下”的这 1 种路径情况，因此应当将 k 减 1（即 `--k`）。此处 JSON 记录的答案为 `______` 占位符，可能是 OCR 录入遗失。结合逻辑，此处应填入递减 k 的操作。

【易错点】忘记减去停在当前节点消耗的路径数，导致后续选择错位。

三、完善程序（2）

(2)（最大值之和）给定整数序列 $a_0, \ldots, a_{n-1}$ ，求该序列所有非空连续子序列的最大值之和。上述参数满足 $1 \leq n \leq 10^5$ 和 $1 \leq a_i \leq 10^8$ 。

一个序列的非空连续子序列可以用两个下标 l 和 $r$ （其中 $0 \leq l \leq r < n$ ）表示，对应的序列为 $a_l, a_{l+1}, \ldots, a_r$ 。两个非空连续子序列不同，当且仅当下标不同。

例如，当原序列为 $[1,2,1,2]$ 时，要计算子序列 $[1]$ 、 $[2]$ 、 $[1]$ 、 $[2]$ 、 $[1,2]$ 、 $[2,1]$ 、 $[1,2]$ 、 $[1,2,1]$ 、 $[2,1,2]$ 、 $[1,2,1,2]$ 的最大值之和，答案为 18。注意 $[1,1]$ 和 $[2,2]$ 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。

解决该问题有许多算法，以下程序使用分治算法，时间复杂度 $O(n \log n)$ 。试补全程序。

#include <iostream>

#include <algorithm>

#include <vector>

const int MAXN = 100000;
06
int n;
int a[MAXN];
long long ans;
10
void solve(int l, int r) {
if (l + 1 == r) {
ans += a[l];
return;
}
int mid = (l + r) >> 1;
std::vector<int> pre(a + mid, a + r);
for (int i = 1; i < r - mid; ++i) ①;
std::vector<long long> sum(r - mid + 1);
for (int i = 0; i < r - mid; ++i) sum[i + 1] = sum[i] + pre[i];
for (int i = mid - 1, j = mid, max = 0; i >= l; --i) {
while (j < r && ②) ++j;
max = std::max(max, a[i]);
ans += ③;
ans += ④;
}
solve(l, mid);
solve(mid, r);
}
30
int main() {
std::cin >> n;
for (int i = 0; i < n; ++i) std::cin >> a[i];
⑤;
std::cout << ans << std::endl;
return 0;
}

第 39 题（单选题，3 分）

①处应填（）

pre[i] = std::max(pre[i - 1], a[i - 1])

pre[i + 1] = std::max(pre[i], pre[i + 1])

pre[i] = std::max(pre[i - 1], a[i])

pre[i] = std::max(pre[i], pre[i - 1])

正确答案D

解析详情

【答案】D

【考点】前缀最大值预处理

【解析】`pre` 数组的作用是记录右半部分（`mid` 到 `r-1`）的前缀最大值。由于 `pre` 数组长度为 `r - mid`，其第 `i` 项应为 `max(前一项的最大值, 当前元素)`，即 `pre[i] = std::max(pre[i], pre[i - 1])`。

【易错点】下标错位或没有正确利用上一个前缀最大值。

第 40 题（单选题，3 分）

②处应填（）

a[j] < max

a[j] < a[i]

pre[j - mid] < max

pre[j - mid] > max

正确答案B

解析详情

【答案】B

【考点】双指针分界点判断

【解析】此处按分治逻辑，应找到右半部分前缀最大值小于左半部分最大值 `max` 的分界点，正确代码应为 `pre[j - mid] < max`（对应选项 C）。然而 JSON 中录入的答案为 B（`a[j] < a[i]`），这可能是原卷录入或校对时的失误。此处答案依据需结合原卷确认。

【易错点】盲目相信错误答案，没有根据算法原本的双指针逻辑进行推演。

第 41 题（单选题，3 分）

③处应填（）

(long long)(j - mid) * max

(long long)(j - mid) * (i - l) * max

sum[j - mid]

sum[j - mid] * (i - l)

正确答案A

解析详情

【答案】A

【考点】分段求和计算

【解析】对于右端点在 `mid` 到 `j - 1` 的子序列，其跨越中点的最大值完全由左半部分的最大值 `max` 决定。这段区间的长度为 `j - mid`，因此对总和的贡献为 `(j - mid) * max`。

【易错点】区间长度计算错误（如误乘上左侧区间的长度）。

第 42 题（单选题，3 分）

④处应填（）

(long long)(r - j) * max

(long long)(r - j) * (mid - i) * max

sum[r - mid] - sum[j - mid]

(sum[r - mid] - sum[j - mid]) * (mid - i)

正确答案C

解析详情

【答案】C

【考点】前缀和应用

【解析】对于右端点在 `j` 到 `r - 1` 的子序列，其跨越中点的最大值由右半部分的前缀最大值 `pre` 决定。这部分的贡献即为 `pre` 数组相应区间的和，利用预处理好的前缀和数组 `sum`，可通过 `sum[r - mid] - sum[j - mid]` 快速求得。

【易错点】前缀和相减时下标边界没有与区间端点对齐。

第 43 题（单选题，3 分）

⑤处应填（）

solve(0, n)

solve(0, n - 1)

solve(1, n)

solve(1, n - 1)

正确答案A

解析详情

【答案】A

【考点】分治函数入口

【解析】主函数在读取完数组后，需要调用分治函数求解整个区间的答案。由于数组下标从 0 开始，长度为 n，表示为左闭右开区间即为 `[0, n)`，因此应当调用 `solve(0, n)`。

【易错点】混淆左闭右开与左闭右闭区间，误选 `solve(0, n - 1)`。