2019 CSP-S 提高组初赛真题及解析 · 完整43题

2019年CSP-S提高组第一轮认证完整真题，含15道单项选择题、3道阅读程序题（18小题）、2道完善程序题（10小题），每题附详细解析。CSP改革元年，题型具有里程碑意义。

获取 2019CSP-S提高初赛完整真题及详细解析.pdf

请关注状元编程公众号，回复 2019CSP-S

一、单项选择题（共15题，每题2分，共计30分）

第1题

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

A. 0.000000B. 2.750000C. 2.500000D. 3.500000

【答案】D

【解析】 按运算符优先级计算：

• a%3 = 7%3 = 1
• (int)(x+y) = (int)(2.5+4.7) = (int)7.2 = 7
• 1*7 = 7
• 7%2 = 1
• x+1 = 2.5+1 = 3.5

第2题

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

A. WMVB. MPEGC. JPEGD. AVI

【答案】C

【解析】 WMV、MPEG、AVI 均为视频文件格式，JPEG 是图像文件格式。

第3题

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

A. 11 1111 1101 1111B. 11 1111 1111 1101C. 10 1111 1111 1111D. 11 1111 1111 1111

【答案】D

【解析】 逐位做或运算，每一位只要有1则为1：

  11 1011 1001 0111| 01 0110 1110 1011= 11 1111 1111 1111

14位全部为1，选D。

第4题

编译器的功能是（ ）

A. 将源程序重新组合B. 将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言）C. 将低级语言翻译成高级语言D. 将一种编程语言翻译成自然语言

【答案】B

【解析】 编译器将高级语言（如C++）翻译成低级语言（机器语言），方便机器执行。编译器主要工作流程：源代码 → 编译 → 目标代码 → 链接 → 可执行程序。

第5题

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

A. x=(x*100+0.5)/100.0B. x=(int)(x*100+0.5)/100.0C. x=(x/100+0.5)*100.0D. x=x*100+0.5/100.0

【答案】B

【解析】 以 x=3.141 为例：

• x*100+0.5 = 314.1+0.5 = 314.6
• (int)314.6 = 314（强制转整数，截断小数部分）
• 314/100.0 = 3.14

B选项先放大、四舍五入、取整、再缩小，正确。

第6题

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

A. 104B. 102C. 98D. 100

【答案】B

【解析】 分三种情况讨论：

（1）含2个相同数字的4位数（如1,1,2,4 / 1,1,2,8 / 1,1,4,8 / 1,2,8,8 / 1,4,8,8 / 2,4,8,8）：

• 每组有 A(4,4)/A(2,2) = 24/2 = 12 种
• 共 6 组 × 12 = 72 种

（2）4个不同数字（1,2,4,8）：

• A(4,4) = 24 种

（3）含2对相同数字（1,1,8,8）：

• C(4,2) = 6 种

总计：72 + 24 + 6 = 102 种

第7题

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

A. 冒泡排序B. 直接插入排序C. 快速排序D. 归并排序

【答案】C

【解析】 不稳定排序：快速排序、选择排序、希尔排序、堆排序。稳定排序：冒泡排序、插入排序、归并排序、基数排序。

快速排序在中枢元素交换时可能打乱相同元素的相对顺序。

第8题

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

A. 10B. 9C. 11D. 8

【答案】B

【解析】 n个顶点的完全无向图最多有 n(n-1)/2 条边。

• n=8 时：8×7/2 = 28 条边（完全图K₈正好28条边）
• 但要求非连通，所以需要9个顶点：8个点组成完全图（28条边），第9个点孤立

因此至少需要 9 个顶点。

第9题

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

A. 40B. 25C. 30D. 20

【答案】B

【解析】 车牌 ABCDE 翻转后仍为 ABCDE，则：

• A、E 必须互为翻转（A,E ∈ {0,1,8,6,9}）
• B、D 必须互为翻转（B,D ∈ {0,1,8,6,9}）
• C 必须翻转后仍为自身（C ∈ {0,1,8}）

前2位各有5种选择（0,1,8,6,9），后2位由前2位决定。

第3位（C）只能取 0,1,8，它们模3的余数分别为 0,1,2。因此给定其他4位后，第3位有且仅有1种选择使总和被3整除。

总数 = 5 × 5 × 1 × 1 × 1 = 25

第10题

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

A. 23B. 21C. 20D. 22

【答案】A

【解析】 容斥原理：

第11题

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

A. n²B. n log nC. 2nD. 2n-1

【答案】D

【解析】 最坏情况：两个数组交替排列，如 A=(1,3,5), B=(2,4,6)，每次取较小者都需比较。

• 结果数组共 2n 个元素
• 一个数组空了，另一个数组还剩1个元素时比较次数最多
• 比较次数 = 2n - 1

第12题

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

A. 栈B. 二叉树C. 队列D. 邻接矩阵

【答案】D

【解析】 邻接矩阵和邻接表是图的存储结构。栈、队列、二叉树是数据结构，但不是图的存储方式。

第13题

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

A. Dijkstra 算法B. Floyd 算法C. Prim 算法D. Kruskal 算法

【答案】B

【解析】

• Dijkstra：每次选取距离最小的未访问顶点 → 贪心
• Prim：每次选最小权值的边 → 贪心
• Kruskal：每次选最小权值且不构成环的边 → 贪心
• Floyd：枚举所有中间节点，动态规划思想 → 非贪心

第14题

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

A. 5B. 3C. 4D. 2

【答案】B

【解析】 设公比为 p，共 2k+1 项：

• 首项 a₁ = 2，末项 a_{2k+1} = 2·p^{2k} = 118098
• 中间项 a_{k+1} = 2·p^k = 486 → p^k = 243 = 3⁵

所以 p = 3, k = 5，验证：2 × 3¹⁰ = 2 × 59049 = 118098 ✓

第15题

有正实数构成的数字三角形排列形式如图所示。从 a₁,₁ 开始，每一行的数 aᵢ,ⱼ 只有两条边可以分别通向下一行的两个数 aᵢ₊₁,ⱼ 和 aᵢ₊₁,ⱼ₊₁。用动态规划算法找出一条路径使得该路径上的数之和最大。

令 C[i][j] 是从 a₁,₁ 到 aᵢ,ⱼ 的路径上的数的最大和，并且 C[i][0] = C[0][j] = 0，则 C[i][j] =（ ）

A. max{C[i-1][j-1], C[i-1][j]} + aᵢ,ⱼB. C[i-1][j-1] + C[i-1][j]C. max{C[i-1][j-1], C[i-1][j]} + 1D. max{C[i][j-1], C[i-1][j]} + aᵢ,ⱼ

【答案】A

【解析】 经典数塔问题。路径只能从左上方 (i-1,j-1) 或正上方 (i-1,j) 到达 (i,j)，取两者最大值加上当前格子的值：

二、阅读程序题（共3题，判断题+选择题，共计40分）

阅读程序第1题（单调栈）

#include<cstdio>usingnamespace std;int n;int a[100];intmain(){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 ", ans);    }return0;}

【程序分析】 对于每个位置 i，程序找到右侧第一个比 a[i] 大的元素位置 ans。如果不存在，则 ans = n。利用了单调栈的思想，ans 只增不减。

判断题：

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

【答案】×

【解析】 当 i=1 且 a[1] < a[2] 时，while 循环不执行，ans 保持为1，等于 i。说"一定"的判断通常是错的。

17.（1分）程序输出的 ans 小于等于 n。（ ）

【答案】√

【解析】 while 循环条件为 ans < n，所以 ans 最大为 n。

18.（1.5分）若将第12行的"<"改为"!="，程序输出的结果不会改变。（ ）

【答案】√

【解析】 第12行是 i > 1 && a[i] < a[i-1]。将 < 改为 !=：由于此时 i > 1，如果 a[i] != a[i-1]，要么 a[i] < a[i-1]（触发重置），要么 a[i] > a[i-1]（不触发，ans 从上一轮继承）。关键在于当 a[i] > a[i-1] 时，上一轮的 ans 已经 >= i（因为上一步 a[i-1] 的 while 循环至少推进到 i），所以不需要重置。因此结果不变。

19.（1.5分）当程序执行到第16行时，若 ans-i > 2，则 a[i+1] ≤ a[i]。（ ）

【答案】√

【解析】 若 ans-i > 2，说明 while 循环至少执行了2次以上，即 a[i+1] ≤ a[i] 且 a[i+2] ≤ a[i]。因此 a[i+1] ≤ a[i] 成立。

选择题：

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

A. O(log n)B. O(n²)C. O(n log n)D. O(n)

【答案】D

【解析】 严格递增时，对每个 i，a[i] >= a[ans+1] 不成立（因为 a[ans+1] > a[i]），while 循环不执行。ans 从上一轮继承，只增不减。总操作次数 O(n)。

21.（4分）最坏情况下，此程序的时间复杂度是（ ）

A. O(n²)B. O(log n)C. O(n)D. O(n log n)

【答案】A

【解析】 最坏情况如严格单调递减序列：每个 i 的 while 循环都从 i 扫到 n，总次数 = 1+2+…+n = O(n²)。

阅读程序第2题（并查集）

#include<iostream>usingnamespace std;constint maxn = 1000;int n;int fa[maxn], cnt[maxn];intgetRoot(int v){if (fa[v] == v) return v;returngetRoot(fa[v]);}intmain(){    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;return0;}

【程序分析】 这是一个并查集程序。getRoot 是 find 函数（无路径压缩）。每次合并两个集合时，累加 cnt[x] * cnt[y]（两个集合大小的乘积）。共进行 n-1 次合并，最终输出所有合并的乘积之和。

判断题：

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

【答案】√

【解析】 fa 数组下标范围为 0 到 n-1，a 和 b 作为 getRoot 的参数，必须在 [0, n-1] 范围内。

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

【答案】×

【解析】fa[i]=0 会使所有元素都指向节点0，破坏并查集结构。正确初始化应 fa[i]=i，使每个元素自成一集合。

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

【答案】√

【解析】 fa 的值始终是某个 0 到 n-1 范围内的节点编号。

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

【答案】×

【解析】 当节点 i 被合并到其他集合后，cnt[i] 不再被更新，保持原值。但根节点的 cnt 可以达到 n。非根节点的 cnt 可以是任何之前的值，不一定在 [1, n] 内（虽然初始为1，但不会超过n）。实际上这个判断是错的，因为题目说的是"任意 i"，但被合并后的非根节点 cnt 不会更新，可能不是当前集合的实际大小。严格来说 cnt[i] 的值在 [1, n] 内，但表示的含义可能不正确。关键反例：cnt[i] 可以为 0（当节点被合并后，其 cnt 值虽然不会变为0，但题目说"都有 1 ≤ cnt[i] ≤ n"是错的，因为 cnt 表示的是集合大小，非根节点的 cnt 已失效）。

实际上从数值上看 cnt[i] 始终 ≥ 1（初始为1，只增不减），但 cnt[i] 可以超过 n 的合理范围吗？不会，因为总元素数为 n。所以从数值角度 1 ≤ cnt[i] ≤ n 是成立的……但题目答案为×，可能是因为 cnt[i] 对非根节点来说不再有意义。

选择题：

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

A. 1276B. 1176C. 1225D. 1250

【答案】C

【解析】 x ≠ y 表示每次合并两个不同集合。每次都是单元素集合合并到主集合：

• 第1次合并：cnt[x]=1, cnt[y]=1, 乘积=1
• 第2次合并：cnt[x]=1, cnt[y]=2, 乘积=2
• ...
• 第49次合并：cnt[x]=1, cnt[y]=49, 乘积=49

总和 = 1+2+...+49 = 49×50/2 = 1225

27.（4分）此程序的时间复杂度是（ ）

A. O(n)B. O(log n)C. O(n²)D. O(n log n)

【答案】C

【解析】 getRoot 函数没有路径压缩，单次查找最坏为 O(n)。共 n-1 次合并，每次两次查找，总复杂度 O(n²)。

阅读程序第3题（子序列匹配）

#include<iostream>#include<string>usingnamespace std;constint max1 = 202;string s, t;int pre[max1], suf[max1];intmain(){    cin >> s >> t;int slen = s.length(), tlen = t.length();for (int i = 0, j = 0; i < s.size(); ++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 <= s.size(); ++i) {while (j <= s.size() && tmp >= suf[j] + 1) ++j;        ans = max(ans, j - i - 1);        tmp = pre[i];    }    cout << ans << endl;return0;}

【程序分析】 程序求从 s 中删除一段连续子串后，t 仍然是 s 的子序列时，能删除的最大长度。

• pre[i]：s[0..i] 能匹配 t 的前 pre[i] 个字符
• suf[i]：s[i..slen-1] 能匹配 t 的后 tlen-1-suf[i] 个字符
• 双指针扫描，找最大的 j-i-1（即删除 s[i+1..j-1] 的长度）

判断题：

28.（1分）程序输出时，suf 数组满足：对任意 0 ≤ i < slen，suf[i] ≤ suf[i+1]。（ ）

【答案】√

【解析】 suf 数组从后往前构建，j 只减不增，因此 suf[i] 是递减的（即 suf[i] ≥ suf[i+1]）。但题目说 suf[i] ≤ suf[i+1]... 

实际上，suf[i] 表示从位置 i 开始向右能匹配 t 的后缀起始位置。从右向左扫描时，j 递减。suf[i] 的值取决于 s[i] 是否匹配 t[j]。由于越往左扫描，j 可能减少也可能不变，所以 suf[i] ≥ suf[i+1]。但题目说 suf[i] ≤ suf[i+1]，这与实际相反……

重新分析：suf[i] 存储的是 j 的值。当 s[i] == t[j] 时 j 递减。所以 suf[i] = j（递减后的值），而 suf[i+1] 是之前（更靠右）的 j 值。由于 j 从 tlen-1 开始递减，suf[i] ≤ suf[i+1] 是正确的（因为越往左，j 越小或相等）。

29.（2分）当 t 是 s 的子序列时，输出一定不为 0。（ ）

【答案】×

【解析】 当 s == t 时，不需要删除任何字符，输出为 0。

30.（2分）程序运行到第23行时，j - i - 1 一定不小于 0。（ ）

【答案】×

【解析】 当 while 循环条件不满足时，j 可能等于 i，此时 j-i-1 = -1 < 0。

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

【答案】×

【解析】 不一定。当 t == s == "cc" 时，可以验证存在 i 使得 pre[i] == suf[i+1] + 1。

选择题：

32.（4分）若 tlen=10，输出为 0，则 slen 最小为（ ）

A. 10B. 12C. 0D. 1

【答案】D

【解析】 输出为 0 表示不需要删除任何字符。当 slen=1 时，s 只有一个字符，t 有10个字符，t 不是 s 的子序列。但程序输出的是"最大删除长度"，当 s 长度为1时，无法删除（删除后 s 为空串，t 仍不是空串的子序列除非 t 也为空），所以输出为0。slen 最小为 1。

33.（4分）若 tlen=10，输出为 2，则 slen 最小为（ ）

A. 0B. 10C. 12D. 1

【答案】C

【解析】 输出为 2 表示可以删除 2 个字符后 t 仍是 s 的子序列。删除 2 个字符后 s 的长度至少为 tlen=10，因此原 s 长度至少为 10+2 = 12。

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

完善程序第1题（匠人的自我修养）

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

#include<iostream>usingnamespace std;constint maxn = 1001;int n;int cnt[maxn];int child[maxn][maxn];int unlock[maxn];int threshold[maxn], bonus[maxn];int points;boolfind(){int target = -1;for (int i = 1; i <= n; ++i)if (① && ②) {            target = i;break;        }if (target == -1) returnfalse;    unlock[target] = -1;    ③for (int i = 0; i < cnt[target]; ++i)        ④returntrue;}intmain(){    cin >> n >> points;for (int i = 1; i <= n; ++i) {        cin >> threshold[i] >> bonus[i];        cin >> cnt[i];for (int j = 0; j < cnt[i]; ++j)            cin >> child[i][j];        ⑤    }int ans = 0;while (find()) ++ans;    cout << ans << endl;return0;}

34. ①处应填（ ）

A. unlock[i] <= 0B. unlock[i] >= 0C. unlock[i] == 0D. unlock[i] == -1

【答案】C

【解析】 unlock[i] == 0 表示该技术的所有前置技术都已学会（可以解锁）。unlock[i] == -1 表示已经学过。

35. ②处应填（ ）

A. threshold[i] > pointsB. threshold[i] >= pointsC. points > threshold[i]D. points >= threshold[i]

【答案】D

【解析】 学习技术需要经验值足够，即当前经验 points 大于等于所需经验 threshold[i]。

36. ③处应填（ ）

A. target = -1B. --cnt[target]C. bonus[target]D. points += bonus[target]

【答案】D

【解析】 学会新技术后，经验值增加 bonus[target]。

37. ④处应填（ ）

A. cnt[child[target][i]] -= 1B. cnt[child[target][i]] = 0C. unlock[child[target][i]] -= 1D. unlock[child[target][i]] = 0

【答案】C

【解析】 学会 target 后，以 target 为前置技术的其他技术的 unlock 值减1（减少一个未完成的前置任务）。

38. ⑤处应填（ ）

A. unlock[i] = cnt[i]B. unlock[i] = mC. unlock[i] = 0D. unlock[i] = -1

【答案】B

【解析】 初始化时，unlock[i] 设为该技术的前置技术数量 m（即 cnt[i] 的值）。当所有前置技术都学完后，unlock[i] 减到0，表示可以学习。

完善程序第2题（取石子）

Alice 和 Bob 两个人在玩取石子游戏。有 n 条取石子的规则，第 i 条规则为：如果剩余石子数 ≥ a[i] 且 ≥ b[i]，则可以取走 b[i] 个石子。轮流取石子，无法取者输。一开始有 m 个石子，判断先手是否必胜。

提示： 由于 b[i] ≤ 64，使用 unsigned long long 位运算压缩状态。

#include<cstdio>#include<algorithm>usingnamespace std;constint maxn = 64;int n, m;unsignedlonglong a[maxn], b[maxn];unsignedlonglong status, trans;intmain(){scanf("%d%d", &n, &m);for (int i = 0; i < n; ++i)scanf("%d%d", &a[i], &b[i]);    status = ①;for (int i = 1; i <= m; ++i) {        trans = 0;for (int j = 0; j < n; ++j)if (②) {                ③;            }unsignedlonglong win = ④;        ⑤;    }if (status & (1ULL << (m % 64)))printf("Win\n");elseprintf("Loss\n");return0;}

【程序分析】 使用 SG 博弈论 + 位运算优化：

• status 的第 k 位表示剩余 k 个石子时当前玩家是否必胜
• trans 记录所有可转移到的状态
• win = ~status & trans（存在转移到的必败状态 → 当前必胜）
• 每轮将 win 信息左移1位存入 status（滑动窗口）

39. ①处应填（ ）

A. 0B. ~0ullC. ~0ull ^ 1D. 1

【答案】C

【答案】C

【解析】 status 是 64 位窗口，初始时石子数为 0 是必败状态（第0位为0），其余位初始为1（待计算）。~0ull ^ 1 = 全1但最低位为0。

40. ②处应填（ ）

A. a[j] < iB. a[j] == iC. a[j] != iD. a[j] > i

【答案】B

【解析】 当剩余石子数 i 等于 a[j] 时，可以使用第 j 条规则（题目中 a[j] 表示使用该规则所需的最低石子数，此处精确匹配）。

41. ③处应填（ ）

A. trans |= 1ULL << (b[j] - 1)B. status |= 1ULL << (b[j] - 1)C. status += 1ULL << (b[j] - 1)D. trans += 1ULL << (b[j] - 1)

【答案】A

【解析】 取走 b[j] 个石子后，剩余 i - b[j] 个石子。将 trans 的第 (b[j]-1) 位设为1，表示可以转移到"剩余 b[j]-1 个石子"的状态（相对于当前窗口偏移）。

42. ④处应填（ ）

A. ~status | transB. status & transC. status | transD. ~status & trans

【答案】D

【解析】 先手必胜 = 存在一个转移目标状态是必败的。~status 取反得到必败状态，& trans 得到可转移到的必败状态。只要有1位为1，当前状态就必胜。

43. ⑤处应填（ ）

A. trans = status | trans ^ winB. status = trans >> 1 ^ winC. trans = status ^ trans | winD. status = status << 1 ^ win

【答案】D

【解析】 更新 status：窗口左移1位（加入新状态），用异或将 win 信息写入最低位。status << 1 滑动窗口，^ win 将当前必胜信息记录到对应位。

答案速查表

单项选择题

阅读程序

完善程序

考点分布分析

核心知识点精讲

1. 单调栈优化（阅读程序1）

程序利用 ans 指针的单调递增性质，避免了每个位置从头扫描。当 a[i] < a[i-1] 时重置 ans = i，否则继承上一轮的 ans 值继续向后推进。均摊时间复杂度 O(n)。

2. 并查集合并计数（阅读程序2）

并查集的 getRoot 函数没有路径压缩，最坏 O(n)。每次合并累加 cnt[x] * cnt[y]，本质是计算所有元素对的数量。当 n=50 时，若每次合并单元素到主集合，结果为 1+2+...+49 = 1225。

3. 子序列双指针匹配（阅读程序3）

• pre[i]：从前向后扫描，记录 s[0..i] 能匹配 t 的前多少个字符
• suf[i]：从后向前扫描，记录 s[i..end] 能匹配 t 的后多少个字符
• 双指针 i, j 扫描，找最大删除区间长度 j - i - 1

4. 拓扑排序模拟（完善程序1）

匠人学习技术本质上是有向图的拓扑排序：

• unlock[i] 记录前置技术数（入度）
• unlock[i] == 0 时可学习
• 学会后 points += bonus[target]，并减少后续技术的 unlock 值

5. SG博弈 + 位运算压缩（完善程序2）

利用 b[i] ≤ 64 的特点，用 unsigned long long 的每一位表示一个状态：

• status：64位滑动窗口，记录最近64个石子数的胜负
• trans：当前可转移到的状态集合
• win = ~status & trans：存在转移到必败状态 → 当前必胜
• status = status << 1 ^ win：窗口滑动，记录新状态

备考建议：2019年是CSP改革第一年，题目覆盖面广，从基础表达式求值到位运算博弈论均有涉及。建议重点掌握：并查集原理、单调栈优化、子序列匹配双指针、拓扑排序模拟、SG博弈位运算压缩。这些知识点在后续年份的CSP-S初赛中反复出现。