试卷解析 · 理解每一步

洛谷 SCP-S 2025 第一轮模拟赛（提高级 C++）

CSPS-2025-R1-Mock-Luogu

试卷解析总览，可直接查看每题答案与解析。

一、单项选择题

第 1 题（单选题，2 分）

我国是人工智能大国，高度重视人工智能发展，积极推动互联网、大数据、人工智能和实体经济深度融合。下列关于人工智能领域的发展中，错误的说法是（）？

DeepSeek 和 Qwen 模型均为我国的开源大语言模型。

2025 世界人工智能大会（WAIC）于 7 月 26 日在上海开幕，展示了 AI 技术正突破屏幕界限，正在以各种形式深度融入物理世界。

我国人工智能上市企业超过 300 家，且人工智能的创新领域分布广泛，包括但不限于自动驾驶、智能机器人等。

我国正大力推进算力设施的建设，但算力设施主要分布在东部地区，尚未对西部产业发展产生影响。

正确答案D

解析详情

答案 D人工智能产业与算力布局

思路与推导

我国通过“东数西算”等工程推动东西部算力协同，西部的能源和资源优势已被用于建设数据中心、承接算力需求。
因此“算力设施主要在东部且尚未影响西部产业”的说法与实际布局不符。

第 2 题（单选题，2 分）

你使用 g++ -O2 -o myapp main.cpp 命令编译了一个程序，然后尝试用 gdb ./myapp 进行调试。在 GDB 中，当你试图使用 print 命令查看某个局部变量的值时，最有可能遇到的情况是？（）

程序立即崩溃，因为 GDB 无法处理优化过的代码。

变量值可以被正常显示，但执行速度会变慢。

GDB 会自动重新以 -g 选项编译该程序。

以上三者都错误。

正确答案D

解析详情

答案 DGDB 调试信息与编译优化

思路与推导

命令只有 `-O2` 而没有 `-g`，可执行文件缺少局部变量所需的调试信息，变量还可能被优化掉，`print` 常会提示找不到符号或 `<optimized out>`。
GDB 不会因此崩溃，也不会自动重新编译程序，所以 A、B、C 均不准确。

第 3 题（单选题，2 分）

对于一个长度为 $n$ 、每一项取值在 $[1,k]$ 之间的正整数序列，下列关于快速排序、计数排序、堆排序最坏时间复杂度的组合，哪一个全部正确？（）

\Theta(n\log n)

；

\Theta(k)

；

\Theta(n^2)

\Theta(n^2)

；

\Theta(n+k)

；

\Theta(n\log n)

\Theta(n\log n)

；

\Theta(n+k)

；

\Theta(n\log n)

\Theta(n^2)

；

\Theta(n\log n)

；

\Theta(n\log n)

正确答案B

解析详情

答案 B排序算法最坏时间复杂度

思路与推导

普通快速排序在划分极不均衡时最坏为 $\Theta(n^2)$ ；计数排序要扫描 $n$ 个元素并处理 $k$ 个计数桶，为 $\Theta(n+k)$ 。
堆排序建堆后进行 $n$ 次对数级调整，最坏为 $\Theta(n\log n)$ 。

第 4 题（单选题，2 分）

使用 Kruskal 算法对一张连通图 $G = (V, E)$ 求最小生成树，且要求时间复杂度不超过 $O(|E| \log |E|)$ 。通常情况下，下列哪个数据结构是必要的？（）

队列

链表

并查集

树状数组

正确答案C

解析详情

答案 CKruskal 算法与并查集

思路与推导

Kruskal 按边权排序后依次尝试加入边，必须快速判断两个端点是否已在同一连通块。
并查集支持近常数均摊复杂度的查询与合并，使总复杂度由排序主导为 $O(|E|\log |E|)$ 。

第 5 题（单选题，2 分）

对于以下 C++ 程序，假设 $n$ 为输入给定的正整数，不考虑整型变量溢出和编译器优化，则程序的时间复杂度是（）？

int i = 1;
while (i < n) {
    int j = n;
    while (j > 0)
        j /= 2;
    i = i * 2;
}

\Theta(n)

\Theta(n\log n)

\Theta(\log^2 n)

\Theta(\log n)

正确答案C

解析详情

答案 C嵌套循环复杂度

思路与推导

外层每次令 $i$ 翻倍，共执行 $\Theta(\log n)$ 次；每次外层循环中，内层令 $j$ 不断除以 2，也执行 $\Theta(\log n)$ 次。
两层次数相乘得到 $\Theta(\log^2 n)$ 。

第 6 题（单选题，2 分）

对于一张无自环的有向图 G，如果每对不同结点之间恰有一条有向边，则称 G 为竞赛图。对于一张有 5 个结点的竞赛图 G，下列哪一个数字可能是出度为 0 的结点的个数？（）

正确答案D

解析详情

答案 D竞赛图的出度

思路与推导

若两个结点的出度都为 0，它们之间那条有向边必使其中一个结点出度至少为 1，因此出度为 0 的结点至多一个。
让其余 4 个结点的边全部指向某个结点即可出现恰好一个，故 1 是可能值。

第 7 题（单选题，2 分）

给定长度为 n 的正整数数组，使用前缀和与双指针算法，可以在线性时间解决哪一类问题？（）

统计和为给定正整数 k 的子段数量

统计数组中逆序对个数

统计第 k 小的元素及其个数

将数组从小到大排序

正确答案A

解析详情

答案 A正整数数组的双指针

思路与推导

数组元素均为正数，右端点右移会使区间和增大，左端点右移会使区间和减小，两个指针都只单向移动。
配合前缀和或滑动窗口即可在线性时间统计和为 $k$ 的子段。

第 8 题（单选题，2 分）

给定一个后缀表达式 $3\ 4\ 2\ *\ 1\ 5\ -2\ 3\ ^\ ^/\ +$ （其中：^ 表示乘方，例如 $3^2=9$ ），则这个后缀表达式的值下取整的结果是？（）

65539

正确答案B

解析详情

答案 B后缀表达式求值

思路与推导

按栈计算得 $4\times2=8$ 、 $1-5=-4$ 、 $2^3=8$ ，随后 $(-4)^8=65536$ 。
最终值为 $3+8/65536$ ，介于 3 与 4 之间，下取整为 3。

第 9 题（单选题，2 分）

假设 a, b, m 都是正整数，下列关于模运算的计算式中，恒成立的是（）？

(a + b) \mod m = (a \mod m + b) \mod m

(a - b) \mod m = (a \mod m - b)

(a / b) \mod m = (a \mod m) / (b \mod m)

(a \times b) \mod m \neq ((a \mod m) \times (b \mod m)) \mod m

正确答案A

解析详情

答案 A模运算性质

思路与推导

将 $a$ 、 $b$ 分别写成模 $m$ 的商与余数，相加后的整倍数部分不影响最终余数，因此 $(a+b)\bmod m=((a\bmod m)+b)\bmod m$ 恒成立。
除法不能直接对余数相除，乘法则应是相等而不是不等。

第 10 题（单选题，2 分）

某递归函数的递推式为 $T(n)=3T(n/4)+\Theta(n^{1.2})$ ，则其渐进时间复杂度为（）。(在本题中，记 $\log_{4}3=0.79$ )

\Theta(n^{0.79})

\Theta(n^{1.2})

\Theta(n^{1.2}\log n)

\Theta(n^{1.79})

正确答案B

解析详情

答案 B主定理

思路与推导

递归项的临界指数为 $\log_4 3=0.79$ ，而合并代价为 $\Theta(n^{1.2})$ ，其指数更大。
并且 $3(n/4)^{1.2}<cn^{1.2}$ 对某个 $c<1$ 成立，故由主定理得 $T(n)=\Theta(n^{1.2})$ 。

第 11 题（单选题，2 分）

某校要从5名教师和6名学生中选派5人组成一个活动小组，要求：小组中至少包含1名教师和2名学生，且教师甲和学生乙不能同时入选。请问共有（）种不同的选派方案？

345

425

341

225

正确答案A

解析详情

答案 A组合计数与容斥

思路与推导

先忽略甲、乙冲突：教师人数可为 1、2、3，方案数为 $C(5,1)C(6,4)+C(5,2)C(6,3)+C(5,3)C(6,2)=425$ 。
同时选甲、乙且仍满足条件的方案有 $C(9,3)-C(4,3)=80$ ，故答案为 $425-80=345$ 。

第 12 题（单选题，2 分）

有一批正整数，均满足 $x \equiv 3 \pmod{6}$ ，现计划构造哈希函数 $h(x) = x \bmod m$ ，将元素放入 m 个桶内。若希望尽量覆盖全部的桶，以下哪一个 m 最合适？（）

120

正确答案C

解析详情

答案 C模同余与哈希桶覆盖

思路与推导

所有数可写成 $x=6t+3$ ，模 $m$ 后可到达的桶数由步长 6 与 $m$ 的最大公因数决定，共为 $m/\gcd(6,m)$ 个。
$m=97$ 与 6 互质，随着 $t$ 变化可以遍历全部 97 个余数桶，覆盖最充分。

第 13 题（单选题，2 分）

在下列关于 Manacher 算法的描述中，对于一个长度为 N 的字符串 S，哪一个说法是正确的？（）

该算法使用分治策略，并且平均时间复杂度为

O(N \log N)

。

该算法通过动态规划实现，可在

O(N^2)

时间求一个字符串的所有回文子串。

为了便于代码实现，通常需要在原字符串的每个字符之间和字符串首尾插入特殊字符。

为了降低时间复杂度，Manacher 算法需要预先使用 KMP 算法预处理 border 数组。这里，定义一个字符串 S 的 border 为 S 的一个非 S 本身的子串 T，满足 T 既是 S 的前缀，又是 S 的后缀。

正确答案C

解析详情

答案 CManacher 算法

思路与推导

Manacher 通常在相邻字符及首尾加入分隔符，把奇、偶长度回文统一为奇长度回文处理。
它利用已知回文区间的对称性在线性时间扩展，不依赖分治、普通动态规划或 KMP 的 border 数组。

第 14 题（单选题，2 分）

对于有向图 $G=(V,E)$ ，定义 $G_u$ 为将 $G$ 忽略方向得到的无向图。已知点集 $V=\{1,2,3,4,5,6\}$ ，边集 $E=\{(1,2),(1,6),(3,2),(3,4),(5,4),(5,6)\}$ ，其中 $(u,v)$ 表示 $u$ 连向 $v$ 的有向边。关于 $G$ 和 $G_u$ 的说法中，正确的是（）？

G

是强连通图，而

G_u

是一张点双连通的二分图；

G

不是强连通图，而

G_u

是二分图，但是并不是点双连通的图；

G

不是强连通图，而

G_u

也不是二分图；

G

不是强连通图，而

G_u

是一张点双连通的二分图；

正确答案D

解析详情

答案 D强连通、二分图与点双连通

思路与推导

有向边均由 $1,3,5$ 指向 $2,4,6$ ，显然无法从偶数结点回到奇数结点，所以 $G$ 不强连通。
忽略方向后恰为六边形环 $1-2-3-4-5-6-1$ ；偶环是二分图，且删去任一顶点后仍连通，因此点双连通。

第 15 题（单选题，2 分）

有 8 个布尔变量 $x_1,x_2,\ldots,x_8$ 满足下列异或方程（ $\oplus$ 表示异或）：

\begin{cases} x_1\oplus x_2\oplus x_3\oplus x_5\oplus x_6\oplus x_7\oplus x_8=1,\\ x_3\oplus x_6\oplus x_8=0,\\ x_2\oplus x_3\oplus x_4\oplus x_5\oplus x_6=1,\\ x_1\oplus x_2\oplus x_7=1,\\ x_2\oplus x_6=0. \end{cases}

满足全部方程的不同解的数量为多少？（）

正确答案B

解析详情

答案 B异或方程组与自由变量

思路与推导

由第 5、2、4 式依次得 $x_6=x_2$ 、 $x_3=x_2\oplus x_8$ 、 $x_1=1\oplus x_2\oplus x_7$ ；代回第 1 式得 $x_5=0$ ，再由第 3 式得 $x_4=1\oplus x_2\oplus x_8$ 。
$x_2,x_7,x_8$ 可独立取值，共有 $2^3=8$ 组解。

二、阅读程序（1）

#include <iostream>
using namespace std;

const int maxn = 10000000 + 7;

int n, f[maxn], g[maxn];
long long m, ans = 1;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> f[i];
    }
    for (int i = 1; i <= n; i++) {
        if (f[i] == 1)
            for (int j = i; j <= n; j += i)
                g[j] = 1;
        if (g[i] == 0)
            ans = ans * i % m;
    }
    cout << ans << endl;
    return 0;
}

第 16 题（判断题，1.5 分）

该程序输出一行一个不小于 0 而小于 m 的整数。（）

正确答案错误

解析详情

答案错误取模结果与初值边界

思路与推导

当 $m=1,n=1,f_1=1$ 时， $g_1$ 被置为 1，乘法语句不会执行，`ans` 保持初值 1。
程序输出 1，而“不小于 0 且小于 $m$ ”此时只能是 0，因此断言错误。

第 17 题（判断题，1.5 分）

删去读入循环末尾的右花括号 `}`，并删去紧随其后的第二个 `for (int i = 1; i <= n; i++) {`，程序仍然能正常运行，且输出结果不变。（）

正确答案正确

解析详情

答案正确循环融合与数据依赖

思路与推导

删除读入循环末尾的右花括号和第二个 `for` 声明后，处理逻辑被并入读入循环：每次读入 `f[i]` 后立即处理同一个 $i$ 。
处理 $i$ 时只依赖当前及更小下标产生的 `g`，不需要未来的 `f`，所以结果不变。

第 18 题（判断题，1.5 分）

将处理循环中的 `if (f[i] == 1)` 改为 `if (f[i] == 1 && g[i] == 0)`，程序仍然能正常运行，且输出结果不变。（）

正确答案正确

解析详情

答案正确倍数标记的冗余消除

思路与推导

若处理到 $i$ 时已有 $g[i]=1$ ，必存在更小的 $d\mid i$ 且 $f[d]=1$ ；所有 $i$ 的倍数也都是 $d$ 的倍数，早已被标记。
因此此时跳过 $i$ 的内层循环不会改变任何 `g[j]`，也不会改变乘积。

第 19 题（单选题，3 分）

该程序（对于 n）的最坏情况下的时间复杂度是（）?

\Theta(n)

\Theta(n \log \log n)

\Theta(n \log n)

\Theta(n^2)

正确答案C

解析详情

答案 C调和级数复杂度

思路与推导

最坏情况下所有 $f[i]=1$ ，第 $i$ 次内层循环访问约 $n/i$ 个倍数，总次数为 $\sum_{i=1}^{n}\lfloor n/i\rfloor$ 。
该和为 $\Theta(nH_n)=\Theta(n\log n)$ ，外层的 $\Theta(n)$ 不改变数量级。

第 20 题（单选题，3 分）

对于以下输入，程序输出结果除以 13 的余数是（）？

31 10000
0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

正确答案B

解析详情

答案 B倍数筛标记与模乘

思路与推导

$f_2=f_4=1$ ；处理 2 时所有偶数已被标记，处理 4 只重复标记，所以最终只把 $1,3,5,\ldots,31$ 乘入 `ans`。
奇数连乘逐步模 10000 的结果为 625，而 $625\bmod13=1$ 。

二、阅读程序（2）

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

const int N = 1010;

int n, m, mod;
long long ans, y[N], f[N], g[N], p[N], s[N];

long long qmi(long long a, int b, int p) {
    long long res = 1;
    while (b) {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

long long solve(int n, int k) {
    memset(y, 0, sizeof(y));
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    memset(p, 0, sizeof(p));
    memset(s, 0, sizeof(s));
    long long ans = 0;
    for (int i = 1; i <= k + 2; i++)
        y[i] = (y[i - 1] + qmi(i, k, mod)) % mod;
    f[0] = g[0] = 1;
    for (int i = 1; i <= k + 2; i++)
        f[i] = f[i - 1] * i % mod;
    for (int i = 1; i <= k + 2; i++)
        g[i] = -g[i - 1] * i % mod;
    p[0] = s[k + 3] = 1;
    for (int i = 1; i <= k + 2; i++)
        p[i] = p[i - 1] * (n - i) % mod;
    for (int i = k + 2; i >= 1; i--)
        s[i] = s[i + 1] * (n - i) % mod;
    for (int i = 1; i <= k + 2; i++) {
        long long t1 = p[i - 1] * s[i + 1] % mod;
        long long t2 = f[i - 1] * g[abs(k - i + 2)] % mod;
        (ans += y[i] * t1 % mod * qmi(t2, mod - 2, mod) % mod) %= mod;
        ans = (ans + mod) % mod;
    }
    return ans;
}

int main() {
    scanf("%d%d%d", &n, &m, &mod);
    long long res = 0;
    for (int i = 1; i <= n; i++) {
        res += (n - i + 1) * qmi(m, n - i, mod) % mod * solve(m, i);
        res %= mod;
    }
    printf("%lld", res);
    return 0;
}

第 21 题（判断题，1.5 分）

qmi 函数实现了快速幂算法。该函数对于任意不超过 $10^9+7$ 的非负整数 $b$ ，以及不超过 $10^9+7$ 的正整数 $a,p$ ，均能正确返回 $a^b$ 对 $p$ 取模的值。（）

正确答案错误

解析详情

答案错误快速幂的模 1 边界

思路与推导

循环确实是二进制快速幂，但当 $b=0,p=1$ 时循环不执行，函数直接返回初值 1。
正确的 $a^0\bmod1$ 应为 0，所以“对任意给定范围均正确”不成立。

第 22 题（判断题，1.5 分）

删除程序的第23到27行，程序仍然能正常运行，且输出结果不变。（）

正确答案正确

解析详情

答案正确数组覆盖写与初始化冗余

思路与推导

这些数组是全局数组，首次调用前已经全为 0；每次 `solve` 又会重设 `f[0],g[0],p[0],s[k+3]`，并覆盖本次实际读取的其余下标。
删除五次 `memset` 后没有旧值进入当前计算，输出不变。

第 23 题（判断题，1.5 分）

当输入的 m 为 1 时，输出总为 $\frac{n(n+1)}{2}$ 。（）

正确答案错误

解析详情

答案错误求和公式与模运算

思路与推导

当 $m=1$ 时，`solve(1,i)=1`，主循环未取模前的和确为 $\sum_{i=1}^{n}(n-i+1)=n(n+1)/2$ 。
但程序每轮执行 `res %= mod`，实际输出是该值对 `mod` 取模的结果，不保证等于原整数。

第 24 题（单选题，3 分）

这份程序的最坏时间复杂度是（）。

\Theta(n^2)

\Theta(n \log n)

\Theta(n^2 \log n)

\Theta(n^2 \log (n \times \mod))

正确答案D

解析详情

答案 D拉格朗日插值与快速幂复杂度

思路与推导

第 $i$ 次主循环调用 `solve(m,i)`，其中 $O(i)$ 次幂运算的指数分别为 $i$ 或 $mod-2$ ，耗时 $\Theta(i(\log i+\log mod))$ ；外层还各有一次 $O(\log n)$ 快速幂。
对 $i=1\ldots n$ 求和得到 $\Theta(n^2\log(n\times mod))$ 。

第 25 题（单选题，3 分）

对于以下的输入数据，输出结果为（）。

3 4 10331

1900

9500

820

1650

正确答案C

解析详情

答案 C按子段长度统计最小值总和

思路与推导

长度为 $l$ 的固定子段，在所有序列中的最小值总和为 $4^{3-l}\sum_{r=1}^{4}r^l$ ，且共有 $3-l+1$ 个位置。
$l=1,2,3$ 的贡献依次为 $3\times16\times10=480$ 、 $2\times4\times30=240$ 、 $1\times100=100$ ，合计 820。

第 26 题（单选题，4 分）

这份程序求得了（）的答案对 $\mod$ 取模的结果。

对于所有长度为

n

的，值域为

[1,m]

的整数序列

a

，计算

\sum_{i=1}^{n} \sum_{j=i}^{n} \max_{k=i}^{j} a_k

之和。

对于所有长度为

m

的，值域为

[1,n]

的整数序列

a

，计算

\sum_{i=1}^{m} \sum_{j=i}^{m} \max_{k=i}^{j} a_k

之和。

对于所有长度为

n

的，值域为

[1,m]

的整数序列

a

，计算

\sum_{i=1}^{n} \sum_{j=i}^{n} \min_{k=i}^{j} a_k

之和。

对于所有长度为

m

的，值域为

[1,n]

的整数序列

a

，计算

\sum_{i=1}^{m} \sum_{j=i}^{m} \min_{k=i}^{j} a_k

之和。

正确答案C

解析详情

答案 C幂和插值与子段最小值

思路与推导

`solve(m,i)` 用拉格朗日插值求 $\sum_{x=1}^{m}x^i$ ；对一个长度为 $i$ 的子段，所有取值方案的最小值总和正是 $\sum_{x=1}^{m}(m-x+1)^i=\sum_{x=1}^{m}x^i$ 。
乘上子段位置数 $n-i+1$ 和其余位置方案数 $m^{n-i}$ ，再对 $i$ 求和，得到选项 C。

二、阅读程序（3）

#include <iostream>
#include <string>

typedef long long ll;
const int alpha = 32;
const int maxn = 10000 + 5, maxk = 100 + 5;
const int maxv = 100000 + 5, maxs = 100000 + 5;
const ll mod = 1000000000 + 7;
using namespace std;

int n, k, v;
ll a[maxv];
string s;
int tr[maxs][alpha], dep[maxs], cnt[maxs];
int nxt[maxs], cnt1;
int id[maxs], cnt2;
ll c[maxn][maxk];
ll dp[maxn * 2][maxk], temp[maxk];
int siz[maxs];

void dfs(int ver) {
    int numb = 0, son = 0;
    for (int i = 0; i < alpha; i++) {
        if (tr[ver][i] != 0) {
            dfs(tr[ver][i]);
            ++numb;
            son = tr[ver][i];
        }
    }
    if (ver != 1 && numb == 1 && cnt[ver] == 0) {
        nxt[ver] = nxt[son];
    } else {
        nxt[ver] = ver;
        id[ver] = ++cnt2;
    }
}

void solve(int ver) {
    ll f = 1, g = 1;
    siz[ver] = cnt[ver];
    for (int i = 0; i <= siz[ver] && i <= k; i++) {
        dp[id[ver]][i] = f * c[siz[ver]][i] % mod;
        f = f * g % mod;
        g = g * a[dep[ver]] % mod;
    }
    for (int i = 0; i < alpha; i++)
        if (tr[ver][i] != 0)
            solve(nxt[tr[ver][i]]);
    for (int i = 0; i < alpha; i++)
        if (tr[ver][i] != 0) {
            int x = nxt[tr[ver][i]];
            for (int j = 0; j <= k && j <= siz[ver] + siz[x]; j++)
                temp[j] = 0;
            ll value1 = 1;
            for (int j1 = 0; j1 <= k && j1 <= siz[ver]; j1++) {
                ll value2 = dp[id[ver]][j1];
                for (int j2 = 0; j2 <= siz[x] && j1 + j2 <= k; j2++) {
                    temp[j1 + j2] = (temp[j1 + j2] +
                                      value2 * dp[id[x]][j2]) % mod;
                    value2 = value2 * value1 % mod;
                }
                value1 = value1 * a[dep[ver]] % mod;
            }
            siz[ver] += siz[x];
            for (int j = 0; j <= siz[ver] && j <= k; j++)
                dp[id[ver]][j] = temp[j];
        }
}

int main() {
    cin >> n >> k >> v;
    for (int i = 0; i <= v; i++)
        cin >> a[i];
    cnt1 = 1;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        int cur = 1, len = s.size();
        for (int j = 0; j < len; j++) {
            int ch = s[j] & 31;
            if (tr[cur][ch] == 0) {
                tr[cur][ch] = ++cnt1;
                dep[cnt1] = dep[cur] + 1;
            }
            cur = tr[cur][ch];
        }
        ++cnt[cur];
    }
    c[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= k && j <= i; j++)
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
    dfs(1);
    solve(1);
    cout << dp[id[1]][k] << endl;
    return 0;
}

第 27 题（判断题，1.5 分）

若输入的所有字符串长度均不小于2，且它们的第一个字符均相同，第二个字符两两不同，且 $a_{1}=1$ ，则输出的结果为 $\frac{n!}{k!(n-k)!}$ 。（）

正确答案正确

解析详情

答案正确Trie 上的组合动态规划

思路与推导

任意两串首字符相同而第二字符不同，所以它们的最长公共前缀长度都恰为 1；程序给每对被选字符串乘上 $a_1$ 。
因 $a_1=1$ ，每个大小为 $k$ 的子集权值均为 1，`dp[id[1]][k]` 就是 $C(n,k)=n!/(k!(n-k)!)$ 。

第 28 题（判断题，1.5 分）

将第5行的 const int alpha = 32; 改为 const int alpha = 26; 后，程序仍然能正常运行，且输出结果不变。（）

正确答案错误

解析详情

答案错误字符映射与数组下标

思路与推导

小写字母通过 `s[j] & 31` 映射到 $1\sim26$ ，其中字符 `z` 的下标为 26。
若第二维长度改为 26，合法下标只有 $0\sim25$ ，访问 `tr[*][26]` 会越界，结果无法保证。

第 29 题（判断题，2 分）

若将第18行的 ll dp[maxn * 2][maxk] 改为 ll dp[maxs][maxk]，第30行的if (ver != 1 && numb == 1 && cnt[ver] == 0) 改为 if (false)，程序仍然能正常运行，且输出结果不变。（）

正确答案正确

解析详情

答案正确Trie 路径压缩与 DP 等价性

思路与推导

取消压缩后，单儿子且非终止的结点也进入 `solve`；该结点有 `cnt=0`，自身只含 `dp[0]=1`，与唯一儿子合并时不会增加任何权值，因而只是原样传递儿子 DP。
`dp[maxs][maxk]` 又足以为所有至多 $L+1$ 个 Trie 结点分配状态，所以输出不变。

第 30 题（单选题，3 分）

假设 alpha 为常数，那么该程序的最坏时间复杂度是（）。

\Theta(v + Lk + nk^2)

\Theta(v + L + nk^2)

\Theta(v + Lk)

\Theta(v + L + nk)

正确答案D

解析详情

答案 D压缩 Trie 动态规划复杂度

思路与推导

读入权值、建 Trie 和路径压缩分别为 $\Theta(v)$ 、 $\Theta(L)$ 、 $\Theta(L)$ ；组合数表计算到 $n\times k$ 为 $\Theta(nk)$ 。
压缩后保留的终止/分叉结点为 $O(n)$ ，各子树合并的截断卷积按所含字符串数摊还为 $\Theta(nk)$ ，故总计 $\Theta(v+L+nk)$ 。

第 31 题（单选题，4 分）

记 $c$ 为满足在程序运行结束时满足恰有 26 个 $j \in \{0,1,\cdots,31\}$ 满足 $tr_{i,j} \neq 0$ 的 $i$ 的个数。若在本题条件下，记 $c$ 的最大值为 $c_1$ ，而在满足本题条件且 $L \leq 10^4$ 时，记此时 $c$ 的最大值为 $c_2$ 。设 $c_0 = c_1 - c_2$ ，则 $c_0$ 除以 17 的余数是（）。

0

正确答案B

解析详情

答案 B26 叉 Trie 的极值构造

思路与推导

每增加一个拥有 26 个儿子的结点，最少使叶子数增加 25；由 $n\le10000$ 得 $c_1=\lfloor(10000-1)/25\rfloor=399$ ，且平衡构造的总长度不超过 $10^5$ 。
$L\le10^4$ 时按最浅叶子优先展开：根贡献 26，继续展开 26 个深度 1 叶子后总长度为 1352；再展开深度 2 叶子每次增加 76，故还能展开 $\lfloor(10000-1352)/76\rfloor=113$ 个， $c_2=27+113=140$ 。
所以 $c_0=399-140=259$ ，而 $259\bmod17=4$ 。

第 32 题（单选题，3 分）

对于以下的输入数据，程序输出的结果是（）。

10 3 12

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

ak firstround goodluck havefun luogu luogudevteam luotianyi rpplusplus scp scps

3248

3617

3816

4068

正确答案C

解析详情

答案 C压缩 Trie 上的树形背包

思路与推导

建 Trie 并压缩单链后，根的有效儿子按字符为 `a,f,g,h,l,r,s`，对应子树字符串数为 $1,1,1,1,3,1,2$ 。
依次合并这些子树时，根状态 `dp[3]` 变为 $0,0,27,108,1170,1782,3816$ ；其中跨子树选择按当前结点深度的 $a[dep]$ 累乘。
最终 `dp[id[1]][3]=3816`。

三、完善程序（1）

（1）（树的重心）给定一颗树，树中包含 $n$ 个结点（编号 $1 \sim n$ ）和 $n-1$ 条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。上述参数满足 $1 \leq n \leq 2 \times 10^5$ 。试补全程序。

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

const int N = 2e5 + 10;

int n, pos, maxx_part = 0x3f3f3f3f, siz[N], v[N];
int h[N], e[N], ne[N], idx;

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    ①;
}

void dfs(int x) {
    v[x] = 1;
    ②;
    int max_part = 0;
    for (int i = h[x]; ~i; i = ne[i]) {
        int j = e[i];
        if (v[j]) continue;
        dfs(j);
        siz[x] += siz[j];
        max_part = max(max_part, siz[j]);
    }
    ③;
    maxx_part = min(maxx_part, max_part);
}

int main() {
    ④;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs(1);
    cout << ⑤;
    return 0;
}

第 33 题（单选题，3 分）

①处应填（）

h[a] = ne[idx + 1]

h[a] = e[idx + 1]

h[a] = ++idx

h[a] = idx++

正确答案D

解析详情

答案 D链式前向星加边

思路与推导

新边编号为当前 `idx`，`e[idx]=b` 保存终点，`ne[idx]=h[a]` 接到原链表头之后，应令 `h[a]=idx` 再把 `idx` 加 1。
表达式 `h[a] = idx++` 正好完成这两个动作。

第 34 题（单选题，3 分）

②处应填（）

siz[x] = -1

siz[x] = 0

siz[x] = 1

siz[x] = 0x3f3f3f3f

正确答案C

解析详情

答案 CDFS 子树大小

思路与推导

`siz[x]` 表示以 $x$ 为根的子树结点数，进入 `dfs(x)` 时必须先计入结点 $x$ 本身，因此初始化为 1。
随后再把每个未访问儿子的 `siz[j]` 累加进去。

第 35 题（单选题，3 分）

③处应填（）

max_part = max(max_part, n - siz[x])

maxx_part = max(maxx_part, n - siz[x])

max_part = max(max_part, siz[x])

maxx_part = max(maxx_part, siz[x])

正确答案A

解析详情

答案 A树的重心判定

思路与推导

删除 $x$ 后，儿子方向连通块大小已由 `siz[j]` 更新到 `max_part`；父亲方向剩余的连通块大小为 $n-siz[x]$ 。
所以还需执行 `max_part = max(max_part, n - siz[x])`，才能得到删除 $x$ 后最大连通块。

第 36 题（单选题，3 分）

④处应填（）。

memset(h, 0, sizeof(h))

memset(h, 63, sizeof(h))

memset(h, -63, sizeof(h))

memset(h, 255, sizeof(h))

正确答案D

解析详情

答案 D链式前向星空指针初始化

思路与推导

遍历条件 `~i` 要在 $i=-1$ 时停止，因此每个 `h[a]` 初始值必须为 -1。
`memset(h,255,sizeof(h))` 把每个字节写成 `0xFF`，在常用二进制补码表示下整数值即为 -1。

第 37 题（单选题，3 分）

⑤处应填（）。

siz[maxx_part == 2e9 ? 0 : maxx_part]

maxx_part

maxx_part + 1

2 * maxx_part - 1

正确答案B

解析详情

答案 B重心目标值输出

思路与推导

对每个结点计算删除后的最大连通块大小 `max_part`，再用 `maxx_part=min(maxx_part,max_part)` 维护全局最小值。
题目要求输出的正是这个最小的最大连通块大小，因此输出 `maxx_part`。

三、完善程序（2）

（2）（矩形覆盖问题）在平面直角坐标系上有 $n$ 个矩形，矩形的每条边与坐标系的横轴平行或垂直。对于第 $i$ 个矩形，矩形左下角的顶点坐标为 $(s_x, s_y)$ ，右上角的顶点坐标为 $(e_x, e_y)$ 。每个矩形要么严格包含另一个矩形，要么完全不相交。矩形的边界不会相交、顶点或边也不会重合。要求，对于每个矩形，分别求出包含它的矩形中最小的矩形。如果没有被覆盖，则输出 $\emptyset$ 。上述参数满足 $1 \leq n \leq 2 \times 10^5$ ， $1 \leq s_x, s_y, e_x, e_y \leq 10^9$ ，你需要设计一个时间复杂度不超过 $\Theta(n \log n)$ 的程序。试补全程序。

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

struct rectangle {
    ll sx, sy, ex, ey;
};

struct line {
    ll x, sy, ey, id;
    friend bool operator < (const line &lhs, const line &rhs) {
        return ①;
    }
};

struct segmentTree {
    vector<int> tree, lazy;

    static int ls(int u) { return u << 1; }
    static int rs(int u) { return u << 1 | 1; }
    segmentTree(int N): tree(N * 4 + 1, 0), lazy(N * 4 + 1, -1) {}

    void pushdown(int p) {
        if (~lazy[p]) {
            tree[ls(p)] = tree[rs(p)] = lazy[p];
            lazy[ls(p)] = lazy[rs(p)] = lazy[p];
            lazy[p] = -1;
        }
    }

    void update(int p, int l, int r, int ql, int qr, int k) {
        if (l >= ql && r <= qr) {
            tree[p] = lazy[p] = k;
            return;
        }
        pushdown(p); int mid = (l + r) >> 1;
        if (②) update(ls(p), l, mid, ql, qr, k);
        if (qr > mid) update(rs(p), mid + 1, r, ql, qr, k);
    }

    int query(int p, int l, int r, int x) {
        if (l == r) return tree[p];
        pushdown(p); int mid = (l + r) >> 1;
        if (mid >= x) return query(ls(p), l, mid, x);
        else return query(rs(p), mid + 1, r, x);
    }
};

template<class T> struct discretize {
    vector<T> data;
    discretize(): data() {}

    void insert(const T &x) { data.push_back(x); }

    void build() {
        sort(data.begin(), data.end());
        auto endp = unique(data.begin(), data.end());
        data.erase(endp, data.end());
    }

    size_t size() const { return data.size(); }

    int operator[](const T &x) {
        return ③;
    }
};

int main() {
    int n; cin >> n;
    vector<rectangle> P(n);
    for (int i = 0; i < n; i++)
        cin >> P[i].sx >> P[i].sy >> P[i].ex >> P[i].ey;
    discretize<ll> discx, discy;
    for (int i = 0; i < n; i++) {
        discx.insert(P[i].sx);
        discx.insert(P[i].ex);
        discy.insert(P[i].sy);
        discy.insert(P[i].ey);
    }
    discx.build(); discy.build();
    for (int i = 0; i < n; i++) {
        P[i].sx = discx[P[i].sx] + 1;
        P[i].ex = discx[P[i].ex] + 1;
        P[i].sy = discy[P[i].sy] + 1;
        P[i].ey = discy[P[i].ey] + 1;
    }
    vector<line> L; int cnt = 0;
    for (int i = 0; i < n; i++) {
        L.push_back({P[i].sx, P[i].sy, P[i].ey, ++cnt});
        L.push_back({④});
    }
    sort(L.begin(), L.end());
    int N = discx.size();
    segmentTree S(N);
    vector<int> fa(n + 1, -1);
    for (int i = 0; i < L.size(); i++) {
        int c = S.query(1, 1, N, L[i].sy);
        if (L[i].id < 0)
            S.update(1, 1, N, L[i].sy, L[i].ey, fa[-L[i].id]);
        else {
            fa[L[i].id] = c;
            ⑤
        }
    }
    for (int i = 1; i <= cnt; ++i)
        cout << fa[i] << " \n"[i == cnt];
    return 0;
}

第 38 题（单选题，3 分）

①处应填（）

lhs.sy < rhs.sy || lhs.ey < rhs.ey

lhs.sy == rhs.sy ? lhs.id < rhs.id : lhs.sy < rhs.sy

lhs.ey == rhs.ey ? lhs.id < rhs.id : lhs.ey < rhs.ey

lhs.x == rhs.x ? lhs.id < rhs.id : lhs.x < rhs.x

正确答案D

解析详情

答案 D扫描线事件排序

思路与推导

每条竖边事件首先必须按横坐标 `x` 从小到大处理；同一横坐标时再按 `id` 排序，使负编号的离开事件先于正编号的进入事件。
因此比较式为 `lhs.x == rhs.x ? lhs.id < rhs.id : lhs.x < rhs.x`。

第 39 题（单选题，3 分）

②处应填（）

ql < mid

ql <= mid

ql >= mid

ql == mid

正确答案B

解析详情

答案 B线段树区间修改

思路与推导

当前结点左儿子覆盖 $[l,mid]$ ；待修改区间 $[ql,qr]$ 与它相交的条件是 $ql\le mid$ 。
配合已有的 `qr > mid` 判断即可分别递归到所有相交儿子。

第 40 题（单选题，3 分）

③处应填（）

lower_bound(data.begin(), data.end(), x) - data.begin()

upper_bound(data.begin(), data.end(), x) - data.begin()

find(data.begin(), data.end(), x) - data.begin()

distance(data.end(), upper_bound(data.begin(), data.end(), x))

正确答案A

解析详情

答案 A坐标离散化

思路与推导

`build` 后 `data` 已排序去重，且传入的 $x$ 一定来自已插入坐标。
`lower_bound(data.begin(),data.end(),x)-data.begin()` 返回 $x$ 的零基排名，主程序再加 1 转成线段树的一基下标。

第 41 题（单选题，3 分）

④处应填（）

P[i].sx, P[i].sy, P[i].ey, cnt

P[i].sx, P[i].sy, P[i].ey, -cnt

P[i].ex, P[i].sy, P[i].ey, cnt

P[i].ex, P[i].sy, P[i].ey, -cnt

正确答案D

解析详情

答案 D矩形扫描线事件编码

思路与推导

左边界 $sx$ 使用正编号表示矩形进入，右边界必须在 $ex$ 处使用相反的负编号表示矩形离开。
纵向覆盖范围在两次事件中都保持为 $[sy,ey]$ ，故应填 `P[i].ex, P[i].sy, P[i].ey, -cnt`。

第 42 题（单选题，3 分）

⑤处应填（）

fa[i] = S.query(1, 1, N, c)

fa[i] = S.query(1, 1, N, L[i].id)

S.update(1, 1, N, L[i].sy, L[i].ey, L[i].id)

S.update(1, 1, N, L[i].sx, L[i].ex, L[i].id)

正确答案C

解析详情

答案 C扫描线与区间覆盖线段树

思路与推导

正编号事件表示进入矩形：先查询 `sy` 处当前最内层覆盖编号并记为 `fa[id]`，再把整个 $[sy,ey]$ 区间赋成当前矩形编号。
因此应调用 `S.update(1,1,N,L[i].sy,L[i].ey,L[i].id)`；离开时程序再用 `fa[-id]` 恢复父矩形。