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

1. 执行下面代码后，b.count() 与 b.test(3) 的值分别为（）{{ select(1) }}

   bitset<8> b;
   b.set(1);
   b.set(3);
   b.set(5);
   b.flip(3);
   b.set(2);
   

• 4, 1
• 3, 0
• 3, 1
• 2, 0

2. 数组 $a[1..8]=\{5,1,4,7,3,6,2,8\}$。用 ST 表回答静态区间最值。区间 $[2,7]$ 的最大值与区间 $[3,8]$ 的最小值分别为（）{{ select(2) }}

• 7, 2
• 6, 2
• 7, 3
• 8, 2

3. 一张未压缩灰度图像大小为 $1024\times768$ 像素，每个像素占 8 位；ASCII 编码中大写字母 A 的十进制值为 65。则该图像占用的存储空间与字符 A 的编码值分别为（）{{ select(3) }}

• 768 KiB, 97
• 6144 KiB, 65
• 768 KiB, 65
• 786432 KiB, 65

4. 字符串 s="abcababc" 的最长真前缀且为后缀的长度，以及该前后缀分别为（）{{ select(4) }}

• 2, ab
• 3, cab
• 5, abcab
• 3, abc

5. 对字符串 s="abacaba" 计算 Manacher 算法中的奇回文半径 d1[i]（半径包含中心字符）。则 d1[3] 与该串的奇长度回文子串总数分别为（）{{ select(5) }}

• 4, 12
• 3, 10
• 4, 10
• 7, 12

6. 有半开区间：

[1,4), [2,6), [4,7), [5,8)

用扫描线统计覆盖情况。所有区间的并长度与覆盖层数达到最大值的总长度分别为（）{{ select(6) }}

• 7, 2
• 7, 1
• 8, 1
• 7, 3

7. 给定数组 7,2,5,10,8，要把它按原顺序划分为不超过 2 段，使每段和的最大值尽量小。最小可行上界，以及当上界取 17 时贪心判定得到的段数分别为（）{{ select(7) }}

• 17, 2
• 18, 2
• 18, 3
• 19, 3

8. 在模 $26$ 意义下求解同余方程 $7x\equiv5\pmod{26}$。最小非负解与区间 $[0,100]$ 内的解的个数分别为（）{{ select(8) }}

• 23, 3
• 15, 4
• 5, 3
• 23, 4

9. 长度为 8 的 01 串中恰有 4 个 1 且任意两个 1 不相邻的个数，以及 1..6 的排列中恰有 2 个固定点的排列数分别为（）{{ select(9) }}

• 5, 45
• 10, 135
• 5, 120
• 5, 135

10. 设

A = [1 1
     1 0],   v = [1
                  0]

则 $A^6v$ 的第一维，以及矩阵 $A^5$ 四个元素之和分别为（）{{ select(10) }}

• 8, 21
• 13, 21
• 13, 18
• 21, 34

11. 对一个大根堆依次插入 4,1,7,3,9,2，弹出两次，再插入 6,5。最终堆顶元素与两次弹出元素之和分别为（）{{ select(11) }}

• 7, 16
• 6, 14
• 6, 16
• 5, 16

12. 无权图有边：

(1,2), (1,3), (2,4), (3,4), (4,5), (3,6)

从 1 号点开始 BFS，点 5 的最短距离，以及恰好距离 1 号点为 2 的点数分别为（）{{ select(12) }}

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

13. set<int> S={2,5,8,11}。执行：

auto it = S.lower_bound(6);
int x = *it;
S.erase(S.lower_bound(5));
int y = *S.lower_bound(5);

则 x 与 S.size() 分别为（）{{ select(13) }}

• 8, 3
• 5, 3
• 8, 4
• 11, 3

14. 无向图有 4 个点，边为 (1,2),(2,3),(3,4),(4,1),(2,4)。该图是否为二分图；若删除边 (2,4) 后是否为二分图？（）{{ select(14) }}

• 是，是
• 是，否
• 否，是
• 否，否

15. 在 C++14 中，表达式 $(-7)/3$ 与 $(-7)\bmod3$ 的值分别为（）{{ select(15) }}

• -3, 2
• -2, -1
• -2, 2
• -3, -1

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

(1)

#include <bits/stdc++.h>
using namespace std;
int prec(char c) {
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    return 0;
}
void apply(vector<long long> &num, vector<char> &op, int &cnt) {
    long long b = num.back(); num.pop_back();
    long long a = num.back(); num.pop_back();
    char c = op.back(); op.pop_back();
    if (c == '+') num.push_back(a + b);
    if (c == '-') num.push_back(a - b);
    if (c == '*') num.push_back(a * b);
    if (c == '/') num.push_back(a / b);
    ++cnt;
}
int main() {
    string s;
    cin >> s;
    vector<long long> num;
    vector<char> op;
    int applied = 0, depth = 0, maxDepth = 0, maxOps = 0;
    bool needNumber = true;
    for (int i = 0; i < (int)s.size(); ) {
        if (isdigit(s[i]) ||
            (s[i] == '-' && needNumber && i + 1 < (int)s.size() && isdigit(s[i + 1]))) {
            int sign = 1;
            if (s[i] == '-') sign = -1, ++i;
            long long x = 0;
            while (i < (int)s.size() && isdigit(s[i])) {
                x = x * 10 + (s[i] - '0');
                ++i;
            }
            num.push_back(sign * x);
            needNumber = false;
        } else if (s[i] == '(') {
            op.push_back(s[i++]);
            ++depth;
            maxDepth = max(maxDepth, depth);
            maxOps = max(maxOps, (int)op.size());
            needNumber = true;
        } else if (s[i] == ')') {
            while (!op.empty() && op.back() != '(') apply(num, op, applied);
            op.pop_back();
            --depth;
            ++i;
            needNumber = false;
        } else {
            while (!op.empty() && op.back() != '(' && prec(op.back()) >= prec(s[i]))
                apply(num, op, applied);
            op.push_back(s[i++]);
            maxOps = max(maxOps, (int)op.size());
            needNumber = true;
        }
    }
    while (!op.empty()) apply(num, op, applied);
    cout << num.back() << " " << applied << " " << maxDepth << " " << maxOps << "\n";
    return 0;
}

给定输入：

12/(2-5)+7*(3-1)-8/3

16. 程序中的除法使用 C++ 整数除法，商向 0 截断。（）{{ select(16) }}

• 对
• 错

17. 对给定输入，maxOps 的值为 4。（）{{ select(17) }}

• 对
• 错

18. 若输入中出现 -(2+3)，程序仍能把它正确当成一元负号处理。（2分）{{ select(18) }}

• 对
• 错

19. 对给定输入，程序输出为（）{{ select(19) }}

• 8 7 1 4
  

• 7 7 1 4
  

• 8 6 1 3
  

• 9 7 2 4
  

20. 若仅把输入开头的 12 改为 15，最终表达式值为（）{{ select(20) }}

• 8
• 7
• 6
• 9

21. 设输入表达式长度为 L，该程序时间复杂度为（）{{ select(21) }}

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

(2)

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main() {
    int n;
    cin >> n;
    vector<int> a(2 * n + 1), pre(2 * n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    for (int i = 1; i <= 2 * n; ++i) pre[i] = pre[i - 1] + a[i];
    vector<vector<int> > dp(2 * n + 2, vector<int>(2 * n + 2, 0));
    vector<vector<int> > ways(2 * n + 2, vector<int>(2 * n + 2, 0));
    for (int i = 1; i <= 2 * n; ++i) ways[i][i] = 1;
    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= 2 * n; ++l) {
            int r = l + len - 1;
            dp[l][r] = INF;
            int sum = pre[r] - pre[l - 1];
            for (int k = l; k < r; ++k) {
                int val = dp[l][k] + dp[k + 1] + sum;
                int cnt = ways[l][k] * ways[k + 1][r];
                if (val < dp[l][r]) {
                    dp[l][r] = val;
                    ways[l][r] = cnt;
                } else if (val == dp[l][r]) {
                    ways[l][r] += cnt;
                }
            }
        }
    }
    int best = INF, cntStart = 0;
    for (int l = 1; l <= n; ++l) {
        int v = dp[l][l + n - 1];
        if (v < best) best = v, cntStart = 1;
        else if (v == best) ++cntStart;
    }
    cout << best << " " << cntStart << "\n";
    cout << dp[1][n] << " " << ways[1][n] << "\n";
    return 0;
}

给定输入：

5
3 1 4 1 5

22. 将数组复制一遍，是为了把环上的连续段转化为线性区间。（）{{ select(22) }}

• 对
• 错

23. 对给定输入，最小合并代价为 32，达到该代价的起点有 4 个。（）{{ select(23) }}

• 对
• 错

24. ways[l][r] 表示区间 [l,r] 达到最优值的分割方案数，而不是起点数量。（2分）{{ select(24) }}

• 对
• 错

25. 对给定输入，程序输出为（）{{ select(25) }}

• 32 4
  32 2
  

• 32 2
  32 4
  

• 33 4
  32 2
  

• 32 4
  33 2
  

26. 对给定输入，dp[2][6] 的值为（）{{ select(26) }}

• 32
• 34
• 33
• 31

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

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

(3)

#include <bits/stdc++.h>
using namespace std;
struct Rect {
    int x1, y1, x2, y2;
};
int main() {
    int n;
    cin >> n;
    vector<Rect> rec(n);
    vector<int> xs, ys;
    for (int i = 0; i < n; ++i) {
        cin >> rec[i].x1 >> rec[i].y1 >> rec[i].x2 >> rec[i].y2;
        xs.push_back(rec[i].x1);
        xs.push_back(rec[i].x2);
        ys.push_back(rec[i].y1);
        ys.push_back(rec[i].y2);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    vector<vector<int> > diff(xs.size() + 1, vector<int>(ys.size() + 1, 0));
    auto xid = [&](int x) {
        return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    };
    auto yid = [&](int y) {
        return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
    };
    for (auto r : rec) {
        int a = xid(r.x1), b = xid(r.x2);
        int c = yid(r.y1), d = yid(r.y2);
        diff[a][c] += 1;
        diff[b][c] -= 1;
        diff[a][d] -= 1;
        diff[b][d] += 1;
    }
    long long coverArea = 0, maxArea = 0, checksum = 0;
    int maxCover = 0, cells = 0;
    for (int i = 0; i + 1 < (int)xs.size(); ++i) {
        for (int j = 0; j + 1 < (int)ys.size(); ++j) {
            diff[i][j] += (i ? diff[i - 1][j] : 0)
                        + (j ? diff[i][j - 1] : 0)
                        - (i && j ? diff[i - 1][j - 1] : 0);
            long long area = 1LL * (xs[i + 1] - xs[i]) * (ys[j + 1] - ys[j]);
            int cover = diff[i][j];
            if (cover > 0) coverArea += area;
            if (cover > maxCover) {
                maxCover = cover;
                maxArea = area;
                cells = 1;
            } else if (cover == maxCover) {
                maxArea += area;
                ++cells;
            }
            checksum += 1LL * cover * area;
        }
    }
    cout << coverArea << " " << maxCover << " " << maxArea << "\n";
    cout << cells << " " << checksum << "\n";
    return 0;
}

给定输入：

4
0 0 4 3
2 1 6 4
1 3 5 5
4 0 7 2

28. 坐标压缩后按相邻坐标形成小矩形，可以精确保留原矩形覆盖面积。（）{{ select(28) }}

• 对
• 错

29. 本程序把每个输入矩形视为左闭右开区域 [x1,x2) x [y1,y2)。（）{{ select(29) }}

• 对
• 错

30. 变量 maxArea 表示达到最大覆盖层数的压缩小矩形个数。（2分）{{ select(30) }}

• 对
• 错

31. 对给定输入，程序输出为（）{{ select(31) }}

• 29 2 9
  6 38
  

• 29 3 9
  6 38
  

• 30 2 9
  6 38
  

• 29 2 6
  9 38
  

32. 若删除第 4 个矩形，则第一行的 coverArea 变为（4分）{{ select(32) }}

• 23
• 25
• 29
• 32

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

(1)（路线跳跃的最优前驱）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> w(n + 1), dp(n + 1, (1LL << 60));
    vector<int> pre(n + 1, -1);
    for (int i = 1; i <= n; ++i) cin >> w[i];
    dp[0] = 0;
    set<pair<long long, int> > cand;
    cand.insert(make_pair(0LL, 0));
    int expired = 0;
    for (int i = 1; i <= n; ++i) {
        while (____(1)____) {
            cand.erase(____(2)____);
            ++expired;
        }
        pair<long long, int> best = *cand.begin();
        dp[i] = ____(3)____;
        ____(4)____;
        cand.insert(____(5)____);
    }
    cout << dp[n] << " " << pre[n] << "\n";
    return 0;
}

样例输入：

7 3
4 2 7 1 3 6 2

33. ____(1)____ 处应填（）{{ select(33) }}

• expired < i - k
• expired > i - k
• cand.empty()
• dp[expired] < k

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

• make_pair(w[expired], expired)
• make_pair(dp[i], i)
• make_pair(dp[expired], expired)
• make_pair(best.first, best.second)

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

• best.first - w[i]
• best.first + w[i]
• dp[i - 1] + w[i]
• best.second + w[i]

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

• pre[i] = expired
• pre[i] = i - k
• pre[i] = cand.size()
• pre[i] = best.second

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

• make_pair(dp[i], i)
• make_pair(w[i], pre[i])
• make_pair(dp[pre[i]], pre[i])
• make_pair(dp[n], n)

(2)（混合括号串的最长合法片段）

#include <bits/stdc++.h>
using namespace std;
struct Item {
    char ch;
    int pos;
};
bool match(char l, char r) {
    return (l == '(' && r == ')') || (l == '[' && r == ']');
}
int main() {
    string s;
    cin >> s;
    stack<Item> st;
    st.push(Item{'#', -1});
    int best = 0, cnt = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
        char c = s[i];
        if (c == '(' || c == '[') {
            st.push(Item{c, i});
        } else {
            if (____(6)____) {
                st.pop();
                int len = ____(7)____;
                if (len > best) {
                    ____(8)____;
                    cnt = 1;
                } else if (____(9)____) {
                    ++cnt;
                }
            } else {
                while (!st.empty()) st.pop();
                ____(10)____;
            }
        }
    }
    cout << best << " " << cnt << "\n";
    return 0;
}

样例输入：

([])[)]([])

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

• st.empty()
• st.size() > 1 && match(st.top().ch, c)
• match('#', c)
• c == '(' || c == '['

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

• st.top().pos - i
• i + st.top().pos
• i - st.top().pos
• i + 1

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

• best = len
• len = best
• best += len
• cnt = len

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

• len < best
• len == best
• st.empty()
• cnt == len

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

• st.push(Item{'#', i})
• st.push(Item{c, i})
• best = 0
• --cnt