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

1. 执行下面的程序片段后，输出结果是（ ）。 {{ select(1) }}

   unsigned int x = 2024;
   cout << (x & -x);
   
   

• $4$
• $8$
• $16$
• $2024$

2. 程序需要先读入一个整数 n，再读入一整行可能包含空格的字符串。假设相关头文件均已包含，下列写法最稳妥的是（ ）。{{ select(2) }}

•   cin >> n;
    getline(cin, s);
  

•   cin >> n;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    getline(cin, s);
  

•   cin >> n;
    cin.clear();
    getline(cin, s);
  

•   cin >> n >> s;
  

3. 一棵有 $2026$ 个结点的完全二叉树，按从上到下、从左到右的顺序编号为 $1 \sim 2026$。这棵树的叶子结点个数是（ ）。{{ select(3) }}

• $1012$
• $1013$
• $1024$
• $2026$

4. 已知某二叉树的先序遍历为 A B D E C F G，中序遍历为 D B E A F C G。该二叉树的后序遍历为（ ）。{{ select(4) }}

• D E B F G C A
• D B E F C G A
• D E B G F C A
• B D E C F G A

5. 设 $n$ 为正整数，下列代码片段中，doSomething() 的执行次数量级是（ ）。 {{ select(5) }}

   for (int i = 1; i <= n; i++) {
       for (int j = i; j <= n; j += i) {
           doSomething();
       }
   }
   

• $\Theta(n)$
• $\Theta(n\log n)$
• $\Theta(n\sqrt n)$
• $\Theta(n^2)$

6. 若要比较版本号字符串，例如 "1.10" 应大于 "1.2"，"2.0" 应大于 "1.100"。规定每段均为非负整数且无空段；若段数不同，缺失段按 $0$ 处理。下列方法最合理的是（ ）。{{ select(6) }}

• 直接按字符串字典序比较
• 直接把整个字符串转成浮点数比较
• 按 . 分割后，把每一段按整数依次比较
• 只比较字符串长度

7. 设 $A,B,C$ 都是布尔变量，表达式 !(A && B) || C 与下列哪个表达式等价？（ ）{{ select(7) }}

• (!A || !B) || C
• (!A && !B) || C
• !(A || B) || C
• !A || !(B || C)

8. 一个无向图有 $10^5$ 个顶点、$2 \times 10^5$ 条边。若需要遍历每个点的所有邻接点，下列存储方式最合适的是（ ）。{{ select(8) }}

• 邻接矩阵，因为访问任意两点是否相连只需 $O(1)$
• 邻接表，因为空间复杂度约为 $O(n+m)$
• 用一个数组只存每个点的度数即可
• 用二维数组 bool g[100000][100000]，因为 bool 很省空间

9. 对一个数组使用双指针维护区间和，想在线性时间内统计“和不超过 $S$ 的连续子段”。下列条件中，最关键的是（ ）。{{ select(9) }}

• 前缀和数组必须严格递增
• 数组元素都应为非负数
• 所有元素必须互不相同
• 区间长度必须固定

10. 有若干个活动，每个活动有开始时间和结束时间，要求选出尽量多的互不重叠活动。若一个活动的结束时间不晚于另一个活动的开始时间，则二者不重叠。经典贪心策略应优先选择（ ）。{{ select(10) }}

• 开始时间最早的活动
• 持续时间最短的活动
• 结束时间最早的活动
• 与其他活动重叠数量最少的活动

11. 有 $n$ 个房屋排成一个环，保证 $n \ge 2$ 且 $a_i \ge 0$。第 $i$ 个房屋价值为 $a_i$。不能同时选择相邻的两个房屋，且第 $1$ 个和第 $n$ 个也相邻。若要用线性 DP 求最大价值，最合理的处理方式是（ ）。{{ select(11) }}

• 直接对 $1 \sim n$ 做一次普通线性 DP
• 分别计算 $1 \sim n-1$ 和 $2 \sim n$ 两种情况，再取较大值
• 在价值最小的房屋处断开环，再对剩余房屋做一次线性 DP
• 按价值从大到小贪心选择不相邻的房屋

12. 对一棵有 $10^6$ 个结点的树进行深度优先遍历。若这棵树退化成一条链，使用递归 DFS 最可能遇到的问题是（ ）。{{ select(12) }}

• 时间复杂度从 $O(n)$ 变成 $O(n^2)$
• 递归层数过深，可能导致栈溢出
• DFS 无法遍历链状结构
• 必须使用邻接矩阵才能遍历

13. 在无限大的方格平面上，从 $(0,0)$ 出发，每一步只能上下左右移动一格。若要恰好用 $t$ 步到达 $(7,6)$，下列说法正确的是（ ）。{{ select(13) }}

• $t=12$ 和 $t=14$ 均可行
• $t=13$ 和 $t=15$ 均可行
• $t=13$ 可行，$t=15$ 不可行
• $t=14$ 可行，$t=16$ 不可行

14. 任意给出若干个整数并排成一列。至少需要给出（ ）个整数，才能保证一定存在一个非空连续子段，其和能被 $5$ 整除。{{ select(14) }}

• $4$
• $5$
• $6$
• $10$

15. 一个无向图有 $n$ 个顶点、$m$ 条边。设所有顶点度数之和为 $S$，则一定有（ ）。{{ select(15) }}

• $S=m$
• $S=2m$
• $S=n+m$
• $S=n^2$

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

判断题每题 $1$ 分；第 $19,20,25,26,31$ 题每题 $3$ 分；第 $21,27,32,33$ 题每题 $4$ 分。

(1)

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    vector<pair<char, int>> st;
    int erased = 0;
    for (char c : s) {
        if (!st.empty() && st.back().first == c) {
            st.back().second++;
        } else {
            st.push_back({c, 1});
        }
        if (st.back().second == 3) {
            erased += 3;
            st.pop_back();
        }
    }
    string ans;
    for (auto p : st) {
        ans.append(p.second, p.first);
    }
    cout << ans << endl;
    cout << erased << endl;
    return 0;
}

16. 判断题（1 分）：程序中的 st 保存的是当前还没有被删除的连续字符段。（ ）{{ select(16) }}

• 对
• 错

17. 判断题（1 分）：在程序运行过程中，st 中相邻两个元素的 first 一定不同。（ ）{{ select(17) }}

• 对
• 错

18. 判断题（1 分）：若把 if (st.back().second == 3) 改成 if (st.back().second >= 3)，程序输出一定不变。（ ）{{ select(18) }}

• 对
• 错

19. （3 分）若输入为：

    abbbaaacccaa
    

    程序第一行输出为（ ）。{{ select(19) }}

• aa
• a
• ccc
• 空行

20. （3 分）使用第 $19$ 题的输入，程序第二行输出为（ ）。{{ select(20) }}

• $6$
• $9$
• $10$
• $12$

21. （4 分）设输入字符串长度为 $n$，该程序的时间复杂度为（ ）。{{ select(21) }}

• $O(n)$
• $O(n\log n)$
• $O(n^2)$
• $O(3^n)$

(2)

输入保证 $1 \le a_i \le k$。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> cnt(k + 1, 0);
    int have = 0;
    int l = 0;
    int best = n + 1;
    int ways = 0;
    for (int r = 0; r < n; r++) {
        if (cnt[a[r]] == 0) have++;
        cnt[a[r]]++;
        while (have == k) {
            int len = r - l + 1;
            if (len < best) {
                best = len;
                ways = 1;
            } else if (len == best) {
                ways++;
            }
            cnt[a[l]]--;
            if (cnt[a[l]] == 0) have--;
            l++;
        }
    }
    if (best == n + 1) {
        cout << -1 << endl;
    } else {
        cout << best << " " << ways << endl;
    }
    return 0;
}

22. 判断题（1 分）：变量 have 表示当前区间 $[l,r]$ 中出现过的不同颜色数量。（ ）{{ select(22) }}

• 对
• 错

23. 判断题（1 分）：当某次外层 for 中的 while (have == k) 语句完全退出后，当前区间 $[l,r]$ 一定不再包含全部 $k$ 种颜色。（ ）{{ select(23) }}

• 对
• 错

24. 判断题（1 分）：变量 ways 表示所有包含全部 $k$ 种颜色的区间个数。（ ）{{ select(24) }}

• 对
• 错

25. （3 分）若输入为：

    10 3
    1 2 1 3 2 1 2 3 1 2
    

    程序输出的第一个数是（ ）。{{ select(25) }}

• $2$
• $3$
• $4$
• $6$

26. （3 分）使用第 $25$ 题的输入，程序输出的第二个数是（ ）。{{ select(26) }}

• $3$
• $4$
• $5$
• $6$

27. （4 分）该程序的时间复杂度为（ ）。{{ select(27) }}

• $O(n+k)$
• $O(nk)$
• $O(n^2)$
• $O(k^2)$

(3)

输入的所有整数均在 $[-10^9,10^9]$ 内。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    unordered_map<int, int> dp;
    unordered_map<int, int> pre;
    int best = 0;
    int last = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        int len = dp[x - 1] + 1;
        if (len > dp[x]) {
            dp[x] = len;
            pre[x] = x - 1;
        }
        if (dp[x] > best) {
            best = dp[x];
            last = x;
        }
    }
    cout << best << endl;
    vector<int> seq;
    int cur = last;
    int len = best;
    while (len--) {
        seq.push_back(cur);
        cur = pre[cur];
    }
    reverse(seq.begin(), seq.end());
    for (int i = 0; i < (int)seq.size(); i++) {
        if (i) cout << " ";
        cout << seq[i];
    }
    cout << endl;
    return 0;
}

28. 判断题（1 分）：dp[v] 表示当前已经读入的数中，以数值 $v$ 结尾，且相邻元素数值依次增加 $1$ 的子序列的最大长度。（ ）{{ select(28) }}

• 对
• 错

29. 判断题（1 分）：该程序求的是最长连续子数组，而不是子序列。（ ）{{ select(29) }}

• 对
• 错

30. 判断题（1 分）：对于尚未出现过的键，表达式 dp[x - 1] 的值会被当作 $0$ 使用。（ ）{{ select(30) }}

• 对
• 错

31. （3 分）若输入为：

    9
    3 4 2 3 4 5 1 2 3
    

    程序第一行输出为（ ）。{{ select(31) }}

• $3$
• $4$
• $5$
• $6$

32. （4 分）使用第 $31$ 题的输入，程序第二行输出为（ ）。{{ select(32) }}

• 1 2 3 4
• 2 3 4 5
• 3 4 5
• 1 3 4 5

33. （4 分）若认为 unordered_map 的单次访问平均为 $O(1)$，则该程序整体平均时间复杂度为（ ）。{{ select(33) }}

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

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

(1)（最长平稳片段）

某传感器连续记录了 $n$ 个数值，第 $i$ 个数值为 $a_i$。定义一个连续片段是“平稳”的，当且仅当该片段中的最大值与最小值之差不超过 $D$。 请计算最长平稳连续片段的长度。 保证 $1 \le n \le 10^5$，$0 \le D \le 10^9$，$-10^9 \le a_i \le 10^9$。 请补全程序。

#include <bits/stdc++.h>
using namespace std;
int solve(const vector<long long>& a, long long D) {
    int n = (int)a.size();
    deque<int> mx, mn;
    int l = 0;
    int ans = 0;
    for (int r = 0; r < n; r++) {
        while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
        mx.push_back(r);
        while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
        mn.push_back(r);
        while (__(34)__) {
            if (__(35)__) mx.pop_front();
            if (__(36)__) mn.pop_front();
            l++;
        }
        ans = max(ans, __(37)__);
    }
    return __(38)__;
}
int main() {
    int n;
    long long D;
    cin >> n >> D;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << solve(a, D) << endl;
    return 0;
}

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

• a[mx.front()] - a[mn.front()] > D
• a[mx.front()] - a[mn.front()] < D
• mx.front() - mn.front() > D
• r - l + 1 > D

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

• mx.front() == l
• mx.back() == l
• a[mx.front()] == l
• mx.front() < r

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

• mn.front() == l
• mn.back() == l
• a[mn.front()] == l
• mn.front() > r

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

• r - l + 1
• r - l
• mx.front() - mn.front()
• a[mx.front()] - a[mn.front()]

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

• l
• r
• D
• ans

(2)（四位密码锁）

一个四位密码锁的状态用长度为 $4$ 的数字串表示，例如 0000、0193。每次操作可以选择其中一位数字，将其加 $1$ 或减 $1$，数字按 $0,1,\ldots,9$ 循环变化，即 $9$ 加 $1$ 变成 $0$，$0$ 减 $1$ 变成 $9$。 给定起始状态 $S$、目标状态 $T$，以及若干个禁止经过的状态。请计算从 $S$ 到 $T$ 的最少操作次数。若无法到达，输出 $-1$。若起始状态等于目标状态且未被禁止，答案为 $0$。 请补全程序。

#include <bits/stdc++.h>
using namespace std;
int code(const string& s) {
    int x = 0;
    for (char c : s) {
        x = x * 10 + (c - '0');
    }
    return x;
}
string decode(int x) {
    string s(4, '0');
    for (int i = 3; i >= 0; i--) {
        s[i] = char('0' + x % 10);
        x /= 10;
    }
    return s;
}
vector<int> getNext(int state) {
    string s = decode(state);
    vector<int> res;
    for (int i = 0; i < 4; i++) {
        for (int d : {-1, 1}) {
            string t = s;
            int x = t[i] - '0';
            x = (x + d + 10) % 10;
            t[i] = char('0' + x);
            res.push_back(code(t));
        }
    }
    return res;
}
int bfs(string S, string T, const vector<int>& blocked) {
    int s = code(S);
    int t = code(T);
    if (__(40)__) return -1;
    queue<int> q;
    vector<int> dist(10000, -1);
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == t) return dist[u];
        for (int v : getNext(u)) {
            if (__(41)__) continue;
            __(42)__;
            q.push(v);
        }
    }
    return __(43)__;
}
int main() {
    string S, T;
    int m;
    cin >> S >> T >> m;
    vector<int> blocked(10000, 0);
    for (int i = 0; i < m; i++) {
        string x;
        cin >> x;
        __(39)__;
    }
    cout << bfs(S, T, blocked) << endl;
    return 0;
}

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

• blocked[code(x)] = 1
• blocked[i] = 1
• blocked[code(S)] = 1
• blocked[code(T)] = 1

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

• blocked[s] || blocked[t]
• blocked[s] && blocked[t]
• s == t
• blocked[0]

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

• blocked[v] || dist[v] != -1
• blocked[v] && dist[v] != -1
• blocked[u] || dist[v] == -1
• dist[u] != -1

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

• dist[v] = dist[u] + 1
• dist[u] = dist[v] + 1
• dist[v]++
• dist[v] = 0

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

• 0
• dist[s]
• 10000
• -1