GESP 客观题评测系统

2019 CCF CSP-S 第一轮（提高级 C++）

CSPS-2019-R1

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

一、单项选择题

第 1 题（单选题，2 分）

若有定义：int a=7; float x=2.5, y=4.7; 则表达式 $x + a\%3 \times (\text{int})(x + y) \% 2$ 的值是：（）

0.000000

2.750000

3.500000

2.500000

正确答案C

解析详情

【答案】C

【考点】C++ 类型转换与算术运算

【解析】先算强制类型转换 `(int)(x + y) = (int)(2.5 + 4.7) = (int)7.2 = 7`。取模运算 `a % 3 = 7 % 3 = 1`。乘除和取模同级、从左到右，故 `1 × 7 % 2 = 7 % 2 = 1`。最终加上 x：`2.5 + 1 = 3.5`。

【易错点】强制类型转换的优先级高于乘除取模，且 % 2 只对前面的整数运算生效。

第 2 题（单选题，2 分）

下列属于图像文件格式的有（）

MPEG

WMV

AVI

JPEG

正确答案D

解析详情

【答案】D

【考点】常见文件格式

【解析】JPEG 是一种广泛使用的静态图像压缩格式。而 MPEG、WMV 和 AVI 都是常见的视频编码或视频容器格式，不属于纯图像文件格式。

【易错点】视频本质是连续的图像帧，但视频格式与单一图像格式不同。

第 3 题（单选题，2 分）

二进制数 11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑或运算的结果是（）。

11 1111 1111 1101

11 1111 1101 1111

11 1111 1111 1111

10 1111 1111 1111

正确答案C

解析详情

【答案】C

【考点】二进制逻辑或

【解析】逻辑或运算（|）规则为：只要对应位中至少有一个 1，结果位就是 1。将 11 1011 1001 0111 和 01 0110 1110 1011 逐位对齐，每一位上都至少有一个 1，故结果为 11 1111 1111 1111。

【易错点】混淆逻辑或与二进制加法，逻辑或不产生进位。

第 4 题（单选题，2 分）

编译器的功能是（）

将低级语言翻译成高级语言

将源程序重新组合

将一种编程语言翻译成自然语言

将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言）

正确答案D

解析详情

【答案】D

【考点】编译器功能

【解析】编译器的核心功能是将一种高级语言写成的源程序翻译为等价的低级语言（如汇编语言或机器语言）目标程序。

【易错点】编译器不进行自然语言翻译，也不仅仅是重新组合源程序。

第 5 题（单选题，2 分）

设变量 x 为 float 型且已赋值，则以下语句中能将 x 中的数值保留到小数点后两位，并将第三位四舍五入的是（）

x=(x*100+0.5)/100.0;

x=(x/100+0.5)*100.0;

x=x*100+0.5/100.0;

x=(int)(x*100+0.5)/100.0;

正确答案D

解析详情

【答案】D

【考点】浮点数四舍五入与强制类型转换

【解析】为实现保留两位小数并对第三位四舍五入，先乘 100 移位：`x * 100`。加 0.5 实现四舍五入进位，然后强制转 `int` 截断小数部分。最后除以 100.0 转回浮点数，即 `(int)(x * 100 + 0.5) / 100.0`。

【易错点】如果不强制转为 `int`，加 0.5 只是让数字变大，无法截断后面的小数部分。

第 6 题（单选题，2 分）

由数字 1, 1, 2, 4, 8, 8 所组成的不同的 4 位数的个数是（）。

104

102

100

正确答案C

解析详情

【答案】C

【考点】含重复元素的排列计数

【解析】情况1：四位均不同(1,2,4,8)，有 4! = 24 种。情况2：含一对相同数字(两个1或两个8)，C(2,1) × C(3,2) × 4!/2! = 2 × 3 × 12 = 72 种。情况3：含两对相同数字(两个1和两个8)，4!/(2!×2!) = 6 种。总和为 24 + 72 + 6 = 102 种。

【易错点】相同数字在排列中不可区分，需除以其个数的阶乘来去重。

第 7 题（单选题，2 分）

排序的算法很多，若按排序的稳定性和不稳定性分类，则（）是不稳定排序。

快速排序

直接插入排序

归并排序

冒泡排序

正确答案A

解析详情

【答案】A

【考点】排序算法的稳定性

【解析】快速排序在划分（partition）过程中，会远距离交换元素，可能打乱相等元素的相对顺序，因此是不稳定的。直接插入、归并和冒泡都可以保证相等元素的相对顺序不变。

【易错点】混淆稳定性与算法时间复杂度的优劣，稳定性专指相等元素的相对次序。

第 8 题（单选题，2 分）

G 是一个非连通无向图（没有重边和自环），共有 28 条边，则该图至少有 ___ 个顶点。

正确答案A

解析详情

【答案】A

【考点】简单图的极值边数

【解析】要求无向图非连通，边数最多的情况是 n-1 个顶点构成完全图，1个顶点孤立。边数为 C(n-1, 2)。当 n=8 时，最大边数 C(7,2)=21 < 28；当 n=9 时，最大边数 C(8,2)=28。故至少需要 9 个顶点。

【易错点】错误使用连通图的边数公式 C(n,2)，未考虑图必须非连通的限制。

第 9 题（单选题，2 分）

一些数字可以颠倒过来看，例如 0、1、8 颠倒过来还是本身，6 颠倒过来是 9.9 颠倒过来看还是 6，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如 106 颠倒过来是 901。假设某个城市的车牌只有 5 位数字，每一位都可以取 0 到 9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的 5 位数能被 3 整除？（）

正确答案B

解析详情

【答案】B

【考点】组合计数与整除判定

【解析】车牌颠倒后不变，首尾必须对应，可选 00,11,88,69,96（注意6和9互为颠倒），共5对。次外层同样5对。中间位只能是颠倒不变的 0,1,8。因为模 3 余数分别为 0,1,2，对于任意确定的前两对外层，必有唯一一个中间位使 5 位数和能被 3 整除。故组合数为 5 × 5 × 1 = 25 种。

【易错点】忘记考虑 6 和 9 颠倒后不仅位置互换而且数值互换的特性。

第 10 题（单选题，2 分）

一次期末考试，某班有 15 人数学得满分，有 12 人语文得满分，并且有 4 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（）。

正确答案B

解析详情

【答案】B

【考点】容斥原理

【解析】根据容斥原理公式：至少一门满分人数 = 数学满分人数 + 语文满分人数 - 两门均满分人数。计算得 15 + 12 - 4 = 23 人。

【易错点】直接相加导致两门都满分的同学被重复计算。

第 11 题（单选题，2 分）

设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（）。

n^{2}

n \log n

2n - 1

2n

正确答案C

解析详情

【答案】C

【考点】有序数组归并的比较下界

【解析】最坏情况下，A 和 B 元素大小交错（如 A=[1,3,5], B=[2,4,6]），必须比较到其中一个数组只剩最后一个元素才结束。此时前 2n-1 个元素都需要通过比较得出，故至少需比较 2n-1 次。

【易错点】最后剩余的一个元素可以直接追加，不需要比较，所以不是 2n 次。

第 12 题（单选题，2 分）

以下哪个结构可以用来存储图（）

二叉树

队列

邻接矩阵

栈

正确答案C

解析详情

【答案】C

【考点】图的存储结构

【解析】图的常用存储结构有邻接矩阵和邻接表。邻接矩阵使用二维数组存储顶点之间的边关系。二叉树、队列、栈等并不是用来直接表示图结构的。

【易错点】队列和栈多用于图的广度/深度遍历过程，而非存储图的拓扑结构。

第 13 题（单选题，2 分）

以下哪些算法不属于贪心算法？（）

Dijkstra算法

Prim算法

Kruskal算法

Floyd算法

正确答案D

解析详情

【答案】D

【考点】贪心算法与动态规划

【解析】Dijkstra、Prim 和 Kruskal 均在每一步做出局部最优选择（选最短边/最近点），属于贪心。Floyd 算法通过中间顶点 k 进行状态转移 `d[i][j] = min(d[i][j], d[i][k] + d[k][j])`，本质是动态规划。

【易错点】只要有求极值操作不一定就是贪心，Floyd 是经典的全局状态转移。

第 14 题（单选题，2 分）

有一个等比数列，共有奇数项，其中第一项和最后一项分别是 2 和 118098，中间一项是 486，请问以下哪个数是可能的公比？（）

正确答案D

解析详情

【答案】D

【考点】等比数列

【解析】首项 a1=2，末项 118098，中项 486。中项是第 k+1 项，有 a1 * q^k = 486，推导 2 * q^k = 486，故 q^k = 243。因为 3^5 = 243，所以可能的公比为 3。末项 2 * 3^10 = 118098 验证成立。

【易错点】错误地将中项到首尾的距离计算为不同的项数差。

第 15 题（单选题，2 分）

有正实数构成的数字三角形排列形式如图所示。第一行的数为 $a_{1,1}$ ; 第二行的数为左到右依次为 $a_{2,1}, a_{2,2}$ ，第 n 行的数为 $a_{n,1}, a_{n,2}, \ldots, a_{n,n}$ 。从 $a_{1,1}$ 开始，每一行的数 $a_{i,j}$ 只有两条边可以分别通向下一行的两个数 $a_{i+1,j}$ 和 $a_{i+1,j+1}$ 。用动态规划算法找出一条从 $a_{1,1}$ 向下通到 $a_{n,1}, a_{n,2}, \ldots, a_{n,n}$ 中某个数的路径，使得该路径上的数之和最大。

令 C[i][j] 是从 $a_{1,1}$ 到 $a_{i,j}$ 的路径上的数的最大和，并且 C[i][0]=C[0][j]=0，则C[i][j]=（）。

\max\{C[i-1][j-1],C[i-1][j]\}+a_{i,j}

\max\{C[i-1][j-1],C[i-1][j]\}+1

C[i-1][j-1]+C[i-1][j]

\max\{C[i][j-1],C[i-1][j]\}+a_{i,j}

正确答案A

解析详情

【答案】A

【考点】数字三角形动态规划

【解析】节点 a[i,j] 的上方只能来自左上 a[i-1,j-1] 或正上 a[i-1,j]。状态转移方程应取两前驱的最大值加上自身权重，即 C[i][j] = max(C[i-1][j-1], C[i-1][j]) + a[i,j]。

【易错点】边界混淆，错误地将同一行的元素 C[i][j-1] 当作前驱状态。

二、阅读程序（1）

#include <cstdio>
using namespace std;
int n;
int a[100];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

第 16 题（判断题，1 分）

第16行输出ans时，ans的值一定大于i。（）

正确答案错误

解析详情

【答案】错误

【考点】循环变量与边界条件

【解析】在严格单调递增数组中，`i` 递增，`ans` 每轮只被更新为 `i`，内层 `while` 条件 `a[i] >= a[ans+1]` 始终不成立，`ans` 保持为 `i`。因此输出 `ans` 时可以等于 `i`，不一定大于。

【易错点】认为 `while` 循环必定至少执行一次自增。

第 17 题（判断题，1 分）

程序输出的 ans 小于等于 n。（）

正确答案正确

解析详情

【答案】正确

【考点】循环不变量

【解析】`ans` 的初始值为 1，赋值来源于 `i` (其中 `i <= n`)。`while` 循环的严格条件是 `ans < n` 才能自增。因此 `ans` 的最大值不会超过 `n`。

【易错点】没有看到 `while` 中有 `ans < n` 的保护条件，误以为可能越界。

第 18 题（判断题，1.5 分）

若将第 12 行的 “<” 改为 “!=”，程序输出的结果不会改变。（）

正确答案正确

解析详情

【答案】正确

【考点】程序等价性与循环不变量

【解析】原条件 `a[i] < a[i-1]` 变更为 `a[i] != a[i-1]` 后，当 `a[i] > a[i-1]` 时 `ans` 会被重置为 `i`。但因为此时 `a[i] >= a[ans+1]` 会重新从 `i` 向右扩展，这与上一轮已经扩展到的边界结果相同，输出不受实质影响。

【易错点】误认为额外的 `ans = i` 重置会导致答案变小。

第 19 题（判断题，1.5 分）

当程序执行到第 16 行时，若 $ans - i > 2$ ，则 $a[i + 1] \leq a[i]$ 。（）

正确答案正确

解析详情

【答案】正确

【考点】双指针扫描不变量

【解析】如果 `ans - i > 2`，说明 `ans` 至少扩展到了 `i+3` 或继承自更早。若是本轮扩展，必定通过了 `a[i] >= a[i+1]` 的判断；若是继承前几轮，说明之前有 `a[k] >= a[i]` 且 `a[k] >= a[i+1]`。两者均隐含 `a[i+1] <= a[i]` 的性质。

【易错点】忽视双指针扫描过程保留的单调性特征。

第 20 题（单选题，3 分）

若输入的a数组是一个严格单调递增的数列，此程序的时间复杂度是（）。

O(n)

O(\log n)

O(n^{2})

O(n \log n)

正确答案A

解析详情

【答案】A

【考点】双指针时间复杂度

【解析】当数组严格递增，`a[i] < a[i-1]` 不成立，`ans` 也不满足 `a[i] >= a[ans+1]`。内层 `while` 根本不执行自增。外层循环执行 n 次，整体操作次数为线性量级 O(n)。

【易错点】看到两层循环嵌套就盲目判断为 O(n^2)。

第 21 题（单选题，4 分）

最坏情况下，此程序的时间复杂度是（）。

O(\log n)

O(n^{2})

O(n \log n)

O(n)

正确答案B

解析详情

【答案】B

【考点】最坏时间复杂度

【解析】当数组严格递减时，每次 `a[i] < a[i-1]` 成立，`ans = i`。内层 `while` 中 `a[i] >= a[ans+1]` 持续成立，`ans` 从 `i` 一直增加到 `n`。执行次数为 sum(n-i) = O(n^2)。

【易错点】双指针有重置机制时，内层循环指针可能反复回退扫描。

二、阅读程序（2）

#include <iostream>
using namespace std;

const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];
int getRoot(int v) {
    if (fa[v] == v) return v;
    return getRoot(fa[v]);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        fa[i] = i;
        cnt[i] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, x, y;
        cin >> a >> b;
        x = getRoot(a);
        y = getRoot(b);
        ans += cnt[x] * cnt[y];
        fa[x] = y;
        cnt[y] += cnt[x];
    }
    cout << ans << endl;
    return 0;
}

第 22 题（判断题，1 分）

输入的 a 和 b 值应在 $[0, n-1]$ 的范围内。（）

正确答案正确

解析详情

【答案】正确

【考点】数组下标范围

【解析】输入变量 `a` 和 `b` 直接用于调用 `getRoot(a)` 和 `getRoot(b)`，并作为数组 `fa` 的下标。由于循环初始化只处理了 0 到 n-1，故 `a` 和 `b` 必须在 [0, n-1] 范围内以防越界。

【易错点】忽略并查集有效元素范围由 `n` 限制，而非数组声明时的最大容量 `maxn`。

第 23 题（判断题，1 分）

第16行改成“fa[i] = 0;”，不影响程序运行结果。（）

正确答案错误

解析详情

【答案】错误

【考点】并查集初始化

【解析】并查集必须初始化每个节点的父节点为自身（`fa[i] = i`），代表每个节点各自为一个连通分量。如果统一改为 `fa[i] = 0`，则所有节点初始即在同一个以 0 为根的连通分量中，导致无法正确合并和计数。

【易错点】误以为初始化为 0 可以代表空集或未连接状态。

第 24 题（判断题，1.5 分）

若输入的a和b值均在[0, n-1]的范围内，则对于任意0 ≤ i < n，都有0 ≤ fa[i] < n。（）

正确答案正确

解析详情

【答案】正确

【考点】并查集父指针范围

【解析】初始时 `fa[i] = i` 在 [0, n-1]。后续操作仅有 `fa[x] = y`，而 `x` 和 `y` 都是通过合法输入经过 `getRoot` 得到的根节点下标，这些下标最初在 [0, n-1]，所以任何父指针均在此范围内。

【易错点】未追踪 `getRoot` 的返回值，误以为合并过程中会产生超出初始编号的值。

第 25 题（判断题，1.5 分）

若输入的a和b值均在[0, n-1]的范围内，则对于任意0 ≤ i < n，都有1 ≤ cnt[i] ≤ n。（）

选择题

正确答案错误

解析详情

【答案】错误

【考点】并查集合并与集合大小

【解析】在进行合并前，代码未检查根节点是否相同（无 `if (x != y)`）。如果对同一连通分量内的点重复执行，`cnt[y] += cnt[x]` 会把相同的计数反复累加，使得 `cnt` 超过总顶点数 n。

【易错点】误以为并查集自然不会对相同连通分量累加计数。

第 26 题（单选题，4 分）

当 n 等于 50 时，若 a、b 的值都在 $[0,49]$ 的范围内，且在第 25 行时 x 总是不等于 y，那么输出为（）。

1250

1276

1225

1176

正确答案C

解析详情

【答案】C

【考点】并查集合并计数

【解析】每次合并两不同连通分量，增加的贡献恰好是 `cnt[x] * cnt[y]`。最终 50 个点全部连通，等价于计算所有 50 个点之间两两连通对数，即 C(50,2) = 50 * 49 / 2 = 1225。

【易错点】试图模拟每一次 49 次循环的具体增量，而忽略了问题等价于完全图边数。

第 27 题（单选题，4 分）

此程序的时间复杂度是（）。

O(n^{2})

O(\log n)

O(n)

O(n \log n)

正确答案A

解析详情

【答案】A

【考点】并查集时间复杂度

【解析】该并查集实现没有路径压缩（`getRoot` 中只有 `while (fa[x] != x) x = fa[x];`），也没有按秩合并。最坏情况下树退化为链表，每次查询 `O(n)`。总执行 50 次，最坏复杂度 O(n^2)。

【易错点】习惯性认为并查集复杂度都是 O(n log n) 甚至反阿克曼函数。

二、阅读程序（3）

3. 本题 t 是 s 的子序列的意思是：从 s 中删去若干个字符，可以得到 t；特别的，如果 s = t，那么 t 也是 s 的子序列；空串是任何串的子序列。例如 “acd” 是 “abcde” 的子序列，“acd” 是 “acd” 的子序列，但 “adc” 不是 “abcde” 的子序列。

s[x..y] 表示 s[x] ... s[y] 共 y - x + 1 个字符构成的字符串，若 x > y 则 s[x..y] 是空串。t[x..y] 同理。

#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];
7
int main() {
cin >> s >> t;
int slen = s.length(), tlen = t.length();
for (int i = 0, j = 0; i < slen; ++i) {
if (j < tlen && s[i] == t[j]) ++j;
pre[i] = j; // t[0..j-1] 是 s[0..i] 的子序列
}
for (int i = slen - 1, j = tlen - 1; i >= 0; --i) {
if (j >= 0 && s[i] == t[j]) --j;
suf[i] = j; // t[j+1..tlen-1] 是 s[i..slen-1] 的子序列
}
suf[slen] = tlen - 1;
int ans = 0;

for (int i = 0, j = 0, tmp = 0; i <= slen; ++i) {
while (j <= slen && tmp >= suf[j] + 1) ++j;
ans = max(ans, j - i - 1);
tmp = pre[i];
}
cout << ans << endl;
return 0;
}

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

第 28 题（判断题，1 分）

程序输出时， $\text{suf}$ 数组满足：对任意 $0 \leq i < \text{slen}$ ， $\text{suf}[i] \leq \text{suf}[i+1]$ 。（）

正确答案正确

解析详情

【答案】正确

【考点】后缀匹配的单调性

【解析】循环 `for (int i = slen - 1; i >= 0; --i)` 中，当匹配字符相同时 `j--`。所以 `i` 从大变小，`j` 只会单调减小或不变。反过来从下标角度看，`suf[i]` (即当时的 `j`) 随着下标 `i` 增加也是单调不减的。

【易错点】受逆序循环和递减操作的干扰，搞反了不等式方向。

第 29 题（判断题，2 分）

当t是s的子序列时，输出一定不为 $\theta$ 。

正确答案错误

解析详情

【答案】错误

【考点】子序列与可删除区间

【解析】输出非 0 要求能找到合法的 `i`、`j` 使得 `j - i - 1 > 0`。若 `s` 与 `t` 完全相等，子序列条件满足，但无法删除任何连续的非空片段，否则长度不够。此时 `ans` 仍保持为初始值 0。

【易错点】认为只要是子序列就必然存在多余字符可被删去。

第 30 题（判断题，2 分）

程序运行到第23行时，“j - i - 1”一定不小于0。（）

正确答案错误

解析详情

【答案】错误

【考点】双指针边界

【解析】循环中若匹配失败，`j` 会减小。可能出现 `j <= i`，此时 `j - i - 1` 为负数。代码中通过 `ans = max(ans, j - i - 1)` 来过滤负数，所以中间状态的表达式值可能小于 0。

【易错点】混淆了 `ans` 结果非负与中间计算过程可能为负数的概念。

第 31 题（判断题，2 分）

当t是s的子序列时，pre数组和suf数组满足：对任意 $0 \leq i < slen$ ， $pre[i] > suf[i+1] + 1$ 。（）

正确答案错误

解析详情

【答案】错误

【考点】前缀与后缀子序列匹配

【解析】若 `s` 和 `t` 完全一样，对于任意 `i`，前缀匹配正好消耗 `i+1` 个字符（`pre[i] = i+1`），后缀匹配 `suf[i+1]` 为 `i`。此时 `pre[i] = suf[i+1] + 1`，并没有严格大于（>）。

【易错点】忽视完全匹配情况下的相等边界。

第 32 题（单选题，4 分）

若 tlen=10，输出为 0，则 slen 最小为（）。

正确答案C

解析详情

【答案】C

【考点】字符串长度边界

【解析】`cin >> s >> t` 读入字符串，长度至少为 1。输出为 0 表示没有多余的连续字符可删（或者删除后无法满足子序列要求）。当 `slen = 1` 时，显然 `ans = 0`，所以最小值为 1。

【易错点】试图用 `slen = 0` 解释空串，但 C++ `cin >> string` 不会读入空串。

第 33 题（单选题，4 分）

若 tlen=10，输出为 2，则 slen 最小为（）。

正确答案D

解析详情

【答案】D

【考点】子序列长度下界

【解析】要能删除连续 2 个字符（输出为 2）并使得剩余字符中包含长度为 10 的 `t` 作为子序列，`s` 的长度至少必须包含这 10 个有效字符和被删除的 2 个多余字符，所以 `slen` 至少为 12。

【易错点】计算时重叠了有效字符和被删除字符的长度。

三、完善程序（1）

1. （匠人的自我修养）一个匠人决定要学习 n 个新技术。要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。

输入第一行有两个数，分别为新技术个数 $n\left(1 \leq n \leq 10^{3}\right)$ ，以及已有经验值 $\left(\leq 10^{7}\right)$ 。

接下来 n 行。第 i 行的两个正整数，分别表示学习第 i 个技术所需的最低经验值（≤ 10⁷），以及学会第 i 个技术后可获得的经验值（≤ 10⁴）。

接下来 n 行。第 i 行的第一个数 $m_i$ （ $0 \leq m_i < n$ ），表示第 i 个技术的相关技术数量。紧跟着 m 个两两不同的数，表示第 i 个技术的相关技术编号。输出最多能学会的新技术个数。

下面的程序以 $O(n^{2})$ 的时间复杂度完成这个问题，试补全程序。

#include <cstdio>
using namespace std;
const int maxn = 1001;

int n;
int cnt[maxn];
int child[maxn][maxn];
int unlock[maxn];
int points;
int threshold[maxn], bonus[maxn];

bool find() {
    int target = -1;
    for (int i = 1; i <= n; ++i)
        if (① && ②) {
            target = i;
            break;
        }
    }
    if (target == -1)
        return false;
    unlock[target] = -1;
    ③;
    for (int i = 0; i < cnt[target]; ++i)
        ④;
    return true;
}

int main() {
    scanf("%d%d", &n, &points);
    for (int i = 1; i <= n; ++i) {
        cnt[i] = 0;
        scanf("%d%d", &threshold[i], &bonus[i]);
    }
    for (int i = 1; i <= n; ++i) {
        int m;
        scanf("%d", &m);
    }
}

for (int j = 0; j < m; ++j) {
int fa;
scanf("%d", &fa);
child[fa][cnt[fa]] = i;
++cnt[fa];
}
}
int ans = 0;
while (find())
++ans;
printf("%d\n", ans);
return 0;
}

第 34 题（单选题，3 分）

①处应填（）

unlock[i] == 0

unlock[i] <= 0

unlock[i] >= 0

unlock[i] == -1

正确答案A

解析详情

【答案】A

【考点】拓扑依赖状态

【解析】技术 `i` 可以被研究的前提是它的前置依赖全部满足。`unlock[i]` 用于记录未满足的前置技术数量。只有当 `unlock[i] == 0` 时，才表示不再有阻碍，此时填 A。选项 D `unlock[i] == -1` 是用于标记已经学过的技术。

【易错点】选 `unlock[i] <= 0` 会把已经研究过的技术（标记为 -1）重复处理。

第 35 题（单选题，3 分）

②处应填（）

threshold[i] > points

points >= threshold[i]

threshold[i] >= points

points > threshold[i]

正确答案B

解析详情

【答案】B

【考点】阈值条件判断

【解析】学会技术的另一个条件是当前总经验值必须达到该技术的门槛值。当前经验值为 `points`，门槛为 `threshold[i]`。必须满足 `points >= threshold[i]` 才能学习。

【易错点】门槛包含相等情况，不能使用严格大于。

第 36 题（单选题，3 分）

③处应填（）

bonus[target] = 0

--cnt[target]

points += bonus[target]

target = -1

正确答案C

解析详情

【答案】C

【考点】状态更新

【解析】学会技术 `target` 后，玩家会获得该技术的经验值奖励，使得总经验增加。对应操作是 `points += bonus[target]`，这样新增加的经验值能用于解锁后续技术。

【易错点】错误更新与点数无关的依赖数组 `cnt`。

第 37 题（单选题，3 分）

④处应填（）

unlock[child[target][i]] = 0

cnt[child[target][i]] = 0

cnt[child[target][i]] -= 1

unlock[child[target][i]] -= 1

正确答案D

解析详情

【答案】D

【考点】依赖计数更新

【解析】学会 `target` 后，依赖它的后续技术的前置条件就满足了一个，所以它们对应的“未满足前置数”需减 1。后续技术的索引是 `child[target][i]`，所以操作为 `unlock[child[target][i]] -= 1`。

【易错点】误把记录后继技术数量的 `cnt` 数组当成了依赖计数更新。

第 38 题（单选题，3 分）

⑤处应填（）

unlock[i] = 0

unlock[i] = -1

unlock[i] = m

unlock[i] = cnt[i]

正确答案C

解析详情

【答案】C

【考点】依赖计数初始化

【解析】读入第 `i` 项技术时，`m` 表示它的前置技术数量。`unlock[i]` 应初始赋值为 `m`，表示还有 `m` 个前置未完成。随着前置技术被解锁，这个值逐渐减到 0。

【易错点】错将 `unlock[i]` 赋为其他无关初始值或标记。

三、完善程序（2）

2. （取石子）Alice 和 Bob 两个人在玩取石子游戏。他们制定了 n 条取石子的规则，第 i 条规则为：如果剩余石子的个数大于等于 a[i] 且大于等于 b[i]，那么他们可以取走 b[i] 个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了。一开始石子有 m 个。请问先取石子的人是否有必胜的方法？

输入第一行有两个正整数，分别为规则个数 n（1 ≤ n ≤ 64），以及石子个数 m（≤ 10⁷）。

接下来 n 行。第 i 行有两个正整数 a[i] 和 b[i]。（1 ≤ a[i] ≤ 10⁷, 1 ≤ b[i] ≤ 64）

如果先取石子的人必胜，那么输出 “Win”，否则输出 “Loss”。

提示:

可以使用动态规划解决这个问题。由于 b[i] 不超过 64，所以可以使用 64 位无符号整数去压缩必要的状态。

status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。

试补全程序。

代码说明：

“~”表示二进制补码运算符，它将每个二进制位的0变为1、1变为0；

而 “^” 表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 0，反之为 1。

ull 标识符表示它前面的数字是 unsigned long long 类型。

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

const int maxn = 64;
int n, m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &a[i], &b[i]);
}

for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j)
        if (a[i] > a[j]) {
            swap(a[i], a[j]);
            swap(b[i], b[j]);
        }
    status = ①;
    trans = 0;
    for (int i = 1, j = 0; i <= m; ++i) {
        while (j < n && ②) {
            ③;
            ++j;
        }
        win = ④;
        ⑤;
    }
    puts(win ? "Win" : "Loss");
    return 0;
}

第 39 题（单选题，3 分）

①处应填（）

~0ull

1

0

~0ull ^ 1

正确答案D

解析详情

【答案】D

【考点】位压缩动态规划初始化

【解析】状态 `status` 的最低位表示 0 个石子时的胜负，显然必败（值为 0）。对于高位，为防止越界计算应全填 1（表示安全或不可达必败态）。`~0ull` 是全 1，异或 1 (`^ 1`) 后仅最低位变 0，因此选 D。

【易错点】全置 0 会导致后续未初始化的位置被误判为可利用的必败态。

第 40 题（单选题，3 分）

②处应填（）

a[j] > i

a[j] != i

a[j] == i

a[j] < i

正确答案C

解析详情

【答案】C

【考点】排序扫描与规则激活

【解析】外层循环枚举当前石子总数 `i`。当 `a[j]` 恰好等于 `i` 时，规则 `j` 被激活并可用。因数组已按 `a` 升序排列，应用 `a[j] == i` 将满足当前门槛的规则全部加入可用集合。

【易错点】使用 `<` 或 `>` 会错过刚好满足条件的阈值，或跳过多条同级规则。

第 41 题（单选题，3 分）

③处应填（）

trans += 1ull << (b[j] - 1)

trans |= 1ull << (b[j] - 1)

status |= 1ull << (b[j] - 1)

status += 1ull << (b[j] - 1)

正确答案B

解析详情

【答案】B

【考点】位掩码集合表示

【解析】变量 `trans` 用于记录当前允许取走哪些数量的石子。当可以取 `b[j]` 个石子时，应将 `trans` 的第 `b[j]-1` 位置 1。使用位或操作 `trans |= 1ull << (b[j] - 1)` 能安全添加，不受重复元素进位影响。

【易错点】用加法 `+=` 可能因重复的步长规则引发进位，导致掩码错误。

第 42 题（单选题，3 分）

④处应填（）

~status & trans

~status | trans

status | trans

status & trans

正确答案A

解析详情

【答案】A

【考点】博弈动态规划状态转移

【解析】先手必胜的条件是：在可用步数集合中，存在至少一个步数能到达必败状态（对应位为 0）。所以我们要检查 `trans` 的位（可用操作）是否与 `status` 为 0 的位（后继必败）有交集。`~status & trans` 非 0 即可确认。

【易错点】忘记对 `status` 取反，导致找成了“到达必胜状态”的步子。

第 43 题（单选题，3 分）

⑤处应填（）

status = trans >> 1 ^ win

trans = status ^ trans | win

trans = status | trans ^ win

status = status << 1 ^ win

正确答案D

解析详情

【答案】D

【考点】滚动位压缩状态

【解析】当前求得 `i` 个石子的胜负为 `win`，计算下一个 `i+1` 时，所有历史步数距离增加 1，对应于掩码整体左移 1 位：`status << 1`。并将当前结果写入最低位，用异或或位或均可：`status << 1 ^ win`。

【易错点】移位方向错误，向右移位会导致历史距离变短而不是变长。