单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）

1. 在Linux系统终端中，杀死名为test的进程的命令是（ ）。 {{ select(1) }}

• ps test
• kill test
• stop test
• killall test

2. 机房的IP地址为192.168.10.124，若想将其划分为4个子网，需要借的主机位数和每个子网的有效IP个数分别为（ ）。 {{ select(2) }}

• 1；126
• 1；127
• 2；64
• 2；62

3. 下列语句中，可以用于清空stack<int> stk的是（ ）。 {{ select(3) }}

• stk.clear();
• while (stk.empty()) stk.pop();
• while (stk.size()) stk.pop();
• clear(stk);

4. 从0-9中选择3个数构成不含前导0且能被3整除的数的方案数为（ ）。 {{ select(4) }}

• 192
• 256
• 48
• 228

5. 在一张无权图中使用广度优先搜索求从1号结点到其他所有结点的最短路径，下列说法中错误的是（ ）。 {{ select(5) }}

• 某一时刻，队列中某两个结点到结点1的距离的差为0
• 某一时刻，队列中某两个结点到结点1的距离的差为1
• 某一时刻，队列中某两个结点到结点1的距离的差为2
• 某一时刻，队列中任意两个结点到结点1的距离差为0

6. 关于图算法BFS、Dijkstra和Bellman-Ford，求解边权均为-1的图的最长路径可以使用（ ）种算法，求解边权均为1的图的最长路径可以使用（ ）种算法，求解边权均小于0的图的最长路径可以使用（ ）种算法。（上述3个问题中若有不存在解的情况，所选算法需要判断不存在解的情况，只考虑正确性而不考虑效率。） {{ select(6) }}

• 3；1；3
• 1；3；1
• 1；2；3
• 3；2；1

7. 在序列分块类问题中，对长度为n的序列，若取块长B，零散块的修改复杂度为$O(B)$，查询复杂度为$O(log^2 n)$，整块的修改杂度为$O(1)$，查询复杂度为$O(\frac{n}{B} log^2 n)$，则m次修改/查询的最坏复杂度最优为（ ）。 {{ select(7) }}

• $O\left(m \sqrt{n log^2 n}\right)$
• $O(m \sqrt{n} log n)$
• $O(m \sqrt{n log n})$
• $O(m \sqrt{n})$

8. 在C++程序中执行如下代码片段后，t的值为（ ）。

int a=1, b=1, c=4, d=5, e=1;
bool f = true; 
auto t = ((a > b ^ c) & f) < d ^ e;

{{ select(8) }}

• true
• false
• 0
• 1

9. 在一口无限深的井中，蜗牛处于井口下方5个单位长度处，每天白天以$\frac{1}{2}$的概率向上爬3个单位长度，晚上下滑1个单位长度，则蜗牛爬出井口（向上爬大于等于5个单位即为爬出井口）的期望天数为（ ）。 {{ select(9) }}

• $\frac{8}{3}$
• $\frac{12}{5}$
• 10
• 5

10. 使用二进制分组优化多重背包问题，数量为10的物品会被拆分为（ ）件物品。 {{ select(10) }}

• 1
• 2
• 3
• 4

11. 有一个数列定义如下：$a_0=1$，$a_1=1$，$a_n=(a_{n-1}+a_{n-2}) \bmod 10 (n>1)$，则$a_{1024}$和$a_{2048}$分别等于（ ）。 {{ select(11) }}

• 3；1
• 5；4
• 8；5
• 1；1

12. 下列代码片段中，有（ ）种方法可以判断状态s的第x个二进制位的情况（0/1）（x从0开始编号，编号从低位到高位增大）。
    • (1) (bool) (s >> x & 1)
    • (2) (bool) (s << x & 1)
    • (3) (~s >> x | ~1) == s
    • (4) (~s | ~1 << x) == s {{ select(12) }}

• 1
• 2
• 3
• 4

13. 下图中点双连通分量和边双连通分量分别有（ ）个。 {{ select(13) }}

• 1；1
• 2；3
• 3；2
• 2；2

14. 下图共有（ ）种不同的拓扑序。 {{ select(14) }}

• 35
• 21
• 24
• 76

15. 由3个中括号和3个小括号组成的本质不同的合法括号序列数为（ ），其中，一对匹配的小括号之间不应有中括号。 {{ select(15) }}

• 770
• 710
• 192
• 560

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填x；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 2e5 + 10;
04 
05 long long a[N];
06 
07 int main() {
08     int n, m;
09     scanf("%d%d", &n, &m); // 1<=n,m<=2e5
10     for (int i = 1; i <= n; ++i) scanf("%lld", a + i); // 1<=a[i]<=1e9
11     while (m--) {
12         int x;
13         scanf("%d", &x); // 1<=x<=1e9
14         int lst = 1;
15         for (int i = 1; i <= n; ++i) {
16             if (a[i] >= lst) {
17                 if (x <= a[i]) {
18                     a[i] += x - lst + 1;
19                     break;
20                 } else {
21                     int dis = a[i] - lst + 1;
22                     lst = a[i] + 1;
23                     a[i] += dis;
24                 }
25             }
26         }
27     }
28 
29     for (int i = 1; i <= n; ++i) printf("%lld\n", a[i]);
30     return 0;
31 }

假定输入数据范围：$1 ≤ n, m ≤ 2 × 10^5$，$a_i, x \in [1, 10^9]$。

■ 判断题 16. 将第5行中的long long改为int，不影响程序结果。（ ） {{ select(16) }}

• 正确
• 错误

17. （2分）该算法的时间复杂度为$O(nm)$。（ ） {{ select(17) }}

• 正确
• 错误

18. 当输入为3 2 3 25 6 1时，输出为7 2 7。（ ） {{ select(18) }}

• 正确
• 错误

19. 当输入为3 2 3 2 16 6时，输出为9 2 1。（ ） {{ select(19) }}

• 正确
• 错误

■ 选择题 20. 当输入为4 5 10 20 30 40 20 10 30 25 5时，输出为（ ）。 {{ select(20) }}

• 10 20 30 40
• 100 20 30 40
• 30 30 60 100
• 90 30 30 40

21. 当输入为3 4 10 20 10 10 20 10 10时，输出为（ ）。 {{ select(21) }}

• 10 20 60
• 10 70 10
• 60 20 10
• 10 20 10

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 int cow[300010];
05 int buf[300010], tot;
06 int buf2[300010], tot2;
07 
08 signed main() {
09     int n;
10     scanf("%d", &n);
11     for (int i = 1; i <= n; ++i) {
12         char ch;
13         for (ch = getchar(); ch != '0' && ch != '1'; ch = getchar());
14         cow[i] = ch - '0';
15     }
16     int tim = n << 1, start = 0;
17     for (int i = 1; i <= n + 1; ++i) {
18         if (cow[i] == 1 && cow[i - 1] == 0) start = i;
19         else if (cow[i] == 0 && cow[i - 1] == 1) {
20             if (start == 1 || i == n + 1) {
21                 buf2[++tot2] = i - start;
22                 tim = min(tim, (i - start - 1) << 1 | 1);
23             } else {
24                 buf[++tot] = i - start;
25                 tim = min(tim, ((i - start - 1) >> 1) << 1 | 1);
26             }
27         }
28     }
29     long long ans = 0;
30     for (int i = 1; i <= tot; ++i) ans += (buf[i] + tim - 1) / tim;
31     for (int i = 1; i <= tot2; ++i) ans += (buf2[i] + tim - 1) / tim;
32     cout << ans << endl;
33     return 0;
34 }

输入为一个整数n以及一个长度为n的01字符串。保证$1 ≤ n ≤ 3 × 10^5$。

■ 判断题 22. 在第17~28行的循环结束后，始终有tot + tot2 == n为true。（ ） {{ select(22) }}

• 正确
• 错误

23. 若输入为5 11111，则输出为1。（ ） {{ select(23) }}

• 正确
• 错误

24. 若输入为6 011101，则输出为4。（ ） {{ select(24) }}

• 正确
• 错误

■ 选择题 25. 若输入为9 101001101，则tot2 =（ ）。 {{ select(25) }}

• 0
• 1
• 2
• 3

26. 若输入为15 110011100101101，则buf[1...tot]的内容为（ ）。 {{ select(26) }}

• 3 1 1
• 3 1 2
• 1 1 2 1
• 1 1 2 2

27. 若输入为13 0010110111011，则tot + tot2 =（ ）。 {{ select(27) }}

• 1
• 2
• 3
• 4

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 5e5 + 10;
04 int pls[N], cnt[N], dist[N], dist2[N];
05 
06 signed main() {
07     ios::sync_with_stdio(false);
08     cin.tie(NULL);
09     int n, k;
10     cin >> n >> k; // 1<=k<=n<=5e5
11     int x;
12     for (int i = 1; i <= k; ++i) {
13         cin >> x;
14         pls[x] = i;
15         ++cnt[x];
16     }
17     int ans = 0;
18     for (int i = 1; i <= k; ++i) {
19         cin >> x;
20         ++cnt[x];
21         if (pls[x]) {
22             int d;
23             if (pls[x] < i) {
24                 d = k + pls[x] - i;
25             } else {
26                 d = pls[x] - i;
27             }
28             ans = max(ans, ++dist[d]);
29             if (pls[x] < k + 1 - i) {
30                 d = k + pls[x] - (k + 1 - i);
31             } else {
32                 d = pls[x] - (k + 1 - i);
33             }
34             ans = max(ans, ++dist2[d]);
35         }
36     }
37     for (int i = 1; i <= n; ++i) {
38         if (!cnt[i]) {
39             ++ans;
40         }
41     }
42     cout << ans << endl;
43     return 0;
44 }

假定输入数据中$1 ≤ k ≤ n ≤ 5 × 10^5$，后跟的两个长度为k的序列分别是$\{1, 2, \cdots, n\}$的一个大小为k的子集的一个排列。

■ 判断题 28. 若输入为6 3 1 2 3 2 3 1，则输出为6。（ ） {{ select(28) }}

• 正确
• 错误

29. 若输入为6 3 1 2 3 4 5 6，则输出为1。（ ） {{ select(29) }}

• 正确
• 错误

30. 若输入为5 3 1 2 3 3 2 1，则dist[0] = 1，dist2[0] = 2。（ ） {{ select(30) }}

• 正确
• 错误

■ 选择题

31. **若输入为6 4 1 2 3 4 4 3 1 5，则第23行执行（ ）次。 {{ select(31) }}

• 1
• 2
• 3
• 4

32. 若输入为5 4 1 2 3 4 4 3 1 5，则输出为（ ）。 {{ select(32) }}

• 1
• 2
• 3
• 4

33. 若输入为5 3 1 2 3 2 3 4，则执行完第17~35行的for循环后dist2[2] =（ ）。 {{ select(33) }}

• 0
• 1
• 2
• 3

完善程序（单选题，每小题3分，共计30分）

(1) （击靶）在坐标轴上$[-C, C]$区间内有T个靶子（不重合），射手刚开始处在坐标原点，进行c次操作。

• L：从坐标x处移动到坐标$x-1$处。
• R：从坐标x处移动到坐标$x+1$处。
• F：进行一次射击，若当前坐标处存在未被击倒的靶子，则击倒该靶子。

求对原操作序列修改一次后，最多能击倒多少靶子？

输入格式： 第1行是两个正整数T和$C$。第2行是T个正整数，表示靶子的坐标。第3行是一个长度为c的字符串，字典为$\{L, R, F\}$，表示原操作序列。

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int N = 1e5 + 10, DELTA = 1e5 + 1;
05 int pls[N], mp[N << 1], Lft[N << 1], second[N << 1], LEFT[N << 1];
06 int nTar, nOp, curAns, ans;
07 char op[N];
08 
09 void work(int delta, char from, char to) {
10     memset(second, 0, sizeof(second));
11     memcpy(Lft, LEFT, sizeof(Lft));
12     for (①) {
13         if (②) {
14             if (from == 'F' && mp[pls[i] + DELTA] && Lft[pls[i] + DELTA] == i && second[pls[i] + DELTA] == 0)
15                 ans = max(ans, curAns - 1);
16             else if (to == 'F' && mp[pls[i] + DELTA] && Lft[pls[i] + DELTA] == 0)
17                 ans = max(ans, curAns + 1);
18             else
19                 ans = max(ans, curAns);
20         }
21         if (op[i] == 'F') {
22             if (mp[pls[i] + DELTA] && Lft[pls[i] + DELTA] == i)
23                 Lft[pls[i] + DELTA] = second[pls[i] + DELTA];
24             if (Lft[pls[i] + DELTA] == 0)
25                 --curAns;
26         }
27         pls[i] += delta;
28         if (mp[pls[i] + DELTA]) {
29             if (Lft[pls[i] + DELTA] == 0) {
30                 ③;
31                 Lft[pls[i] + DELTA] = i;
32             }
33             ④;
34             Lft[pls[i] + DELTA] = min(Lft[pls[i] + DELTA], i);
35         }
36         pls[i] -= delta;
37     }
38 }
39 
40 signed main() {
41     ios::sync_with_stdio(false);
42     cin.tie(NULL);
43     cin >> nTar >> nOp; // nTar表示靶子的个数，nOp表示操作序列的长度
44     int tar;
45     for (int i = 1; i <= nTar; ++i) {
46         cin >> tar; // 目标的位置
47         mp[tar + DELTA] = 1;
48     }
49     cin >> (op + 1); // 输入操作序列
50     int x = 0;
51     for (int i = 1; i <= nOp; ++i) {
52         pls[i] = x;
53         if (op[i] == 'L') --x;
54         else if (op[i] == 'R') ++x;
55         else if (mp[x + DELTA] && !Lft[x + DELTA]) {
56             ++ans;
57             Lft[x + DELTA] = i;
58         }
59     }
60     int tmp = ans;
61     memcpy(LEFT, Lft, sizeof(Lft));
62     curAns = tmp; work(2, "L", "R");
63     curAns = tmp; work(-2, "R", "L");
64     curAns = tmp; work(1, "L", "F");
65     curAns = tmp; work(⑤);
66     curAns = tmp; work(-1, "F", "L");
67     curAns = tmp; work(1, "F", "R");
68     cout << ans << endl;
69     return 0;
70 }

34. ①处应填（ ）。 {{ select(34) }}

• int i = 1; i <= nOp; ++i
• int i = nOp; i >= 1; --i
• int i = 1; i <= nTar; ++i
• int i = nTar; i >= 1; --i

35. ②处应填（ ）。 {{ select(35) }}

• op[i] == to
• op[i] == from
• op[i] == 'L'
• op[i] == 'R'

36. ③处应填（ ）。 {{ select(36) }}

• ++curAns
• --curAns
• ++ans
• --ans

37. ④处应填（ ）。 {{ select(37) }}

• LEFT[pls[i] + DELTA] = i
• ans = curAns
• second[pls[i] + DELTA] = i
• ++curAns

38. ⑤处应填（ ）。 {{ select(38) }}

• 1, 'R', 'F'
• 2, 'R', 'F'
• -1, 'R', 'L'
• -1, 'R', 'F'

(2) （字典序最小最长路径）给出一张有n个结点、m条边的带权无环有向图，边以$(a_i, b_i, l_i)$的形式给出，表示从$a_i$到$b_i$的一条有向边，边权为$l_i$。现在要求对于每个结点，输出以它为起点且经过最多条边的路径经过的边数以及边权之和。如果有多条经过边数最多的路径，则选择将路径边权按顺序排列，得到序列中字典序最小的一条。

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int N = 2e5 + 10;
05 vector<pair<int, int>> g[N];
06 int dp[N], nexE[N], nexT[N], rnk[N], id[N];
07 long long sum[N];
08 bool vis[N];
09 
10 void work(int cur) {
11     if (vis[cur]) return;
12     vis[cur] = true;
13     for (auto it : g[cur]) {
14         work(it.first);
15         dp[cur] = max(dp[cur], dp[it.first] + 1);
16     }
17     for (auto it : g[cur])
18         if (dp[it.first] + 1 == dp[cur] && (nexE[cur] == 0 || it.second < nexE[cur]))
19             ①;
20 }
21 
22 signed main() {
23     ios::sync_with_stdio(false);
24     cin.tie(NULL);
25     int n, m;
26     cin >> n >> m; // 输入结点数n和边数m
27     int u, v, w;
28     for (int i = 1; i <= m; ++i) {
29         cin >> u >> v >> w; // 从u到v的一条有向边，边权为w
30         g[u].push_back(make_pair(v, w));
31     }
32     for (int i = 1; i <= n; ++i)
33         if (②)
34             work(i);
35     for (int i = 1; i <= n; ++i)
36         id[i] = i;
37     sort(id + 1, id + n + 1, [&](int x, int y) { return ③; });
38     vector<int> vec;
39     for (int i = 1; i <= n; ++i) {
40         if (dp[id[i]] == 0) continue;
41         if (dp[id[i]] != dp[id[i - 1]] && !vec.empty()) {
42             sort(vec.begin(), vec.end(), [](int x, int y) { return nexE[x] < nexE[y] || (④ && rnk[nexT[x]] < rnk[nexT[y]]); });
43             int cnt = 0;
44             for (int x : vec) rnk[x] = ++cnt;
45             vec.clear();
46         }
47         vec.push_back(id[i]);
48         for (auto it : g[id[i]])
49             if (dp[it.first] + 1 == dp[id[i]] && (nexE[id[i]] == 0 || (it.second < nexE[id[i]] || (it.second == nexE[id[i]] && rnk[it.first] < rnk[nexT[id[i]]]))) {
50                 nexE[id[i]] = it.second;
51                 nexT[id[i]] = it.first;
52             }
53         sum[id[i]] = ⑤;
54     }
55     for (int i = 1; i <= n; ++i)
56         cout << dp[i] << ' ' << sum[i] << endl;
57     return 0;
58 }

39. ①处应填（ ）。 {{ select(39) }}

• nexE[cur] = it.second
• nexE[cur] = dp[it.first] + 1
• nexT[cur] = it.second
• nexT[cur] = it.first

40. ②处应填（ ）。 {{ select(40) }}

• dp[i]
• !vis[i]
• !rnk[i]
• nexT[i]

41. ③处应填（ ）。 {{ select(41) }}

• nexE[x] < nexE[y]
• nexT[x] < nexT[y]
• dp[x] < dp[y]
• id[x] < id[y]

42. ④处应填（ ）。 {{ select(42) }}

• rnk[x] == rnk[y]
• rnk[x] < rnk[y]
• nexE[x] > nexE[y]
• nexE[x] == nexE[y]

43. ⑤处应填（ ）。 {{ select(43) }}

• sum[id[i]] + nexE[id[i]]
• sum[nexT[id[i]]] + nexE[id[i]]
• sum[rnk[id[i]]] + nexE[id[i]]
• nexE[id[i]] + nexT[id[i]]

---