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

1. 下面这段代码属于哪个算法的核心代码？（ ）

int primes[N], cnt;
bool v[N];
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!v[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            v[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

{{ select(1) }}

• 埃氏筛法
• 欧拉筛算法
• 分解质因数
• 中国剩余定理

2. 在Linux操作系统中，以下哪个命令的作用是分页显示普通文本类型文件csp？（ ） {{ select(2) }}

• vi csp
• more csp
• cat csp
• ls csp

3. 下列不属于视频文件格式的是（ ）。 {{ select(3) }}

• MPEG
• JPEG
• AVI
• WMV

4. 已知q为int类型变量，p为int*类型变量，下列赋值语句中不符合语法的是（ ）。 {{ select(4) }}

• +q = *p;
• *p = +q;
• q = *(p + q);
• *(p + q) = q;

5. 下列关于有向图和无向图的说法中，错误的是（ ）。 {{ select(5) }}

• n个顶点的弱连通有向图最少有$n - 1$条边
• n个顶点的强连通有向图最少有n条边
• n个顶点的简单有向图最多有$n*(n - 1)$条边
• n个顶点的简单无向图最多有$n*(n - 1)/2$条边

6. 前序遍历和中序遍历相同的二叉树为且仅为（ ）。 {{ select(6) }}

• 只有一个结点的独根二叉树
• 根结点没有右子树的二叉树
• 非叶子结点只有右子树的二叉树
• 非叶子结点只有左子树的二叉树

7. 以下哪个命令，在NOI Linux环境下能将一个名为csp.cpp的C++源文件编译并生成一个名为csp的可执行文件？（ ） {{ select(7) }}

• g++ csp.exe -o csp.cpp
• g++ -o csp.cpp csp
• g++ -o csp csp.cpp
• g++ csp.bat -o csp.cpp

8. 集合$U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$，则U的元素两两互质的三元子集个数为（ ）。 {{ select(8) }}

• 42
• 35
• 36
• 45

9. 以下关于排序算法的说法中错误的是（ ）。 {{ select(9) }}

• 堆排序在最好和最坏情况下的时间复杂度都是$O(n \log n)$
• 归并排序在最好和最坏情况下的时间复杂度都是$O(n \log n)$
• 拓扑排序从入度为0的结点开始
• 快速排序在最好和最坏情况下的时间复杂度都是$O(n \log n)$

10. 以下哪种算法不属于贪心算法？（ ） {{ select(10) }}

• 迪杰斯特拉算法
• KMP
• Kruskal
• 哈夫曼算法

11. 下列选项中，哪个不可能是下图的深度优先遍历序列？（ ）

{{ select(11) }}

• 1,5,7,8,9,4,2,3,6
• 1,4,7,8,9,5,2,3,6
• 1,2,3,5,7,8,6,9,4
• 1,2,3,6,9,8,5,7,4

12. 下面new_mem函数的时间复杂度为（ ）。

int mem[8192];
void new_mem(int n) {
    for (int i = 1; i <= n; i++) mem[i] = i;
    for (int i = 2; i <= n; i++)
        for (int j = i; j <= n; j += i) mem[j]--;
}

{{ select(12) }}

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

13. 以下关于动态规划算法的说法中，错误的是（ ）。 {{ select(13) }}

• 递推实现动态规划算法的时间复杂度总是不低于递归实现
• 动态规划算法有递推和递归两种实现形式
• 动态规划算法将原问题分解为一个或多个相似的子问题
• 动态规划算法具有无后效性

14. 由50支队伍进行排球单循环比赛，胜一局积1分，负一局积0分，且任取27支队伍能找到一个全部战胜其余26支队伍的队伍和一支全部负于其余26支队伍的队伍，问这50支队伍总共最少有（ ）种不同的积分。 {{ select(14) }}

• 51
• 50
• 49
• 48

15. 一个简单无向图有9个顶点、6条边。在最坏情况下，至少增加（ ）条边可以使其连通。 {{ select(15) }}

• 3
• 4
• 5
• 6

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

(1)

01 #include <iostream>
02 #include <algorithm>
03 #include <queue>
04 using namespace std;
05 typedef long long ll;
06 const ll MAXN = 2e5 + 5;
07 ll n, m, k;
08 struct node {
09     ll w, num;
10     bool operator<(const node& k) const {
11         return w < k.w;
12     }
13 } a[MAXN];
14 priority_queue<node> q;
15 int main() {
16     ios::sync_with_stdio(false);
17     cin >> n >> m >> k;
18     for (int i = 1; i <= n; ++i) {
19         cin >> a[i].w >> a[i].num;
20     }
21     sort(a + 1, a + n + 1);
22     q.push({-1000000000, 0});
23     ll ans = 0;
24     for (int i = n; i >= 1; --i) {
25         ll v = 0;
26         while (!q.empty()) {
27             node t = q.top();
28             q.pop();
29             if (t.w + k > a[i].w) {
30                 q.push(t);
31                 break;
32             }
33             if (t.num == a[i].num) {
34                 ans += a[i].num;
35                 q.push(a[i]);
36                 if (t.num > a[i].num) {
37                     t.num -= a[i].num;
38                     q.push(t);
39                 }
40                 break;
41             }
42             v += t.num;
43             ans += t.num;
44             a[i].num -= t.num;
45         }
46         if (v) {
47             q.push({a[i].w, v});
48         }
49     }
50     cout << ans << endl;
51     return 0;
52 }

假设输入都是合法的，回答下列问题。

■ 判断题

16. cout << endl会强行刷新缓存区，在换行较多的情况下会比cout << "\n"更慢。（ ） {{ select(16) }}

• 正确
• 错误

17. priority_queue位于头文件algorithm中。（ ） {{ select(17) }}

• 正确
• 错误

18. 该程序中，node经过sort后按照w的值从小到大排序。（ ） {{ select(18) }}

• 正确
• 错误

19. 交换第33行代码和第36行代码，程序在任意输入数据下输出不变。（ ） {{ select(19) }}

• 正确
• 错误

■ 选择题（每题2分）

20. 若输入

3 5 2
9 4
7 6
5 5

则本程序的输出是（ ）。 {{ select(20) }}

• 9
• 10
• 14
• 15

21. 这段程序的时间复杂度为（ ）。 {{ select(21) }}

• $O(1)$
• $O(N)$
• $O(N \log N)$
• $O\left(N \log^2 N\right)$

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int N = 2e5 + 5;
05 const int M = 3e5 + 5;
06 
07 struct edge {
08     int u, v, w;
09 } e[M];
10 inline bool cmp(edge aa, edge bb) { return aa.w > bb.w; }
11 
12 int f[N];
13 int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
14 
15 vector<int> mp[N];
16 int n, m, x, y, z, q, cnt;
17 int val[N], fa[N], dep[N], top[N], son[N], tot[N];
18 
19 void dfs1(int u) {
20     tot[u] = 1, dep[u] = dep[fa[u]] + 1;
21     int siz = mp[u].size();
22     for (int i = 0; i < siz; ++i) {
23         int v = mp[u][i];
24         if (v == fa[u]) continue;
25         fa[v] = u, dfs1(v);
26         tot[u] += tot[v];
27         if (tot[v] > tot[son[u]]) son[u] = v;
28     }
29 }
30 void dfs2(int u, int Top) {
31     top[u] = Top;
32     if (!son[u]) return;
33     dfs2(son[u], Top);
34     int siz = mp[u].size();
35     for (int i = 0; i < siz; ++i) {
36         int v = mp[u][i];
37         if (!top[v]) dfs2(v, v);
38     }
39 }
40 
41 int lca(int u, int v) {
42     while (top[u] != top[v]) {
43         if (dep[top[u]] < dep[top[v]]) swap(u, v);
44         u = fa[top[u]];
45     }
46     return dep[u] < dep[v] ? u : v;
47 }
48 
49 void kruskal() {
50     sort(e + 1, e + m + 1, cmp);
51     for (int i = 1; i <= n; ++i) f[i] = i;
52     for (int i = 1; i <= m; ++i) {
53         int u = find(e[i].u), v = find(e[i].v);
54         if (u == v) continue;
55         val[++cnt] = e[i].w;
56         f[cnt] = f[u] = f[v] = cnt;
57         mp[u].push_back(cnt), mp[v].push_back(cnt);
58         mp[cnt].push_back(u), mp[cnt].push_back(v);
59     }
60     for (int i = 1; i <= cnt; ++i) {
61         if (tot[i]) continue;
62         int rt = find(i);
63         dfs1(rt), dfs2(rt, rt);
64     }
65 }
66 
67 int main() {
68     scanf("%d%d%d", &n, &m, &q);
69     cnt = n;
70     for (int i = 1; i <= m; ++i) {
71         scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
72     }
73     kruskal();
74     while (q--) {
75         scanf("%d%d", &x, &y);
76         if (find(x) != find(y)) printf("-1\n");
77         else printf("%d\n", val[lca(x, y)]);
78     }
79     return 0;
80 }

假设输入数据满足$2 ≤ n, q ≤ 2 × 10^5$，$1 ≤ m ≤ 3 × 10^5$，$1 < u_i, v_i, x_i, y_i ≤ n$，$1 ≤ w_i ≤ 10^6$，$u_i ≠ v_i$，$x_i ≠ y_i$。回答下列问题。

■ 判断题

22. 两次dfs的目的在于，针对每个结点计算其所有子结点所构成子树的大小，进而找出子树大小最大的子结点，从而寻找LCA。LCA就是两点之间w的最小值。（ ） {{ select(22) }}

• 正确
• 错误

23. 本段代码中N的范围错误，应该开至两倍大小。（ ） {{ select(23) }}

• 正确
• 错误

24. （2分）本段代码的并查集不可以用于可撤销操作。（ ） {{ select(24) }}

• 正确
• 错误

■ 选择题

25. 若输入为

5 4 3
1 2 5
2 3 6
3 4 1
1 4 3
1 5
2 4
1 3

则程序输出为（ ）。 {{ select(25) }}

• -1 3 5
• 0 3 5
• -1 5 5
• -1 5 1

26. 本段代码中，如果把并查集改为按秩合并+路径压缩并查集，则代码的时间复杂度（ ）。 {{ select(26) }}

• 降低
• 不变
• 升高
• 是随机值

27. （4分）以下说法中不正确的是（ ）。 {{ select(27) }}

• 既然已经保证$u_i ≠ v_i$，则第54行代码可以删除。
• 第37行的if语句与v != son[u]等价。
• 第76行，如果考虑$x = y$的情况，那么程序只能输出-1。
• 第62行和第63行语句只会执行一次，因为很显然在dfs之前tot都为0，而一次dfs之后都为1，一直continue。

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int N = 1e5 + 10;
05 int n, k, ans, val[N], L[N], R[N];
06 vector<int> vec;```cpp
07 struct BIT {
08     int C[N];
09     inline void add(int x, int y) { for (; x <= n; x += x & -x) C[x] = max(C[x], y); }
10     inline int query(int x) {
11         int ans = 0;
12         for (; x > 0; x -= x & -x) ans = max(ans, C[x]);
13         return ans;
14     }
15 } le, re, s;
16 int main() {
17     scanf("%d%d", &n, &k);
18     val[0] = 1; val[n + 1] = n + 1;
19     for (int i = 1; i <= n; i++) scanf("%d", &val[i]);
20     for (int i = 1; i <= n; i++) vec.push_back(val[i]);
21     sort(vec.begin(), vec.end());
22     vec.erase(unique(vec.begin(), vec.end()), vec.end());
23     for (int i = 1; i <= n; i++)
24         val[i] = lower_bound(vec.begin(), vec.end(), val[i]) - vec.begin() + 1;
25     for (int i = 1; i <= n; i++) {
26         L[i] = le.query(val[i]) + 1;
27         le.add(val[i], L[i]);
28     }
29     for (int i = n; i >= 1; i--) {
30         R[i] = re.query(n - val[i] + 1) + 1;
31         re.add(n - val[i] + 1, R[i]);
32     }
33     for (int i = k + 1; i <= n + 1; i++) {
34         s.add(val[i - k - 1], L[i - k - 1]);
35         ans = max(ans, s.query(val[i]) + k + R[i]);
36     }
37     printf("%d", ans);
38     return 0;
39 }

假设输入数据均合法，(1 ≤ k ≤ n ≤ 10^5)，(1 ≤ val[i] ≤ 10^6)，回答下列问题。

■ 判断题（每题2分） 28. 对于一个int类型的正整数x来说，Lowbit(x) ≤ x。（ ） {{ select(28) }}

• 正确
• 错误

29. 之所以将val[n + 1]设置为n + 1而不是1e6 + 1，是因为无论设置为什么值，这个位置都不会被访问。（ ） {{ select(29) }}

• 正确
• 错误

30. 在(1 ≤ i ≤ n)时，L[i] + R[i]有可能比答案更大。（ ） {{ select(30) }}

• 正确
• 错误

31. 本段代码的时间复杂度是(O(n \log n))。（ ） {{ select(31) }}

• 正确
• 错误

■ 选择题 32. 若输入

5 1
1 4 2 8 5

则程序输出为（ ）。 {{ select(32) }}

• 2
• 3
• 4
• 5

33. （4分）下列说法中正确的是（ ）。 {{ select(33) }}

• 如果n变大100倍，其他条件不变，则C也要开大100倍空间。
• 这段代码的复杂度不是(O(n \log n))，而是(O(n^2))，因为vector的erase函数的复杂度是(O(n))，而里面嵌套的unique也是(O(n))，只不过这段代码的常数很小，因此能跑通10万。
• ans最大和val一样，最大为(1e6)。
• 第24行val[i] = lower_bound(vec.begin(), vec.end(), val[i]) - vec.begin() + 1，在这里用val[i] = upper_bound(vec.begin(), vec.end(), val[i]) - vec.begin() + 1得到的结果一定与前者不同。

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

(1) 题目描述： 给定一棵树，边形如((u_i, v_i))。维护以下操作：

• (op = 1)，指定一条边，将所有从(u_i)出发、不经过这条边就能到达的点的点权加k；
• (op = 2)，指定一条边，将所有从(v_i)出发、不经过这条边就能到达的点的点权加k。

输出最终每个点的点权。初始点权为0。

01 #include <bits/stdc++.h>
02 #define int long long
03 using namespace std;
04 const int N = 410000;
05 int u[N], v[N], depth[N], chafen[N], ans[N];
06 int n, q;
07 vector<int> mp[N];
08 void depdfs(int x, int fa, int dep) {
09     depth[x] = dep;
10     for (int i = 0; i < mp[x].size(); i++) {
11         int pt = mp[x][i];
12         if (pt != fa) depdfs(pt, x, dep + 1);
13     }
14 }
15 void chafendfs(int x, int fa, int v) {
16     ①;
17     ans[x] = v;
18     for (int i = 0; i < mp[x].size(); i++) {
19         int pt = mp[x][i];
20         if (pt != fa) chafendfs(pt, x, v);
21     }
22 }
23 signed main() {
24     scanf("%lld", &n);
25     for (int i = 1; i < n; i++) {
26         scanf("%lld%lld", u + i, v + i);
27         ②;
28     }
29     ③;
30     scanf("%lld", &q);
31     for (int i = 1; i <= q; i++) {
32         int op, e, val;
33         scanf("%lld%lld%lld", &op, &e, &val);
34         int ch, nch, chd, nchd;
35         if (op == 1) {
36             ch = u[e], nch = v[e];
37             chd = depth[ch], nchd = depth[nch];
38             if (chd < nchd) ④;
39             else chafen[ch] += val;
40         }
41         if (op == 2) {
42             ⑤;
43             chd = depth[ch], nchd = depth[nch];
44             if (chd < nchd) chafen[1] += val, chafen[nch] -= val;
45             else chafen[ch] += val;
46         }
47     }
48     chafendfs(1, 0, 0);
49     for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
50     return 0;
51 }

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

• v += chafen[x];
• v -= chafen[x];
• x += chafen[v];
• x -= chafen[v];

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

• mp[u[i]].push_back(v[i]);
• mp[v[i]].push_back(u[i]);
• mp[u[i]].push_back(v[i]); mp[v[i]].push_back(u[i]);
• mp[v[i]].push_back(v[i]); mp[u[i]].push_back(u[i]);

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

• depdfs(0, 0, 0);
• depdfs(0, 0, 1);
• depdfs(2, 0, 0);
• depdfs(1, 0, 1);

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

• chafen[1] -= val, chafen[nch] += val;
• chafen[1] += val, chafen[nch] += val;
• chafen[1] -= val, chafen[nch] -= val;
• chafen[1] += val, chafen[nch] -= val;

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

• ch = v[e], nch = v[e];
• ch = v[e], nch = u[e];
• ch = u[e], nch = v[e];
• ch = u[e], nch = u[e];

(2) 题目描述： 给定2n个数排成两排（每个数在2n个数中最多出现两次），一次操作可以交换任意一列中的两个数，求使每行中的数不重复的最少操作数。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int MAXN = 50050;
04 int N, h[MAXN], to[MAXN << 1], nxt[MAXN << 1], tp[MAXN << 1], tot;
05 int vis1[MAXN << 1], vis2[MAXN << 1];
06 int type[MAXN], sum[MAXN];
07 int ans;
08 inline void add(int u, int v, int t) {
09     to[++tot] = v, nxt[tot] = h[u], tp[tot] = t, h[u] = tot;
10 }
11 
12 pair<int, int> get(int x) {
13     if (vis2[x]) return make_pair(2, vis2[x]);
14     else if (vis1[x]) return make_pair(1, vis1[x]);
15     else return ①;
16 }
17 int dfs(int x, int fa) {
18     sum[x] = 1;
19     int res = ②;
20     for (int i = h[x]; i; i = nxt[i]) {
21         if (sum[to[i]]) continue;
22         type[to[i]] = ③;
23         res += dfs(to[i], x);
24         sum[x] += sum[to[i]];
25     }
26     return res;
27 }
28 int sol(int x) {
29     type[x] = 1;
30     int now = dfs(x, x);
31     return min(now, sum[x] - now);
32 }
33 
34 int main() {
35     scanf("%d", &N);
36     for (int i = 1; i <= N; ++i) {
37         int d; scanf("%d", &d);
38         pair<int, int> temp = get(d);
39         if (temp.first) {
40             add(i, temp.second, 1), add(temp.second, i, 1);
41         }
42         vis1[d] = i;
43     }
44     for (int i = 1; i <= N; ++i) {
45         int d; scanf("%d", &d);
46         pair<int, int> temp = get(d);
47         if (temp.first == 2) {
48             add(i, temp.second, 1), add(temp.second, i, 1);
49         } else if (temp.first == 1) {
50             ④;
51         }
52         vis2[d] = i;
53     }
54     for (int i = 1; i <= N; ++i) {
55         if (!sum[i]) ans += sol(i);
56     }
57     printf("%d", ans);
58     return 0;
59 }

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

• make_pair(0, vis2[x])
• make_pair(1, vis2[x])
• make_pair(2, vis2[x])
• make_pair(0, 0)

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

• 0
• (0, 0)
• make_pair(0, 0)
• pair<int>(0, 0)

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

• type[x] | 1
• type[x] ^ 1
• ~type[x]
• !type[x]

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

• add(i, temp.second, 0), add(temp.second, i, 0);
• add(i, temp.second, 1), add(temp.second, i, 0);
• add(i, temp.second, 0), add(temp.second, i, 1);
• add(i, temp.second, 1), add(temp.second, i, 1);

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

• add(i, temp.second, 0), add(temp.second, i, 1);
• add(i, temp.second, 1), add(temp.second, i, 0);
• add(i, temp.second, 0), add(temp.second, i, 0);
• add(i, temp.second, 1), add(temp.second, i, 1);

---