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

1. 浙江省省队选拔的缩写为 ZJOI，其中 O 的中文含义是（ ）。

{{ select(1) }}

• O 神
• 奥林匹克
• 省队
• 输出

2. 在方程组

$$\begin{cases} 3a+2b+5c=3,\\ a+4b+c=17,\\ -a+6b+6c=4 \end{cases}$$

中，$a$ 的值是（ ）。

{{ select(2) }}

• $3.2$
• $3$
• $-4.2$
• 前三个选项都不对

3. 关于树的直径和重心，下列说法正确的是（ ）。

{{ select(3) }}

• 一棵树最多有一条直径。
• 树的直径必然穿过树的所有重心。
• 偶数条边的树不可能有两个重心。
• 若 $n\ge 2$ 且为自然数，则 $2^n-1$ 个结点的树最多有 $2^{2n-2}$ 条直径。

4. Alice 和 Bob 正在讨论排序算法。

• Alice：我在书上看到过，基于比较的排序算法时间复杂度不会低于 $\Theta(n\log n)$。
• Bob：可是某种算法可以做到 $\Theta(n)$ 啊。
• Alice：我说的“时间复杂度”指的是平均情况，而不是最好情况。

根据上下文，Bob 最可能提到了（ ）算法。

{{ select(4) }}

• 插入排序
• 快速排序
• 基数排序
• 堆排序

5. 当输入的图是稀疏图，$m=\Theta(n)$ 时，可以使用一些数据结构来优化 Dijkstra 算法，让复杂度变成 $\Theta(n\log n)$。下面四个数据结构中，最合适的是（ ）。

{{ select(5) }}

• 单调队列
• ST 表
• 并查集
• 线段树

6. STL 是我们写代码的好帮手，下列 STL 算法模板或容器拼写正确的是（ ）。

{{ select(6) }}

• previous_permutation
• priority_queue
• kth_element
• unordered_mutimap

7. 把 $2,0,2,4,0,9,2,1$ 排成一个环，旋转后能重合的方案看成同一种，有（ ）种排法。

{{ select(7) }}

• $720$
• $5040$
• $3360$
• $420$

8. 使用两个栈 $f,b$ 来实现一个队列。具体地，每次入队就将元素压进 $b$，出队就将元素从 $f$ 弹出；特别地，若要出队时 $f$ 为空，则将 $b$ 栈中元素按照栈顶到栈底的顺序全部塞入 $f$ 栈。设操作总次数为 $n$，那么（ ）。

{{ select(8) }}

• 出队操作每次时间复杂度为 $O(1)$。
• 存在一种输入数据，使得总时间复杂度为 $O(n^2)$。
• 单次入队或出队操作的均摊时间复杂度均为 $O(1)$。
• 若还要实现 pop_back（即“若 $b$ 为空则把 $f$ 的元素塞入 $b$ 栈，然后将 $b$ 栈栈顶弹出”），不改变其他代码，仍然可以保证 $n$ 次操作总时间复杂度为 $O(n)$。

9. 以边集数组的形式给出一张 $n^k$ 个结点（假定 $k\ge 2$ 且结点编号可以 $O(1)$ 参与运算）、$n$ 条边的图，希望任求一条欧拉回路，时间复杂度最低是（ ）。

{{ select(9) }}

• $O(n)$
• $O(kn)$
• $O(kn\log n)$
• $O(n^k)$

10. 一名同学预处理了 fact、invf 数组，其中 fact[i] 表示 $i!$ 除以质数 $M=10^9+7$ 的余数，invf[i] 表示 fact[i] 在模 $10^9+7$ 意义下的乘法逆元，那么下列说法正确的是（ ）。

{{ select(10) }}

• 要求出 invf 的前 $n$ 项，时间复杂度最低为 $O(n\log n)$。
• invf[300] 和 300*invf[301] 在模 $10^9+7$ 意义下同余。
• 要计算从 $2000$ 人中选出 $500$ 人组合的方案数，可用 1ll*fact[2000]*invf[1500]%M*invf[500]%M。
• 在 CSP 第二轮考试中，为了加速预处理过程，可以在程序内直接写出 $1!,2!,\ldots,(10^6)!$ 的逆元。

11. 一份文件仅含有英文小写字母，其中字母 $a,b,c,\ldots,z$ 出现次数依次为 $2^1,2^2,\ldots,2^{26}$。若使用二进制哈夫曼编码方式，则整份文件的哈夫曼编码总长度是（ ）。

{{ select(11) }}

• $5\times 2^{26}-10$
• $2^{28}-58$
• $2^{28}-56$
• $2^{27}-54$

12. 宾果游戏是一款经典的游戏，玩法如下：

在 $n\times n$ 的棋盘上，每个格子都写有一个条件，玩家标记出所有自己满足条件的格子。如果某一条直线（一行、一列或一条对角线）上所有格子都被标记，则玩家获胜。

一名玩家正在玩一款 $n=6$ 的宾果游戏，并且失败了。他最多标记了（ ）个格子。

{{ select(12) }}

• $30$
• $29$
• $25$
• 前三个选项都不对

13. 01 背包问题（有 $n$ 个物品，每个物品有一个体积和价值。从中选出若干个，求体积不超过 $V$ 前提下价值最大值）是 NP-Hard 的，这意味着（ ）。

{{ select(13) }}

• 人们证明了该问题不是 P 问题。
• 可以在多项式时间内验证 01 背包问题一个解的正确性。
• 该问题存在 DP 做法，因此该问题存在多项式时间复杂度解法。
• 可以在多项式时间内，把哈密顿回路问题转化为 01 背包问题。

14. 执行如下代码片段后，*i 的值为（ ）。

set<int> s = {50, 10, 20, 30, 20};
auto i = ++ ++s.begin();

{{ select(14) }}

• $10$
• $12$
• $20$
• $30$

15. NOI Linux 2.0 中，拥有最高权限的用户是（ ）。

{{ select(15) }}

• CCF_NOI
• admin
• root
• Ka***5307

二、阅读程序（共 3 组，合计 40 分）

第 1 组（共 13 分）

阅读下面的程序。输入数据满足 $1\le n\le 10^5$，$1\le b_i,c_i\le n$。

#include <bits/stdc++.h>

#define N 100010
#define ll long long
#define mod 998244353
#define end {puts("0"); return 0;}

using namespace std;

inline ll rd() {
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-') flag = true;
    ll res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + c - '0';
    return flag ? -res : res;
}

int n, b[N], c[N];

int main() {
    n = rd(); ll num = 0, ans = 1;
    for (int i = 1; i <= n; i++) b[i] = rd();
    for (int i = 1; i <= n; i++) c[i] = rd();
    int mx = c[1], mn = b[1];
    for (int i = 1; i <= n; i++) {
        if ((i == 1 && b[i] != c[i]) ||
            (b[i] < b[i - 1] && c[i] > c[i - 1]))
            end
        if (i == 1) continue;
        if (b[i] > c[i]) end
        if (b[i] > mn) end
        else if (c[i] < mx) end
        else if (b[i] < mn) {
            num += mn - b[i] - 1, mn = b[i];
            continue;
        }
        else if (c[i] > mx) {
            num += c[i] - mx - 1, mx = c[i];
            continue;
        }
        if (!num) end
        ans *= num;
        ans %= mod;
        num--;
    }
    printf("%lld\n", ans);
    return 0;
}

16. （判断题，1 分）把第 6 行修改为 #define end {puts("0");return;}，程序的行为不变。

{{ select(16) }}

• 正确
• 错误

17. （判断题，1.5 分）删去第 43 行后，程序的行为不变。

{{ select(17) }}

• 正确
• 错误

18. （判断题，1.5 分）输入如下数据时，输出为 0。

5
5 4 3 2 1
1 2 3 4 5

{{ select(18) }}

• 正确
• 错误

19. （3 分）当输入如下数据时，输出为（ ）。

3
1 1 1
1 3 3

{{ select(19) }}

• $0$
• $1$
• $2$
• $3$

20. （3 分）输入如下数据时，若在第 43 行后要求输出 num 的值并删去第 48 行，则输出的结果为（ ）。

6
3 3 1 1 1 1
3 4 4 6 6 6

{{ select(20) }}

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

21. （3 分）当 $n=10$，$b_1=c_1=c_2=5$，$b_i=1\ (i\ge 2)$，$c_i=10\ (i\ge 3)$ 时，输出为（ ）。

{{ select(21) }}

• $720$
• $5040$
• $40320$
• $362880$

第 2 组（共 13 分）

阅读下面的程序。令 $\sum |s_i|=m$。输入数据满足 $1\le n,m\le 10^3$，且字符串仅含有小写字母。

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'

const int N = 1e3 + 5, INF = 1e18, M = 26;
int n, g[N], d[N]; string s[N];

int change(char c) {
    return c - 'a';
}

namespace A {
    int t[N][M], cnt, f[N], tot;

    void insert(string s, int i) {
        int p = 0;
        for (char c : s) {
            int k = change(c);
            if (!t[p][k])
                t[p][k] = ++cnt;
            p = t[p][k];
        }
        f[p] = i;
        return;
    }

    void dfs(int u = 0) {
        if (f[u])
            g[f[u]] = ++tot, d[tot] = f[u];
        for (char c = 'a'; c <= 'z'; c++)
            if (t[u][change(c)]) dfs(t[u][change(c)]);
        return;
    }
}

namespace B {
    vector<int> cnt[N];

    void sort(vector<tuple<int, int>>& e) {
        for (int k = 0; k < e.size(); k++) {
            int v = get<0>(e[k]), i = get<1>(e[k]);
            cnt[i].push_back(v);
        }
        e.clear();
        for (int i = 1; i <= n; i++)
            for (int v : cnt[i]) e.push_back({v, i});
        for (int i = 1; i <= n; i++)
            cnt[i].clear();
        return;
    }
}

namespace C {
    int n = 26, m, x[N], y[N], b = 0, b1 = 0, b2 = 0, f = INF, h[N];
    vector<tuple<int, int>> e[N];

    void make(int u, int v, int i) {
        u++, v++;
        e[u].push_back({v, i});
        x[u]++, y[v]++;
        f = min(f, min(u, v));
        return;
    }

    stack<int> t;

    void dfs(int u) {
        while (h[u] < e[u].size()) {
            int q = d[get<1>(e[u][h[u]])];
            dfs(get<0>(e[u][h[u]++])), t.push(q);
        }
        return;
    }

    void work() {
        for (int i = 1; i <= n; i++)
            if (x[i] == y[i]) b++;
            else if (x[i] - y[i] == 1) b1++, f = i;
            else if (y[i] - x[i] == 1) b2++;
            else cout << "No Solution!" << endl, exit(0);
        if (!(b == n || (b1 == 1 && b2 == 1)))
            cout << "No Solution!" << endl, exit(0);
        for (int i = 1; i <= n; i++) B::sort(e[i]);
        dfs(f); assert(t.size() == m);
        while (!t.empty()) cout << s[t.top()], t.pop(); cout << endl;
        return;
    }
}

signed main() {
    cin >> n; C::m = n;
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= n; i++) A::insert(s[i], i);
    A::dfs();
    for (int i = 1; i <= n; i++)
        C::make(change(s[i].front()), change(s[i].back()), g[i]);
    C::work();
    return 0;
}

22. （判断题，1 分）将第 5 行删去，程序的行为不变。

{{ select(22) }}

• 正确
• 错误

23. （判断题，1 分）将第 12 行的 c - 'a' 改为 c - 'a' + 1，程序的行为不变。

{{ select(23) }}

• 正确
• 错误

24. （判断题，1.5 分）将第 39 行的 get<0>(e[k]) 改为 e[k].first，程序的行为不变。

{{ select(24) }}

• 正确
• 错误

25. （判断题，1.5 分）程序总是能正常运行。

{{ select(25) }}

• 正确
• 错误

26. （2 分）当输入如下数据时，输出为（ ）。

3
aab
aza
aea

{{ select(26) }}

• azaaeaaab
• aabaeaaza
• aaaaaabez
• aeaazaaab

27. （3 分）执行第 86 行后，$n$ 和 namespace A 中的 tot 的大小关系为（ ）。

{{ select(27) }}

• 总是 $n=tot$
• 有时 $n<tot$，有时 $n=tot$
• 有时 $n>tot$，有时 $n=tot$
• 无法确定

28. （3 分）我们认为 $n,m$ 同阶，字符集大小为 $k$，则程序的时间复杂度为（ ）。

{{ select(28) }}

• $O(n)$
• $O(n^2)$
• $O(k\cdot n)$
• $O(k\cdot n^2)$

第 3 组（共 14 分）

阅读下面的程序。若无特殊说明，保证输入的字符串包含且仅包含小写字母，且长度在 $[1,10^7]$ 之间。

#include <bits/stdc++.h>
using namespace std;

#define Ull unsigned long long

const int Mul = 29, L = 10000005;
char a[L];
Ull pre[L], suf[L], pw[L];

Ull prehash(int l, int r) {
    l--;
    Ull res = pre[l] * pw[r - l];
    return pre[r] - res;
}

Ull sufhash(int l, int r) {
    r++;
    Ull res = suf[r] * pw[r - l];
    return suf[l] - res;
}

int main() {
    scanf("%s", a + 1);
    int n = strlen(a + 1);
    pw[0] = 1;
    for (int i = 1; i <= n; i++)
        pw[i] = pw[i - 1] * Mul;
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] * Mul + a[i];
    for (int i = n; i; i--)
        suf[i] = suf[i + 1] * Mul + a[i];
    int l = 1, r = 0, res1 = 0;
    while (r <= n) {
        while (l && prehash(l, r) == sufhash(l, r))
            l--, r++;
        l++, r--;
        res1 = r - l + 1;
        l++, r++;
        while (r <= n && prehash(l, r) != sufhash(l, r))
            l++, r++;
    }
    l = 1, r = 1;
    int res2 = 1;
    while (r <= n) {
        while (l && prehash(l, r) == sufhash(l, r))
            l--, r++;
        l++, r--;
        res2 = r - l + 1;
        l++, r++;
        while (r <= n && prehash(l, r) != sufhash(l, r))
            l++, r++;
    }
    printf("%d", max(res1, res2));
    return 0;
}

29. （判断题，1.5 分）若去掉第 33 行，程序可能死循环。

{{ select(29) }}

• 正确
• 错误

30. （判断题，1.5 分）若随机生成一个长度为 $10^5$ 字符的字符串作为输入，则在第 27 行运行结束后，等式 prehash(921,2024)==sufhash(921,2024) 成立的概率约为 $10^{-7}$。

{{ select(30) }}

• 正确
• 错误

31. （判断题，2 分）程序时间复杂度为 $O(n)$，其中 $n$ 为字符串长度。

{{ select(31) }}

• 正确
• 错误

32. （2 分）假设输入是长 $10^7$ 的、每个字符都是从 a 或 b 中均匀选取的字符串。进行下面哪一项改动后，代码的输出发生改变的概率最大？（ ）

{{ select(32) }}

• 把第 3 行改成 #define Ull unsigned
• 把 Mul 改成 $64$
• 把第 38 行改成 int res2=3;
• 把第 19 行改成 int n=strlen(a+1)+2;

33. （3 分）输入为 yummymmyummyisatyundou 时，输出为（ ）。

{{ select(33) }}

• $5$
• $4$
• $3$
• $2$

34. （4 分）有（ ）个含 $5$ 个小写字母的输入，使得输出为 $4$。

{{ select(34) }}

• $35126$
• $35152$
• $17576$
• 前三个选项都不对

三、完善程序（共 2 组，每空 3 分，共 30 分）

第 1 组：非空好子串统计

给定数列 $\{a_n\}$。数列 $\{b_m\}$ 是好的，当且仅当它能被划分成若干个子序列，满足每个子序列都构成一个有序的排列。求数列 $\{a_n\}$ 有多少个好的子串。

已知：$1\le n\le 10^5$，$1\le a_i\le n$。

提示：考虑转化原问题。倒序加入数字。加入一个数字时，考虑合并两个数。使用栈来维护。

试补全以下程序。

#include <iostream>
#include <stack>

using namespace std;

const int N = 100005;
int n, a[N];
int del[N];
long long ans;
stack<int> res, p[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    res.push(/* Blank 1 */);

    for (int i = n; i >= 1; --i) {
        if (/* Blank 2 */) {
            ++del[p[a[i] + 1].top()];
            p[a[i] + 1].pop();
        }
        if (/* Blank 3 */) {
            res.push(i);
            /* Blank 4 */;
        }
        while (del[res.top()]) res.pop();
        ans += /* Blank 5 */;
    }

    cout << ans << endl;
    return 0;
}

35. 第 /* Blank 1 */ 空应该填（ ）。

{{ select(35) }}

• n
• 1
• n + 1
• a[n]

36. 第 /* Blank 2 */ 空应该填（ ）。

{{ select(36) }}

• !p[a[i] + 1].empty()
• p[a[i] + 1].empty()
• !p[a[i]].empty()
• !p[a[i] - 1].empty()

37. 第 /* Blank 3 */ 空应该填（ ）。

{{ select(37) }}

• a[i] > 1
• i != n
• i != 1
• !p[a[i]].empty()

38. 第 /* Blank 4 */ 空应该填（ ）。

{{ select(38) }}

• --del[a[i]];
• p[a[i]].push(i);
• p[a[i]].pop();
• --del[a[i] + 1];

39. 第 /* Blank 5 */ 空应该填（ ）。

{{ select(39) }}

• res.size()
• res.top()
• max(0, res.size() - i + 1)
• res.top() - i

第 2 组：网格图上路径转合法括号序列

给定长度为 $2n$ 的仅包含 R（向右）和 D（向下）的字符串，表示一条从 $(0,0)$ 到 $(n,n)$ 的路径。

可以证明，合法路径一共有 $\binom{2n}{n}$ 种，长度为 $2n$ 的合法括号序列一共有 $\dfrac{\binom{2n}{n}}{n+1}$ 种。

上述信息意味着，存在构造函数 $f$，使得对于每一种合法路径，都可以构造出不同的元素对 $(x,y)$。其中 $x$ 为一个长度为 $2n$ 的合法括号序列，$y$ 是一个不超过 $n$ 的自然数。以下程序实现了一种构造函数 $f$。

括号序列是一个仅由 (、) 构成的序列。以下的括号序列是合法的：

1. () 是一个合法括号序列。
2. 如果 A 是一个合法括号序列，则 (A) 也是一个合法括号序列。
3. 如果 A 和 B 都是合法括号序列，则 AB 也是一个合法括号序列。

已知：$1\le n\le 100$，$s_i\in\{\mathrm R,\mathrm D\}$。

提示：可以通过计算字典序来形成对应关系。对于括号序列的计算字典序问题，可以考虑把括号序列转化，例如 (()(())) 可以转化为 $\{3,2,2,1\}$，然后用 $f_{i,j}$ 表示转化后的序列长为 $i$、结尾元素为 $j$ 的序列有多少，用 $s_{i,j}$ 表示 $f_{i,j}$ 的前缀和，同时利用组合数。

试补全程序。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 303, base = 1e4;

struct BigNum {
    int len, a[N];

    BigNum(const int& x = 0) {
        memset(a, 0, sizeof a);
        len = 0;
        if (x > 0) {
            len = 1;
            a[0] = x;
        }
    }

    BigNum operator + (const BigNum& b) {
        BigNum c;
        c.len = max(len, b.len) + 1;
        int x, y = 0;
        for (int i = 0; i < c.len; ++i) {
            x = a[i] + b.a[i] + y;
            c.a[i] = x % base;
            y = x / base;
        }
        while (c.len && c.a[c.len - 1] == 0) --c.len;
        return c;
    }

    BigNum operator - (const BigNum& b) {
        BigNum c;
        c.len = max(len, b.len);
        int x, y = 0;
        for (int i = 0; i < c.len; ++i) {
            x = a[i] - b.a[i] + y;
            if (x < 0) /* Blank 1 */;
            else c.a[i] = x, y = 0;
        }
        while (c.len && c.a[c.len - 1] == 0) --c.len;
        return c;
    }

    BigNum operator * (const int& b) {
        BigNum c;
        c.len = len + 1;
        int x, y = 0;
        for (int i = 0; i < c.len; ++i) {
            x = a[i] * b + y;
            c.a[i] = x % base;
            y = x / base;
        }
        while (c.len && c.a[c.len - 1] == 0) --c.len;
        return c;
    }

    pair<BigNum, int> div(const int& b) {
        BigNum c;
        c.len = len;
        int x, y = 0;
        for (int i = c.len - 1; i >= 0; --i) {
            x = y * base + a[i];
            c.a[i] = x / b;
            y = x % b;
        }
        while (c.len && c.a[c.len - 1] == 0) --c.len;
        return make_pair(c, y);
    }

    bool operator <= (const BigNum& b) {
        if (len < b.len) return 1;
        if (len > b.len) return 0;
        for (int i = len - 1; i >= 0; --i) {
            if (a[i] < b.a[i]) return 1;
            if (a[i] > b.a[i]) return 0;
        }
        return 1;
    }
};

BigNum c[N * 2][N], f[N][N], s[N][N];
int n, k;
string a;
int p[N];

int main() {
    cin >> n >> a;

    for (int i = 1; i <= n; ++i) {
        f[1][i] = 1;
        s[1][i] = s[1][i - 1] + 1;
    }

    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            f[i][j] = /* Blank 2 */;
            s[i][j] = s[i][j - 1] + f[i][j];
        }
    }

    c[0][0] = 1;
    for (int i = 1; i <= n << 1; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i && j <= n + 1; ++j)
            c[i][j] = /* Blank 3 */;
    }

    BigNum num = 0;
    int cnt = 0;

    for (int i = 0; i < n << 1; ++i) {
        if (a[i] == 'R') {
            ++cnt;
            num = num + /* Blank 4 */;
        }
    }

    pair<BigNum, int> res = num.div(n + 1);
    num = res.first;
    int r = res.second;

    for (int i = 1; i <= n; ++i) {
        p[i] = 1;
        for (int j = 1; j <= p[i - 1]; ++j) {
            BigNum value = /* Blank 5 */;
            if (value <= num) {
                num = num - value;
                ++p[i];
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = p[i]; j <= p[i - 1]; ++j)
            cout << ')';
        cout << '(';
    }

    for (int i = 1; i <= p[n]; ++i) cout << ')';
    cout << '\n' << r << '\n';

    return 0;
}

40. 第 /* Blank 1 */ 空应该填（ ）。

{{ select(40) }}

• c.a[i] = x + base, y = -1
• c.a[i] = x - base, y = 1
• c.a[i] = x + base * y, y = -y
• c.a[i] = x - base * y, y = -y

41. 第 /* Blank 2 */ 空应该填（ ）。

{{ select(41) }}

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

42. 第 /* Blank 3 */ 空应该填（ ）。

{{ select(42) }}

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

43. 第 /* Blank 4 */ 空应该填（ ）。

{{ select(43) }}

• c[2 * n - i + 1][n - cnt - 1]
• c[2 * n - i - 1][n - cnt + 1]
• c[2 * n - i][n - cnt]
• c[2 * n - i + 1][n - cnt - 1]

44. 第 /* Blank 5 */ 空应该填（ ）。

{{ select(44) }}

• f[n - i + 1][j]
• f[n - i - 1][j - 1]
• f[n - i + 1][j - 1]
• f[n - i - 1][j + 1]