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

1. 以下哪个命令会开启编译器几乎所有常用的警告？（ ） {{ select(1) }}

• g++ -g -lmmain.cpp -omain
• g++ -g -Wall main.cpp -o main
• g++ -g -02 main.cpp -omain
• g++ -g -std=C++11 main.cpp -o main

2. 以下关于NOI Linux的文件操作描述错误的是（ ）。 {{ select(2) }}

• mkdir是新建一个文件
• pwd显示当前工作文件路径
• ls显示文件及文件夹
• more在终端中分页显示普通文本类型文件

3. 以下哪个不属于STL中算法模板库的操作函数？（ ） {{ select(3) }}

• reverse
• sort
• push_back
• lower_bound

4. 以下哪个说法是不正确的？（ ） {{ select(4) }}

• tuple中的每个值都必须是相同的类型
• pair定义在头文件utility中，用于将两个值组合在一起存储
• multiset是维护有序可重集合的容器
• set是维护有序不可重集合的容器

5. 对下图使用Floyd算法计算S点到其余各点的最短路径长度时，到B点的距离d[B]初始时赋为8，在算法的执行过程中不可能出现的值是（ ）。 {{ select(5) }}

• 4
• 5
• 6
• 7

6. 平面上有5个点A(5,3)，B(3,5)，C(2,1)，D(3,3)，E(5,1)。以这5个点作为完全图G的顶点，每两点之间的直线距离是图G中对应边的权值。图G的最小生成树中的所有边的权值和为（ ）。 {{ select(6) }}

• 8
• $7+\sqrt{5}$
• 9
• $6+\sqrt{5}$

7. 单源最短路的Dijkstra算法写的C++程序的运行时间复杂度是（ ）。 {{ select(7) }}

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

8. 对于一棵二叉树，独立集是指两两互不相邻的结点构成的集合。比如，图1有5个不同的独立集（1个双点集合、3个单点集合、1个空集），图2有14个不同的独立集。那么，图3有（ ）个不同的独立集。 {{ select(8) }}

• 1936
• 3600
• 5536
• 6300

9. 以下哪个说法是正确的？（ ） {{ select(9) }}

• 要判断图是否连通，只能用广度优先搜索算法来判别
• 高斯是图论的创始人之一，他解决了哥尼斯堡七桥问题
• 图灵的主要贡献是用图灵机破解了德军的Enigma密码
• 如果待查找的元素确定，只要哈希表的大小不小于查找元素的个数，就一定存在不会产生冲突的哈希函数

10. 下图中的8个结点通过13条无向边相连，每条无向边上都有两项信息：前面的字母表示这条边的安全性（字母S表示这条边是Safe边，字母D表示这条边是Danger边），后面的数字表示这条边的长度。从中找出7条边能连通这8个结点，且这7条边中恰好有2条Safe边（S边），记这7条边长度之和为path，则path的最小值为（ ）。

{{ select(10) }}

• 10
• 11
• 12
• 13

11. 以下哪个不是C++语言中面向对象模式的主要性质？（ ） {{ select(11) }}

• 封装性
• 继承性
• 单调性
• 多态性

12. 从1到2021的所有奇数中，至少要选出（ ）个数，才能确保其中必定存在两个数，它们的和是2022？ {{ select(12) }}

• 505
• 506
• 507
• 508

13. 如果一棵二叉树有2024个结点，树中的结点按层次和顺序依次编号（每层中从左到右编号），其中根结点为1，那么编号为1025的父结点为第（ ）层第（ ）个结点。 {{ select(13) }}

• 10 1
• 10 2
• 9 256
• 11 2

14. 4个学生和2个老师围绕圆桌入座，2个老师之间至少有1个学生，有多少种就座方法？（ ） {{ select(14) }}

• 36
• 72
• 48
• 84

15. 由数字1,2,3,4,5,6,7组成无重复数字的7位整数，从中任取一个，所取的数满足首位是1，且任意相邻两位数字之差的绝对值不大于2，则取到此类数的概率为（ ）。 {{ select(15) }}

• 1/120
• 1/240
• 1/360
• 1/480

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

(1)

01 #include <iostream>
02 #include <algorithm>
03 #include <string.h>
04 
05 using namespace std;
06 
07 const int N = 100000, M = 100000;
08 const long long mod = 1e8 - 3;
09 
10 struct StMatch {
11     int a, b;
12 };
13 bool operator<(const StMatch a, const StMatch b) {
14     return a.a < b.a;
15 }
16 
17 struct StTreeArray {
18     int tree[M + 1];
19     int Lb(int x) { return x & (-x); }
20     void add(int x, int t) {
21         while (x <= M) {
22             tree[x] += t;
23             x += Lb(x);
24         }
25     }
26     int sum(int x) {
27         int ans = 0;
28         while (x > 0) {
29             ans += tree[x];
30             x -= Lb(x);
31         }
32         return ans;
33     }
34 };
35 
36 StTreeArray t;
37 int n;
38 int a[N + 2], b[N + 2], pos[N + 2];
39 
40 int index(int a[], int x) {
41     int l = 1, r = n;
42     while (l < r) {
43         int m = (l + r) >> 1;
44         if (a[m] == x) return m;
45         if (a[m] < x) {
46             l = m + 1;
47         } else {
48             r = m - 1;
49         }
50     }
51     if (a[l] == x) return l;
52     if (a[r] == x) return r;
53     return 0;
54 }
55 
56 int main() {
57     cin >> n;
58     for (int i = 1; i <= n; i++) {
59         cin >> matches[i].a;
60         a[i] = matches[i].a;
61     }
62     for (int i = 1; i <= n; i++) {
63         cin >> matches[i].b;
64         b[i] = matches[i].b;
65     }
66     sort(a + 1, a + n + 1);
67     sort(b + 1, b + n + 1);
68     for (int i = 1; i <= n; i++) {
69         matches[i].a = index(a, matches[i].a);
70         matches[i].b = index(b, matches[i].b);
71         pos[matches[i].b] = i;
72     }
73     for (int i = 1; i <= n; i++) {
74         matches[i].a = pos[matches[i].a];
75     }
76     long long ans = 0;
77     for (int i = n; i >= 1; i--) {
78         ans += t.sum(matches[i].a - 1);
79         ans %= mod;
80         t.add(matches[i].a, 1);
81     }
82     cout << ans << endl;
83     return 0;
84 }

■ 判断题 16. 第19行就是计算Lowbit，即返回x表示成二进制后最右边的1在哪一位。（ ） {{ select(16) }}

• 正确
• 错误

17. 将第13、14行中的<同时或者其中之一改成<=，不影响程序结果。（ ） {{ select(17) }}

• 正确
• 错误

18. 第52行可以去掉，不影响程序结果。（ ） {{ select(18) }}

• 正确
• 错误

19. 第69行也可以去掉，不影响程序结果。（ ） {{ select(19) }}

• 正确
• 错误

■ 选择题 20. 本程序的时间复杂度是（ ）。 {{ select(20) }}

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

21. 对于输入"4 1 3 4 2 1 7 2 4"，本程序的输出为（ ）。 {{ select(21) }}

• 1
• 2
• 3
• 4

(2)

01 #include <cstdio>
02 using namespace std;
03 int gcd(int a, int b) {
04     return b == 0 ? a : gcd(b, a % b);
05 }
06 int main() {
07     int T;
08     scanf("%d", &T);
09     while (T--) {
10         int a0, a1, b0, b1;
11         scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
12         int p = a0 / a1, q = b1 / b0, ans = 0;
13         for (int x = 1; x * x <= b1; x++) {
14             if (b1 % x == 0) {
15                 if (x % a1 == 0 && gcd(x / a1, p) == 1 && gcd(q, b1 / x) == 1) ans++;
16                 int y = b1 / x;
17                 if (x == y) continue;
18                 if (y % a1 == 0 && gcd(y / a1, p) == 1 && gcd(q, b1 / y) == 1) ans++;
19             }
20         }
21         printf("%d\n", ans);
22     }
23     return 0;
24 }

■ 判断题 22. 将第17行中的continue改为break，不影响程序结果。（ ） {{ select(22) }}

• 正确
• 错误

23. 如果输入是"1 4 1 1 96 288"，则输出是"5"。（ ） {{ select(23) }}

• 正确
• 错误

24. 第13行中的x=1可以换为x=a1，程序的运行速度一定会更快。（ ） {{ select(24) }}

• 正确
• 错误

25. 本题有时间复杂度更优的做法。（ ） {{ select(25) }}

• 正确
• 错误

■ 选择题

26. 本题实质上是求符合下面哪个条件的x的个数？（ ） {{ select(26) }}

• $gcd(a0, x) = a1$ 且 $lcm(x, b1) = b0$
• $lcm(a1, x) = a0$ 且 $lcm(x, b0) = b1$
• $gcd(a0, x) = a1$ 且 $gcd(x, b1) = b0$
• $gcd(a0, x) = a1$ 且 $lcm(x, b0) = b1$

27. 如果输入是"1 95 13 717 76"，则输出是（ ）。 {{ select(27) }}

• 1
• 2
• 3
• 4

(3)

01 #include <iostream>
02 #include <string.h>
03 #include <math.h>
04 #include <algorithm>
05 using namespace std;
06 
07 const int N = 10010, MONEY = 1010, L = 1010;
08 
09 struct sLine {
10     int st, en, fun, cost;
11 };
12 int l, n, money;
13 sLine Line[N];
14 int f[L][MONEY], use[L][MONEY], jump[L][MONEY];
15 void print(int l, int cost);
16 bool comp(sLine La, sLine Lb) {
17     return (La.en < Lb.en) ||
18            (La.en == Lb.en && La.st < Lb.st);
19 }
20 
21 int main() {
22     cin >> l >> n >> money;
23     for (int i = 0; i < n; i++) {
24         cin >> Line[i].st >> Line[i].en
25             >> Line[i].fun >> Line[i].cost;
26         Line[i].en += Line[i].st;
27     }
28     sort(Line, Line + n, comp);
29 
30     memset(f, 128, sizeof(f));
31     f[0][0] = 0; jump[0][0] = -1; use[0][0] = -1;
32     for (int i = 0; i < n; i++) {
33         for (int c = money; c >= Line[i].cost; c--) {
34             int st = Line[i].st;
35             if (f[st][c - Line[i].cost] + Line[i].fun >
36                 f[Line[i].en][c]) {
37                 jump[Line[i].en][c] = st;
38                 use[Line[i].en][c] = i;
39             }
40             f[Line[i].en][c] = max(f[Line[i].en][c],
41                                    f[st][c - Line[i].cost] + Line[i].fun);
42         }
43     }
44     int ans = -1, sol = 0;
45     for (int c = 0; c <= money; c++) {
46         if (f[l][c] > ans) {
47             sol = c;
48         }
49         ans = max(ans, f[l][c]);
50     }
51     if (ans >= 0) {
52        cout << ans << endl;
53         cout << "sol=" << sol << endl;
54         print(l, sol);
55     } else {
56         cout << -1 << endl;
57     }
58     return 0;
59 }
60 void print(int l, int cost) {
61     if (l <= 0) return;
62     print(jump[l][cost], cost - Line[use[l][cost]].cost);
63     cout << "Line:" << use[l][cost]
64          << " st:" << Line[use[l][cost]].st
65          << " en:" << Line[use[l][cost]].en
66          << " fun:" << Line[use[l][cost]].fun
67          << " cost:" << Line[use[l][cost]].cost << endl;
68 }

■ 判断题 28. （2分）第16~19行是按照线段的终点排序，且终点越大的越靠前，终点相同则看起点。（ ） {{ select(28) }}

• 正确
• 错误

29. （2分）第30行中的128可以换成别的数。（ ） {{ select(29) }}

• 正确
• 错误

30. （2分）第33行倒序进行动态规划，是为了节约空间，使得f数组可以少一维。（ ） {{ select(30) }}

• 正确
• 错误

31. （2分）本题涉及线段的代价和收益，其实也可以使用最小费用最大流来解决。（ ） {{ select(31) }}

• 正确
• 错误

■ 选择题 32. （4分）若N、M、L分别为最大线段数、最大代价限制、最长区间长度，则本程序的时间复杂度为（ ）。 {{ select(32) }}

• $O(N L)$
• $O(N M L)$
• $O(M L)$
• $O(M N)$

33. （4分）如果使用最小费用最大流来解决本题，则和本程序相比，网络流解法的时间复杂度（ ）。 {{ select(33) }}

• 不能使用网络流来解决
• 更大
• 更小
• 无法确定

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

(1) 给定数a和b，对a可以进行3种操作：×2，÷2，+1。问：最少要进行多少次操作可以让a变为b？比如，输入数据为3 13，输出为8，最佳操作顺序为：3→32→16→8→9→10→11→12→13。

本题不能简单地进行深度搜索，因为前两个操作正好相互抵消，可以无限搜索下去。本程序首先使a、b满足a < b < 2a，然后尝试如何从a变成b。

01 #include <bits/stdc++.h>
02 #define int long long
03 using namespace std;
04 signed main() {
05     int a, b;
06     scanf("%lld%lld", &a, &b);
07     int cnt = 0;
08     while (a > b) {
09         cnt++;
10         if (a % 2 == 1) ①;
11         else a /= 2;
12     }
13     while (b >= a * 2) {
14         cnt++;
15         if (b % 2 == 1) ②;
16         else b /= 2;
17     }
18     if (③) {
19         printf("%lld\n", cnt);
20         return 0;
21     }
22     int aa = a, bb = b;
23     int minn = 0x3f3f3f3f, bs = 0;
24     while (aa >= 1 && bb >= 1 && aa <= bb) {
25         minn = min(minn, cnt + bs + (bb - aa));
26         if (aa % 2 == 1) ④;
27         aa /= 2;
28         bs++;
29         if (bb % 2 == 1) ⑤;
30         bb /= 2;
31         bs++;
32     }
33     printf("%lld\n", minn);
34     return 0;
35 }

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

• a++
• a--
• a *= 2
• a /= 2

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

• b++
• b--
• b *= 2
• b /= 2

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

• a = b
• a == b - 1
• a = b - 1
• a == b

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

• aa--, bs--
• aa--, bs++
• aa++, bs--
• aa++, bs++

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

• bb--, bs--
• bb++, bs++
• bb--, bs++
• bb++, bs--

(2) 输入一个字符串s，求其删掉若干个字符之后，最多能出现多少个"jessie"，并且，如果给出删掉每个字符的代价，则需求出在保证代价最小的情况下"jessie"最多出现多少次。

比如，输入数据为：

jesssie
1 1 5 4 6 1 1

输出为：

1
4

（因为3个s的代价分别为5、4、6，所以删掉的是第二个s）

又比如，输入数据为：

jejesconsiete
6 5 2 3 6 5 7 9 8 1 4 5 1

输出为：

1
21

01 #include <cstdio>
02 #include <cstring>
03 #include <iomanip>
04 #include <iostream>
05 using namespace std;
06 const int maxn = 300005;
07 char s[maxn];
08 int c[maxn][8], t[maxn][8], p[8][maxn], d[maxn];
09 int dp[maxn][8], sum[maxn], ans[maxn];
10 string jes = "jessie";
11 int main() {
12     scanf("%s", s + 1);
13     int n = strlen(s + 1);
14     for (int i = 1; i <= n; i++) {
15         cin >> d[i];
16         sum[i] = sum[i - 1] + d[i];
17     }
18     ①;
19     for (int i = 1; i <= n; i++) {
20         memcpy(dp[i], dp[i - 1], sizeof(int) * 8);
21         if (s[i] == 'j') {
22             dp[i][1] = max(dp[i][1], dp[i][0]);
23         } else if (s[i] == 'e') {
24             dp[i][2] = max(dp[i][2], dp[i][1]);
25             dp[i][6] = max(dp[i][6], dp[i][5]);
26             ②;
27         } else if (s[i] == 's') {
28             dp[i][4] = max(dp[i][4], dp[i][3]);
29             dp[i][3] = max(dp[i][3], dp[i][2]);
30         } else if (s[i] == 'i') {
31             dp[i][5] = max(dp[i][5], dp[i][4]);
32         }
33     }
34     cout << dp[n][6] << endl;
35 
36     memset(t, 0x7f, sizeof(t));
37     memset(p, 0x7f, sizeof(p));
38     memset(c, 0x7f, sizeof(c));
39     memset(ans, ③, sizeof(ans));
40     t[0][0] = sum[n];
41     p[0][1] = sum[n];
42     ans[0] = 0;
43     for (int i = 1; i <= n; i++) {
44         p[0][1] = sum[n] - sum[i - 1];
45         for (int x = 6; x >= 1; x--) {
46             if (jes[x - 1] == s[i]) {
47                 if (x == 1) {
48                     c[i][x] = ans[dp[i][x] - 1];
49                 } else {
50                     c[i][x] = ④;
51                 }
52                 t[i][x] = c[i][x] + sum[n] - sum[i];
53                 p[x][dp[i][x]] = min(p[x][dp[i][x]], t[i][x]);
54                 if (x == 6) {
55                     ans[dp[i][x]] = ⑤;
56                 }
57             }
58         }
59     }
60     cout << ans[dp[n][6]] << endl;
61     return 0;
62 }

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

• dp[0][0] = 0
• dp[0][0] = 1
• dp[0][0] = -1
• dp[0][0] = 6

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

• dp[i][0] = dp[i][6]
• dp[i][0] = dp[i][6] - 1
• dp[i][0] = dp[i][6] + 1
• dp[i][0] = max(dp[i][0], dp[i][6] + 1)

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

• 0x00
• 0xff
• 0x8f
• 0x3f

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

• p[x - 1][dp[i][x]] - sum[n] + sum[i - 1]
• p[x - 1][dp[i][x]] - sum[n] + sum[i]
• p[x - 1][dp[i][x]] - sum[n - 1] + sum[i]
• p[x - 1][dp[i - 1][x]] - sum[n] + sum[i - 1]

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

• min(ans[dp[i][x]], t[i][x])
• min(ans[dp[i][x]], p[i][x])
• min(ans[dp[i][x]], d[i][x])
• min(ans[dp[i][x]], c[i][x])

---