CSP-S 2023 · 提高级第一轮真题

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

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

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

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

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

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

最长公共子序列长度常常用来衡量两个序列的相似度。给定两个序列 $X=\{x_1,x_2,x_3,\ldots,x_m\}$ 和 $Y=\{y_1,y_2,y_3,\ldots,y_n\}$，最长公共子序列（LCS）问题的目标是找到一个最长的新序列 $Z=\{z_1,z_2,z_3,\ldots,z_k\}$，使得序列 $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$ 元；如果第二次掷出 $4$ 点，则最终收益为 $6$ 元。假设骰子掷出任意一点的概率均为 $\frac{1}{6}$，玩家连续掷两次骰子后，所有可能情形下收益的平均值是多少？（ ）

假设有以下 C++ 代码：

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

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

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

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

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

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

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

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

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

01double quick_power(double x, unsigned n) {
02    if (n == 0) return 1;
03    if (n == 1) return x;
04    return quick_power(x, n / 2)
05        * quick_power(x, n / 2)
06        * ((n & 1) ? x : 1);
07}

1  #include <iostream>
2  using namespace std;
3 
4  unsigned short f(unsigned short x) {
5      x ^= x << 6;
6      x ^= x >> 8;
7      return x;
8  }
9 
10  int main() {
11      unsigned short x;
12      cin >> x;
13      unsigned short y = f(x);
14      cout << y <<endl;
15      return 0;
16  }

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

1  #include <iostream>
2  #include <cmath>
3  #include <vector>
4  #include <algorithm>
5  using namespace std;
6 
7  long long solve1(int n) {
8      vector<bool> p(n+1, true);
9      vector<long long> f(n+1, 0), g(n+1, 0);
10      f[1] = 1;
11      for (int i = 2; i * i <= n; i++) {
12          if (p[i]) {
13              vector<int> d;
14              for (int k = i; k <= n; k *= i) d.push_back(k);
15              reverse(d.begin(), d.end());
16              for (int k : d) {
17                  for (int j = k; j <= n; j += k) {
18                      if (p[j]) {
19                          p[j] = false;
20                          f[j] = i;
21                          g[j] = k;
22                      }
23                  }
24              }
25          }
26      }
27      for (int i = sqrt(n) + 1; i <= n; i++) {
28          if (p[i]) {
29              f[i] = i;
30              g[i] = i;
31          }
32      }
33      long long sum = 1;
34      for (int i = 2; i <= n; i++) {
35          f[i] = f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);
36          sum += f[i];
37      }
38      return sum;
39  }
40 
41  long long solve2(int n) {
42      long long sum = 0;
43      for (int i = 1; i <= n; i++) {
44          sum += i * (n / i);
45      }
46      return sum;
47  }
48 
49  int main() {
50      int n;
51      cin >> n;
52      cout << solve1(n) << endl;
53      cout << solve2(n) << endl;
54      return 0;
55  }

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

1  #include <vector>
2  #include <algorithm>
3  #include <iostream>
4 
5  using namespace std;
6 
7  bool f0(vector<int>& a, int m, int k) {
8      int s = 0;
9      for (int i = 0, j = 0; i < a.size(); i++) {
10          while (a[i] - a[j] > m) j++;
11          s += i - j;
12      }
13      return s >= k;
14  }
15 
16  int f(vector<int>& a, int k) {
17      sort(a.begin(), a.end());
18 
19      int g = 0;
20      int h = a.back() - a[0];
21      while (g < h) {
22          int m = g + (h - g) / 2;
23          if (f0(a, m, k)) {
24              h = m;
25          } else {
26              g = m + 1;
27          }
28      }
29 
30      return g;
31  }
32 
33  int main() {
34      int n, k;
35      cin >> n >> k;
36      vector<int> a(n, 0);
37      for(int i = 0; i < n; i++) {
38          cin >> a[i];
39      }
40      cout<< f(a, k) << endl;
41      return 0;
42  }

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

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

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

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

试补全程序。

1  #include <iostream>
2  #include <algorithm>
3  #include <vector>
4 
5  const int MAXN = 100000;
6  const long long LIM = 1000000000000000000ll;
7 
8  int n, m, deg[MAXN];
9  std::vector<int> E[MAXN];
10  long long k, f[MAXN];
11 
12  int next(std::vector<int> cand, long long &k) {
13      std::sort(cand.begin(), cand.end());
14      for (int u : cand) {
15          if (①) return u;
16          k -= f[u];
17      }
18      return -1;
19  }
20 
21  int main() {
22      std::cin >> n >> m >> k;
23      for (int i = 0; i < m; ++i) {
24          int u, v;
25          std::cin >> u >> v; // 一条从 u 到 v 的边
26          E[u].push_back(v);
27          ++deg[v];
28      }
29      std::vector<int> Q;
30      for (int i = 0; i < n; ++i)
31      if (!deg[i]) Q.push_back(i);
32      for (int i = 0; i < n; ++i) {
33          int u = Q[i];
34          for (int v : E[u]) {
35              if (②) Q.push_back(v);
36              --deg[v];
37          }
38      }
39      std::reverse(Q.begin(), Q.end());
40      for (int u : Q) {
41          f[u] = 1;
42          for (int v : E[u]) f[u] = ③;
43      }
44      int u = next(Q, k);
45      std::cout << u << std::endl;
46      while (④) {
47          ⑤;
48          u = next(E[u], k);
49          std::cout << u << std::endl;
50      }
51      return 0;
52  }

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

一个序列的非空连续子序列可以用两个下标 $l$ 和 $r$（其中 $0\le l\le 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)$。试补全程序。

1  #include <iostream>
2  #include <algorithm>
3  #include <vector>
4 
5  const int MAXN = 100000;
6 
7  int n;
8  int a[MAXN];
9  long long ans;
10 
11  void solve(int l, int r) {
12      if (l + 1 == r) {
13          ans += a[l];
14          return;
15      }
16      int mid = (l + r) >> 1;
17      std::vector<int> pre(a + mid, a + r);
18      for (int i = 1; i < r - mid; ++i) ①;
19      std::vector<long long> sum(r - mid + 1);
20      for (int i = 0; i < r - mid; ++i) sum[i + 1] = sum[i] + pre[i];
21      for (int i = mid - 1, j = mid, max = 0; i >= l; --i) {
22          while (j < r && ②) ++j;
23          max = std::max(max, a[i]);
24          ans += ③;
25          ans += ④;
26      }
27      solve(l, mid);
28      solve(mid, r);
29  }
30 
31  int main() {
32      std::cin >> n;
33      for (int i = 0; i < n; ++i) std::cin >> a[i];
34      ⑤;
35      std::cout << ans << std::endl;
36      return 0;
37  }