2023年 CSP-S 第一轮（提高级）

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

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

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

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

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

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

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

一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下: 玩家第一次掷出 $x$ 点，得到 $2x$ 元；第二次掷出 $y$ 点，当 $y=x$ 时玩家会失去之前得到的 $2x$ 元而当 $y\ne x$ 时玩家能保住第一次获得的$2x$ 元。上述 $x,y\in \{1,2,3,4,5,6\}$。例如: 玩家第一次掷出 $3$ 点得到 $6$ 元后，但第二次再次掷出 $3$ 点，会失去之前得到的 $6$ 元，玩家最终收益为 $0$ 元;如果玩家第一次掷出 $3$ 点、第二次掷出 $4$ 点，则最终收益是 $6$ 元。假设骰子挑出任意一点的概率均为 16\frac{1}{6}61​，玩家连续掷两次骰子后，所有可能情形下收益的平均值是多少?

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

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

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

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

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

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

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

[图片]

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

若 n=Σi=0k16i⋅xin = \Sigma^{k}_{i=0}16^i·{x_i}n=Σi=0k​16i⋅xi​，定义 f(n)=Σi=0kxi\mathrm{f}(n) = \Sigma^{k}_{i=0}x_if(n)=Σi=0k​xi​；其中 xi∈0,1,…,15x_i\in {0,1,\dots,15}xi​∈0,1,…,15。对于给定自然数 n0n_0n0​，存在序列 n0,n1,n2,…,nmn_0, n_1, n_2,\dots,n_mn0​,n1​,n2​,…,nm​，其中对于 $1\le i\le m$ 都有 ni=f(ni−1)n_i = \mathrm{f}(n_{i-1})ni​=f(ni−1​)，且 nm=nm−1n_m=n_{m-1}nm​=nm−1​，称 nmn_mnm​ 为 n0n_0n0​ 关于 $\mathrm{f}$ 的不动点。问在 10016100_{16}10016​ 至 1A016\mathrm{1A0}_{16}1A016​ 中，关于 $\mathrm{f}$ 的不动点为 $9$ 的自然数个数为（ ）。

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

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);
}

假设输入的 x 是不超过 $65535$ 的自然数，完成下面的判断题。

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

假设输入的 x 是不超过 $65535$ 的自然数，完成下面的判断题。

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

假设输入的 x 是不超过 $65535$ 的自然数，完成下面的判断题。

当输入为 65535 时，输出为 63。

假设输入的 x 是不超过 $65535$ 的自然数，完成下面的判断题。

当输入为 1 时，输出为 64。

假设输入的 x 是不超过 $65535$ 的自然数，完成下面的单选题。

当输入为 512 时，输出为（ ）

假设输入的 x 是不超过 $65535$ 的自然数，完成下面的单选题。

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

假设输入的 n 是不超过 $1000000$ 的自然数，完成下面的判断题。

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

假设输入的 n 是不超过 $1000000$ 的自然数，完成下面的判断题。

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

假设输入的 n 是不超过 $1000000$ 的自然数，完成下面的判断题。

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

假设输入的 n 是不超过 $1000000$ 的自然数，完成下面的单选题。

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

假设输入的 n 是不超过 $1000000$ 的自然数，完成下面的单选题。

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

假设输入的 n 是不超过 $1000000$ 的自然数，完成下面的单选题。

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

假设输入总是合法的且 ∣a[i]∣≤108,n≤10000|a[i]| \leq 10^8, n\leq 10000∣a[i]∣≤108,n≤10000 和 1≤k≤n(n−1)21\leq k \leq \frac{n(n-1)}{2}1≤k≤2n(n−1)​，完成下面的判断题。

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

假设输入总是合法的且 ∣a[i]∣≤108,n≤10000|a[i]| \leq 10^8, n\leq 10000∣a[i]∣≤108,n≤10000 和 1≤k≤n(n−1)21\leq k \leq \frac{n(n-1)}{2}1≤k≤2n(n−1)​，完成下面的判断题。

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

假设输入总是合法的且 ∣a[i]∣≤108,n≤10000|a[i]| \leq 10^8, n\leq 10000∣a[i]∣≤108,n≤10000 和 1≤k≤n(n−1)21\leq k \leq \frac{n(n-1)}{2}1≤k≤2n(n−1)​，完成下面的判断题。

当输入为 5 7 2 -4 5 1 -3，输出为 5。

假设输入总是合法的且 ∣a[i]∣≤108,n≤10000|a[i]| \leq 10^8, n\leq 10000∣a[i]∣≤108,n≤10000 和 1≤k≤n(n−1)21\leq k \leq \frac{n(n-1)}{2}1≤k≤2n(n−1)​，完成下面的单选题。

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

假设输入总是合法的且 ∣a[i]∣≤108,n≤10000|a[i]| \leq 10^8, n\leq 10000∣a[i]∣≤108,n≤10000 和 1≤k≤n(n−1)21\leq k \leq \frac{n(n-1)}{2}1≤k≤2n(n−1)​，完成下面的单选题。

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

假设输入总是合法的且 ∣a[i]∣≤108,n≤10000|a[i]| \leq 10^8, n\leq 10000∣a[i]∣≤108,n≤10000 和 1≤k≤n(n−1)21\leq k \leq \frac{n(n-1)}{2}1≤k≤2n(n−1)​，完成下面的单选题。

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

（第k小路径）给定一张 $n$ 个点 $m$ 条边的有向无环图，顶点编号从 $0$ 到 $n-1$。

对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的项点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第 $k$ 小的路径。保证存在至少 $k$ 条路径。上述参数满足 1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105 和1≤k≤10181\leq k\leq 10^{18}1≤k≤1018。

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

试补全程序。

① 处应该填 ( )

（第k小路径）给定一张 $n$ 个点 $m$ 条边的有向无环图，顶点编号从 $0$ 到 $n-1$。

对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的项点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第 $k$ 小的路径。保证存在至少 $k$ 条路径。上述参数满足 1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105 和1≤k≤10181\leq k\leq 10^{18}1≤k≤1018。

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

试补全程序。

② 处应该填 ( )

（第k小路径）给定一张 $n$ 个点 $m$ 条边的有向无环图，顶点编号从 $0$ 到 $n-1$。

对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的项点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第 $k$ 小的路径。保证存在至少 $k$ 条路径。上述参数满足 1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105 和1≤k≤10181\leq k\leq 10^{18}1≤k≤1018。

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

试补全程序。

③ 处应该填 ( )

（第k小路径）给定一张 $n$ 个点 $m$ 条边的有向无环图，顶点编号从 $0$ 到 $n-1$。

对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的项点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第 $k$ 小的路径。保证存在至少 $k$ 条路径。上述参数满足 1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105 和1≤k≤10181\leq k\leq 10^{18}1≤k≤1018。

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

试补全程序。

④ 处应该填 ( )

（第k小路径）给定一张 $n$ 个点 $m$ 条边的有向无环图，顶点编号从 $0$ 到 $n-1$。

对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的项点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第 $k$ 小的路径。保证存在至少 $k$ 条路径。上述参数满足 1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105 和1≤k≤10181\leq k\leq 10^{18}1≤k≤1018。

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

试补全程序。

⑤ 处应该填 ( )

（最大值之和）给定整数序列 a0,...,an−1a_0, ..., a_{n-1}a0​,...,an−1​ 求该序列所有非空连续子序列的最大值之和。上述参数满足 1<n≤1051 <n\leq 10^51<n≤105 和 1≤ai≤1081\leq a_i \leq 10^81≤ai​≤108。

一个序列的非空连续子序列可以用两个下标 $l$ 和 $r$ (其中 $0\le l\le r<n$) 表示，对应的序列为 al,al+1,...,ara_l, a_{l+1}, ..., a_ral​,al+1​,...,ar​。两个非空连续子序列不同，当且仅当下标不同。

例如，当原序列为 [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] 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。

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

试补全程序。

① 处应填（ ）

（最大值之和）给定整数序列 a0,...,an−1a_0, ..., a_{n-1}a0​,...,an−1​ 求该序列所有非空连续子序列的最大值之和。上述参数满足 1<n≤1051 <n\leq 10^51<n≤105 和 1≤ai≤1081\leq a_i \leq 10^81≤ai​≤108。

一个序列的非空连续子序列可以用两个下标 $l$ 和 $r$ (其中 $0\le l\le r<n$) 表示，对应的序列为 al,al+1,...,ara_l, a_{l+1}, ..., a_ral​,al+1​,...,ar​。两个非空连续子序列不同，当且仅当下标不同。

例如，当原序列为 [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] 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。

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

试补全程序。

② 处应填（ ）

（最大值之和）给定整数序列 a0,...,an−1a_0, ..., a_{n-1}a0​,...,an−1​ 求该序列所有非空连续子序列的最大值之

和。上述参数满足 1<n≤1051 <n\leq 10^51<n≤105 和 1≤ai≤1081\leq a_i \leq 10^81≤ai​≤108。

一个序列的非空连续子序列可以用两个下标 $l$ 和 $r$ (其中 $0\le l\le r<n$) 表示，对应的序列为 al,al+1,...,ara_l, a_{l+1}, ..., a_ral​,al+1​,...,ar​。两个非空连续子序列不同，当且仅当下标不同。

例如，当原序列为 [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] 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。

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

试补全程序。

③ 处应填（ ）

（最大值之和）给定整数序列 a0,...,an−1a_0, ..., a_{n-1}a0​,...,an−1​ 求该序列所有非空连续子序列的最大值之

和。上述参数满足 1<n≤1051 <n\leq 10^51<n≤105 和 1≤ai≤1081\leq a_i \leq 10^81≤ai​≤108。

一个序列的非空连续子序列可以用两个下标 $l$ 和 $r$ (其中 $0\le l\le r<n$) 表示，对应的序列为 al,al+1,...,ara_l, a_{l+1}, ..., a_ral​,al+1​,...,ar​。两个非空连续子序列不同，当且仅当下标不同。

例如，当原序列为 [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] 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。

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

试补全程序。

④ 处应填（ ）

（最大值之和）给定整数序列 a0,...,an−1a_0, ..., a_{n-1}a0​,...,an−1​ 求该序列所有非空连续子序列的最大值之

和。上述参数满足 1<n≤1051 <n\leq 10^51<n≤105 和 1≤ai≤1081\leq a_i \leq 10^81≤ai​≤108。

一个序列的非空连续子序列可以用两个下标 $l$ 和 $r$ (其中 $0\le l\le r<n$) 表示，对应的序列为 al,al+1,...,ara_l, a_{l+1}, ..., a_ral​,al+1​,...,ar​。两个非空连续子序列不同，当且仅当下标不同。

例如，当原序列为 [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] 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。

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

试补全程序。

⑤ 处应填（ ）