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

1. C++语言中析构函数的主要作用是（ ）。 {{ select(1) }}

• 为对象分配内存空间
• 对对象的静态数据成员进行初始化
• 重载对象的运算符
• 在对象生命周期结束时释放资源，执行清理任务

2. 以下关于NOI Linux的文件操作需要十分谨慎的是（ ）。 {{ select(2) }}

• rm -r
• cp -a
• mkdir
• diff

3. 以下哪一项并非STL中集合容器所具备的操作函数？（ ） {{ select(3) }}

• insert
• swap
• front
• lower_bound

4. 设$A = B = true$，$C = D = false$，以下逻辑运算表达式的值为假的是（ ）。 {{ select(4) }}

• $(\neg A \land B) \lor (C \land D \lor A)$
• $\neg (((A \land B) \lor C) \land D)$
• $A \land (B \lor C \lor D) \lor D$
• $(A \land (D \lor C)) \land B$

5. 阅读以下用动态规划解决0-1背包问题的函数，假设背包的容量是10kg，4个物品的a（重量）分别为1,3,4,6（单位为kg），每个物品对应的b（价值）分别为20,30,50,60，则函数的输出为（ ）。

int knapsack(int w, const vector<int> a, const vector<int> b, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(w + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= w; w++) {
            if (a[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - a[i - 1]] + b[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][w];
}

{{ select(5) }}

• 90
• 100
• 110
• 140

6. 给定一棵二叉树，其前序遍历结果为1 2 4 5 3 6 7，中序遍历结果为4 5 2 1 3 6 7，则这棵树的后序遍历结果为（ ）。 {{ select(6) }}

• 5 4 2 7 6 3 1
• 5 4 7 2 6 3 1
• 4 5 2 7 6 3 1
• 4 2 5 7 6 3 1

7. 一棵有n个结点的二叉树，执行释放全部结点操作的时间复杂度是（ ）。 {{ select(7) }}

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

8. 下列选项中，（ ）不是动态规划算法中常见的优化手段。 {{ select(8) }}

• 滚动数组
• 单调队列
• 自动机
• 状态压缩

9. 下面哪个说法是错误的？（ ） {{ select(9) }}

• 向量又称矢量
• 多重集合不是集合
• 高斯消元法可以求逆矩阵和行列式
• 矩阵只能做加减运算，不能做乘法运算

10. 设正整数$1 ≤ n ≤ 2025$，则使$n^5 - 5n^3 + 4n + 15$是完全平方数的可能的n的个数为（ ）个。 {{ select(10) }}

• 3
• 0
• 1
• 2

11. 以下哪种数据结构是线性数据结构？（ ） {{ select(11) }}

• trie
• Treap
• deque
• Splay

12. 冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序和桶排序算法中有（ ）个是稳定的。 {{ select(12) }}

• 3
• 4
• 5
• 2

13. 对于一个正整数n，如果能找到正整数a和b使得$n = a + b + ab$，则称n为奇特数，例如$3 = 1 + 1 + 1*1$就是一个奇特数，从1到100中有（ ）个奇特数。 {{ select(13) }}

• 74
• 72
• 73
• 75

14. 现有7把钥匙和7把锁，用这些钥匙随机开锁，则A1,A2,A3这三把钥匙全部不能打开对应锁的概率是（ ）。 {{ select(14) }}

• 3/7
• 67/105
• 12/35
• 9/49

15. 以下哪种方法不是解决哈希冲突的方法？（ ） {{ select(15) }}

• 开哈希法
• 线性探查法
• 二次探查法
• 复杂哈希函数

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

(1)

01 #include <bits/stdc++.h>
02 
03 #define N 1005
04 using namespace std;
05 
06 int n, m, t, fi[N], cnt, f[N][N], mh[N], ans;
07 bool vis[N];
08 char c[N];
09 
10 struct pf {
11     int ne, to;
12 } L[N * N];
13 
14 struct data {
15     int x, y;
16 } a[N];
17 
18 inline void add(int x, int y) {
19     L[++cnt].ne = fi[x];
20     L[cnt].to = y;
21     fi[x] = cnt;
22 }
23 
24 inline int read() {
25     int res = 0, f = 1; char ch = getchar();
26     while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
27     while (ch >= '0' && ch <= '9') { res = res * 10 + ch - '0'; ch = getchar(); }
28     return res * f;
29 }
30 
31 inline bool dfs(int u) {
32     for (int i = fi[u]; i; i = L[i].ne) {
33         int v = L[i].to;
34         if (vis[v]) continue;
35         vis[v] = 1;
36         if (!mh[v] || dfs(mh[v])) {
37             mh[v] = u;
38             return 1;
39         }
40     }
41     return 0;
42 }
43 
44 int main() {
45     n = read(), m = read();
46     for (int i = 1; i <= n; ++i) {
47         scanf("%s", c + 1);
48         for (int j = 1; j <= m; ++j)
49             if (c[j] == '1') { a[++t].x = i; a[t].y = j; }
50     }
51     for (int i = 1; i <= t; ++i)
52         for (int j = i + 1; j <= t; ++j)
53             if ((a[i].y + 1 == a[j].y && a[i].x == a[j].x) || (a[i].y == a[j].y && a[i].x + 1 == a[j].x))
54                 f[i][j] = 1;
55     for (int k = 1; k <= t; ++k)
56         for (int i = 1; i <= t; ++i)
57             for (int j = 1; j <= t; ++j)
58                 f[i][j] |= f[i][k] && f[k][j];
59     for (int i = 1; i <= t; ++i)
60         for (int j = 1; j <= t; ++j)
61             if (f[i][j]) add(i, j + t);
62     for (int i = 1; i <= t; ++i) {
63         memset(vis, 0, sizeof(vis));
64         if (dfs(i)) ++ans;
65     }
66     printf("%d\n", t - ans);
67     return 0;
68 }

假设$1 ≤ N, M ≤ 20$，输入1的个数不会超过200个，回答下列问题。

■ 判断题

16. 这段代码的时间复杂度为$O(N^2)$。（ ） {{ select(16) }}

• 正确
• 错误

17. 这段代码的空间复杂度为$O(N^2)$。（ ） {{ select(17) }}

• 正确
• 错误

18. t的最大值为$n*m$。（ ） {{ select(18) }}

• 正确
• 错误

■ 选择题

19. 若读入

5 5
00100
11111
00100
11111
00100

则程序运行跳出第51行的循环后，有多少个$f[i][j]$的初始值为1？（ ） {{ select(19) }}

• 10
• 11
• 12
• 13

20. 若读入

5 5
10101
10101
01110
11111
00100

则程序运行跳出第51行的循环后，有多少个$f[i][j]$的初始值为1？（ ） {{ select(20) }}

• 13
• 14
• 15
• 16

(2)

01 #include <stdio.h>
02 #include <iostream>
03 #include <algorithm>
04 #include <cstring>
05 using namespace std;
06 const int Maxn = 3e5 + 10;
07 char s[Maxn];
08 int a[Maxn], b[Maxn];
09 int f[Maxn];
10 int n;
11 inline bool cmp(int x, int y) {
12     return x > y;
13 }
14 int main() {
15     scanf("%s", s + 1);
16     n = strlen(s + 1);
17     for (int i = 1; i <= n; ++i)
18         a[i] = s[i] - 'a';
19     scanf("%s", s + 1);
20     for (int i = 1; i <= n; ++i)
21         b[i] = s[i] - 'a';
22     sort(a + 1, a + 1 + n);
23     sort(b + 1, b + 1 + n, cmp);
24     int x = 0, y = 0, pos = n;
25     for (int i = 1; i <= n; ++i) {
26         if (a[x + 1] >= b[y + 1]) { pos = i - 1; break; }
27         if (i % 2) f[i] = a[++x];
28         else f[i] = b[++y];
29     }
30     x = y = (n >> 1) + 1;
31     if (!(n % 2)) ++x;
32     for (int i = n; i > pos; --i) {
33         if ((pos + (n - i + 1)) % 2) f[i] = a[--x];
34         else f[i] = b[--y];
35     }
36     for (int i = 1; i <= n; ++i)
37         putchar(f[i] + 'a');
38     putchar('\n');
39     return 0;
40 }

假设读入的两个字符串长度n满足$1 ≤ n ≤ 3e5$，其他输入均合法，回答下列问题。

■ 判断题

21. 第23行排序的cmp函数使得b数组变为从大到小排列，为达到同样的效果也可以使用less<int>。（ ） {{ select(21) }}

• 正确
• 错误

22. std::sort()的时间复杂度是随机的，从$O(N)$到$O(N^2)$都有可能。（ ） {{ select(22) }}

• 正确
• 错误

23. （2分）假设这里用的sort采用了快速排序，那么快速排序是稳定的，即对于$i < j$，当$a[i] = a[j]$时，排序后$a[i]$一定在$a[j]$前。（ ） {{ select(23) }}

• 正确
• 错误

24. （2分）若将第30行代码x = y = (n >> 1) + 1;改为x = y = n >> 1 + 1;，程序在所有相同输入下输出不变。（ ） {{ select(24) }}

• 正确
• 错误

■ 选择题

25. 若程序输入

tinkoff
zscoder

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

• fzfsirk
• fzfsidk
• zfsfrik
• zfsfdik

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

• strlen()和vector的size()函数的时间复杂度相同，都为$O(N)$。
• 当输入两个相同的串时，该程序的输出也是这个串。
• 当输入两个不同的串a,b时，该程序也可能输出与a或b相同的串。
• 若将这段代码中的--y全部改成y--，程序依然可以输出相同的结果。

27. 假设当$n = 100$时，第33行中的f[i] = a[--x];语句最多被执行多少次？（ ） {{ select(27) }}

• 8
• 49
• 50
• 100

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 typedef long long LL;
04 const int N = 1e6 + 5, INF = 0x3f3f3f3f;
05 const LL mod = 1e9 + 7;
06 int n, L, a, b;
07 bool flag[N];
08 int c[N];
09 int dp[N];
10 struct segtree {
11     int l, r, val;
12     #define l(x) tr[x].l
13     #define r(x) tr[x].r
14     #define val(x) tr[x].val
15 } tr[N << 1];
16 void pushup(int x) {
17     val(x) = min(val(x << 1), val(x << 1 | 1));
18 }
19 void build(int l, int r, int x) {
20    l(x) = l, r(x) = r, val(x) = INF;
21     if (l == r) return;
22     int mid = l + r >> 1;
23     build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
24 }
25 void update(int pos, int v, int x) {
26     if (l(x) == r(x)) {
27         val(x) = v;
28         return;
29     }
30     int mid = l(x) + r(x) >> 1;
31     if (mid >= pos) update(pos, v, x << 1);
32     else update(pos, v, x << 1 | 1);
33     pushup(x);
34 }
35 int query(int l, int r, int x) {
36     if (l <= l(x) && r(x) <= r) return val(x);
37     int mid = l(x) + r(x) >> 1, res = INF;
38     if (l <= mid) res = query(l, r, x << 1);
39     if (r > mid) res = min(res, query(l, r, x << 1 | 1));
40     return res;
41 }
42 int main() {
43     ios::sync_with_stdio(false);
44     cin.tie(nullptr);
45     cin >> n >> L >> a >> b;
46     for (int i = 1; i <= n; i++) {
47         int x, y;
48         cin >> x >> y;
49         c[x + 1]++, c[y]--;
50     }
51     for (int i = 1; i <= L; i++) {
52         c[i] += c[i - 1];
53         if (c[i] > 0) flag[i] = true;
54     }
55     build(0, L, 1);
56     update(0, 0, 1);
57     for (int i = a * 2; i <= L; i += 2) {
58         if (flag[i]) continue;
59         int ql = max(0, i - 2 * b), qr = i - 2 * a;
60         dp[i] = query(ql, qr, 1) + 1;
61         update(i, dp[i], 1);
62     }
63     if (dp[L] >= INF) dp[L] = -1;
64     cout << dp[L] << "\n";
65     return 0;
66 }

假设对于输入满足$1 ≤ L ≤ 1e6$，$1 ≤ a ≤ b ≤ 1e3$，$1 ≤ n ≤ 1e3$，$1 ≤ S_i < E_i ≤ L$；L一定是一个偶数。

■ 判断题

28. 本段代码第15行中的N << 1应该改成N << 2，否则会发生数组下标越界。（ ） {{ select(28) }}

• 正确
• 错误

■ 选择题

29. dp数组的转移方程是（ ）。 {{ select(29) }}

• $dp[i] = \min(dp[j]), i - b \leq j \leq i - a$
• $dp[i] = \min(dp[j]), i - b*2 \leq j \leq i - a*2$
• $dp[i] = \min(dp[j]) + 1, i - b \leq j \leq i - a$
• $dp[i] = \min(dp[j]) + 1, i - b*2 \leq j \leq i - a*2$

30. 若输入

2 8
1 2
6 7
3 6

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

• -1
• 1
• 2
• 3

31. 若输入

4 8
1 2
6 7
3 6
2 4
1 8

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

• -1
• 1
• 2
• 3

32. 以下说法中正确的是（ ）。 {{ select(32) }}

• 第50行代码中的flag数组标记了$[x+1, y-1]$这个区间。
• 第56行代码update(0, 0, 1);可删去，因为这是对第0个元素更新值，完全没有必要。
• 第57行代码for (int i = a * 2; i <= L; i += 2)可以改成for (int i = a * 2; i <= L; i += 1)。
• 第60行代码中的query(ql, qr, 1)也可以写成query(ql, qr, 0)。

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

(1) 题目描述： 给你一个$n×n$的矩阵，你可以将$k×k$的连续子矩阵全部加一或者减一，初始时有m个位置不是0，其他全部是0，请问你至少需要多少次操作才能将矩阵中的所有数都变为0？如果无法实现，请输出-1。

显然，利用差分性质能够实现快速修改，具体做法是按照顺序依次修改$(1,1)$，$(1,2)$，…，$(1,n)$，…，$(n,n)$。

01 #include <bits/stdc++.h>
02 #define ll long long
03 using namespace std;
04 ll d[5010][5010], f[5010][5010];
05 int n, m, k;
06 void cf(int x, int y, int c) {
07     int xx = x + k, yy = y + k;
08     if (①) {
09         cout << "-1";
10         exit(0);
11     }
12     d[x][y] -= c;
13     d[xx][y] += c;
14     d[x][yy] += c;
15     ②;
16 }
17 int main() {
18     ll ans = 0;
19     scanf("%d%d%d", &n, &m, &k);
20     while (m--) {
21         int x, y;
22         ll z;
23         scanf("%d%d%lld", &x, &y, &z);
24         f[x][y] = z;
25     }
26     for (int i = 1; i <= n; i++)
27         for (int j = 1; j <= n; j++) {
28             d[i][j] += ③;
29             ll k = ④;
30             if (k) {
31                 ans += ⑤;
32                 cf(i, j, k);
33             }
34         }
35     printf("%lld", ans);
36     return 0;
37 }

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

• xx >= n + 1 || yy >= n + 1
• xx > n + 1 && yy > n + 1
• xx < 1 || yy < 1
• xx < 1 && yy < 1

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

• d[yy][xx] -= c
• d[yy][xx] += c
• d[xx][yy] -= c
• d[xx][yy] += c

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

• -d[i - 1][j - 1]
• d[i][j - 1] - d[i - 1][j - 1]
• d[i - 1][j] - d[i - 1][j - 1]
• d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]

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

• d[i][j]
• f[i][j]
• d[i][j] + f[i][j]
• d[i][j] - f[i][j]

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

• 1
• abs(k)
• k
• -k

(2) 题目描述： 给定一个序列，选择一个前缀和一个与之不相交的后缀，使得所有被选择的数的异或和最大。

先计算并且插入所有后缀异或和$bk[i]$，从前往后记录当前前缀和cur，删除后缀异或和并在Trie树里面寻找与cur对应的异或最大值，更新答案即可。

01 #include <bits/stdc++.h>
02 #define ll long long
03 #define reg register
04 #define F(i, a, b) for (reg int i = (a); i <= (b); ++i)
05 inline ll read();
06 using namespace std;
07 const int N = 1e5 + 10;
08 int n, trie[N * 64][2], cnt = 1, rec[N + 64];
09 ll bk[N], a[N], ans;
10 inline void insert(ll x) {
11     int p = 1;
12     for (reg int i = 62; i >= 0; i--) {
13         bool k = (x & (①));
14         if (!trie[p][k]) trie[p][k] = ++cnt;
15         p = trie[p][k];
16         ②;
17     }
18 }
19 inline void del(ll x) {
20     int p = 1;
21     for (reg int i = 62; i >= 0; i--) {
22         bool k = (x & (1LL << i));
23         if (!rec[p] || !trie[p][k]) return;
24         p = trie[p][k];
25         rec[p]--;
26     }
27 }
28 inline ll search(ll x) {
29     int p = 1;
30     ll s = 0;
31     for (reg int i = 62; i >= 0; i--) {
32         bool k = (x & (1LL << i));
33         s <<= 1;
34         int to = ③;
35         if (!to || !rec[to]) {
36             if (rec[trie[p][k]] && trie[p][k]) p = trie[p][k];
37             else break;
38         } else {
39             p = to;
40             s |= 1;
41         }
42     }
43     return s;
44 }
45 int main() {
46     n = read();
47     F(i, 1, n) a[i] = read();
48     for (reg int i = n; i >= 1; i--) {
49         bk[i] = ④;
50         insert(bk[i]);
51     }
52     ll cur = 0;
53     ans = search(cur);
54     F(i, 1, n) {
55         cur ^= a[i];
56         ⑤;
57         ans = max(ans, search(cur));
58     }
59     printf("%lld", ans);
60     return 0;
61 }
62 inline ll read() { // 快速读入
63     reg ll x = 0;
64     reg char c = getchar();
65     while (!isdigit(c)) c = getchar();
66     while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
67     return x;
68 }

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

• 1LL << i
• 1 << i
• pow(4, i - 1)
• pow(4LL, i - 1)

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

• 不填写
• rec[p]++
• rec[p]--
• rec[p] ^= 1

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

• trie[p][k]
• trie[p][k ^ 1]
• ++cnt
• --cnt

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

• bk[i] = bk[i + 1] ^ a[i]
• bk[i] = bk[i + 1] ^ a[i + 1]
• bk[i] = bk[i - 1] ^ a[i]
• bk[i] = bk[i - 1] ^ a[i - 1]

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

• del(i)
• del(bk[i + 1])
• del(bk[i])
• del(bk[i - 1])

---