开始整卷作答
按大题分页，翻页自动存草稿，做完统一交卷。
## 一、单项选择题（共 $15$ 题，每题 $2$ 分，共 $30$ 分）
第 1–15 题 · 共 15 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X；除特殊说明外，判断题 $1.5$ 分，选择题 $4$分，共计 $40$ 分）
第 16–16 题 · 共 1 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X；除特殊说明外，判断题 $1.5$ 分，选择题 $4$分，共计 $40$ 分）
1.
```cpp
#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;
}
```
第 17–21 题 · 共 5 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X；除特殊说明外，判断题 $1.5$ 分，选择题 $4$分，共计 $40$ 分）
第 22–22 题 · 共 1 题
2.
```cpp
#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;
}
```
第 23–27 题 · 共 5 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X；除特殊说明外，判断题 $1.5$ 分，选择题 $4$分，共计 $40$ 分）
第 28–28 题 · 共 1 题
3.
$t$ 是 $s$ 的子序列的意思是：从 $s$ 中删去若干个字符，可以得到 $t$；特别的，如果 $s=t$，那么 $t$ 也是 $s$ 的子序列；空串是任何串的子序列。例如：$\texttt{acd}$ 是 $\texttt{abcde}$ 的子序列，$\texttt{acd}$ 是 $\texttt{acd}$ 的子序列，但 $\texttt{adc}$ 不是 $\texttt{abcde}$ 的子序列。
$s[x..y]$ 表示 $s[x] \cdots s[y]$ 共 $y-x+l$ 个字符构成的字符串，若 $x>y$ 则 $s[x..y]$ 是空串。$t[x..y]$ 同理。
```cpp
#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];
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\dots pre[i]-1]$ 是 $s[0\dots i]$ 的子序列；
- $t[suf[i]+1\dots tlen-1]$ 是 $ s[i\dots slen-1]$ 的子序列。
第 29–33 题 · 共 5 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
第 34–34 题 · 共 1 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
1. （匠人的自我修养）
一个匠人决定要学习 $n$ 个新技术。要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数 $n(l\leq n\leq 10^3)$，以及己有经验值（$\le10^7$）。
接下来 $n$ 行。第 $i$ 行的两个正整数，分别表示学习第 $i$ 个技术所需的最低经验值（$\le10^7$），以及学会第 $i$ 个技术后可获得的经验值（$\leq 10^7$）。
接下来 $n$ 行。第 $i$ 行的第一个数 $m_i$（$0\le m_i<n$），表示第 $i$ 个技术的相关技术数量。紧跟着 $m$ 个两两不同的数，表示第 $i$ 个技术的相关技术编号。
输出最多能学会的新技术个数。
下面的程序以 $O(n^2)$ 的时间复杂度完成这个问题，试补全程序。
```cpp
#include<cstdio>
using namespace std;
const int maxn = 1001;
int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn], bonus[maxn];
int points;
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;
}
```
第 35–38 题 · 共 4 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
第 39–39 题 · 共 1 题
2. （取石子）
Alice 和 Bob 两个人在玩取石子游戏。他们制定了 $n$ 条取石子的规则，第 $i$ 条规则为：如果剩余石子的个数大于等于 $a[i]$ 且大于等于 $b[i]$，那么他们可以取走 $b[i]$ 个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了。一开始石子有 $m$ 个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数 $n(1<n<64)$, 以及石子个数 $m( \le 10^7)$。
接下来 $n$ 行。第 $i$ 行有两个正整数 $a[i]$ 和 $b[i]$。$(1 \le a[i] \le 10^7,1 \le b[i] \le 64)$。
如果先取石子的人必胜，那么输出 $\texttt{Win}$，否则输出 $\texttt{Loss}$。
提示：
可以使用动态规划解决这个问题。由于 $b[i]$ 不超过 $64$ ,所以可以使用 $64$ 位无符号整数去压缩必要的状态。
status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。
试补全程序。
代码说明：
`~` 表示二进制补码运算符，它将每个二进制位的 $0$ 变为 $1$、$1$ 变为 $0$;
而 `^` 表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 $0$ ,反之为 $1$。
ull 标识符表示它前面的数字是 unsigned long long 类型。
```cpp
#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;
}
```
第 40–43 题 · 共 4 题
展开逐题清单（单独练某一道）
● 绿=已通过 ● 橙=做过没全对 ● 灰=没做过
## 一、单项选择题（共 $15$ 题，每题 $2$ 分，共 $30$ 分）
1.
[CSP2019 提高级] 第 1 题
2.
[CSP2019 提高级] 第 2 题
3.
[CSP2019 提高级] 第 3 题
4.
[CSP2019 提高级] 第 4 题
5.
[CSP2019 提高级] 第 5 题
6.
[CSP2019 提高级] 第 6 题
7.
[CSP2019 提高级] 第 7 题
8.
[CSP2019 提高级] 第 8 题
9.
[CSP2019 提高级] 第 9 题
10.
[CSP2019 提高级] 第 10 题
11.
[CSP2019 提高级] 第 11 题
12.
[CSP2019 提高级] 第 12 题
13.
[CSP2019 提高级] 第 13 题
14.
[CSP2019 提高级] 第 14 题
15.
[CSP2019 提高级] 第 15 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X；除特殊说明外，判断题 $1.5$ 分，选择题 $4$分，共计 $40$ 分）
16.
[CSP2019 提高级] 第 16 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X；除特殊说明外，判断题 $1.5$ 分，选择题 $4$分，共计 $40$ 分）
1.
```cpp
#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;
}
```
17.
[CSP2019 提高级] 第 17 题
18.
[CSP2019 提高级] 第 18 题
19.
[CSP2019 提高级] 第 19 题
20.
[CSP2019 提高级] 第 20 题
21.
[CSP2019 提高级] 第 21 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X；除特殊说明外，判断题 $1.5$ 分，选择题 $4$分，共计 $40$ 分）
22.
[CSP2019 提高级] 第 22 题
2.
```cpp
#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;
}
```
23.
[CSP2019 提高级] 第 23 题
24.
[CSP2019 提高级] 第 24 题
25.
[CSP2019 提高级] 第 25 题
26.
[CSP2019 提高级] 第 26 题
27.
[CSP2019 提高级] 第 27 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X；除特殊说明外，判断题 $1.5$ 分，选择题 $4$分，共计 $40$ 分）
28.
[CSP2019 提高级] 第 28 题
3.
$t$ 是 $s$ 的子序列的意思是：从 $s$ 中删去若干个字符，可以得到 $t$；特别的，如果 $s=t$，那么 $t$ 也是 $s$ 的子序列；空串是任何串的子序列。例如：$\texttt{acd}$ 是 $\texttt{abcde}$ 的子序列，$\texttt{acd}$ 是 $\texttt{acd}$ 的子序列，但 $\texttt{adc}$ 不是 $\texttt{abcde}$ 的子序列。
$s[x..y]$ 表示 $s[x] \cdots s[y]$ 共 $y-x+l$ 个字符构成的字符串，若 $x>y$ 则 $s[x..y]$ 是空串。$t[x..y]$ 同理。
```cpp
#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];
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\dots pre[i]-1]$ 是 $s[0\dots i]$ 的子序列；
- $t[suf[i]+1\dots tlen-1]$ 是 $ s[i\dots slen-1]$ 的子序列。
29.
[CSP2019 提高级] 第 29 题
30.
[CSP2019 提高级] 第 30 题
31.
[CSP2019 提高级] 第 31 题
32.
[CSP2019 提高级] 第 32 题
33.
[CSP2019 提高级] 第 33 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
34.
[CSP2019 提高级] 第 34 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
1. （匠人的自我修养）
一个匠人决定要学习 $n$ 个新技术。要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数 $n(l\leq n\leq 10^3)$，以及己有经验值（$\le10^7$）。
接下来 $n$ 行。第 $i$ 行的两个正整数，分别表示学习第 $i$ 个技术所需的最低经验值（$\le10^7$），以及学会第 $i$ 个技术后可获得的经验值（$\leq 10^7$）。
接下来 $n$ 行。第 $i$ 行的第一个数 $m_i$（$0\le m_i<n$），表示第 $i$ 个技术的相关技术数量。紧跟着 $m$ 个两两不同的数，表示第 $i$ 个技术的相关技术编号。
输出最多能学会的新技术个数。
下面的程序以 $O(n^2)$ 的时间复杂度完成这个问题，试补全程序。
```cpp
#include<cstdio>
using namespace std;
const int maxn = 1001;
int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn], bonus[maxn];
int points;
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;
}
```
35.
[CSP2019 提高级] 第 35 题
36.
[CSP2019 提高级] 第 36 题
37.
[CSP2019 提高级] 第 37 题
38.
[CSP2019 提高级] 第 38 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
39.
[CSP2019 提高级] 第 39 题
2. （取石子）
Alice 和 Bob 两个人在玩取石子游戏。他们制定了 $n$ 条取石子的规则，第 $i$ 条规则为：如果剩余石子的个数大于等于 $a[i]$ 且大于等于 $b[i]$，那么他们可以取走 $b[i]$ 个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了。一开始石子有 $m$ 个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数 $n(1<n<64)$, 以及石子个数 $m( \le 10^7)$。
接下来 $n$ 行。第 $i$ 行有两个正整数 $a[i]$ 和 $b[i]$。$(1 \le a[i] \le 10^7,1 \le b[i] \le 64)$。
如果先取石子的人必胜，那么输出 $\texttt{Win}$，否则输出 $\texttt{Loss}$。
提示：
可以使用动态规划解决这个问题。由于 $b[i]$ 不超过 $64$ ,所以可以使用 $64$ 位无符号整数去压缩必要的状态。
status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。
试补全程序。
代码说明：
`~` 表示二进制补码运算符，它将每个二进制位的 $0$ 变为 $1$、$1$ 变为 $0$;
而 `^` 表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 $0$ ,反之为 $1$。
ull 标识符表示它前面的数字是 unsigned long long 类型。
```cpp
#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;
}
```
40.
[CSP2019 提高级] 第 40 题
41.
[CSP2019 提高级] 第 41 题
42.
[CSP2019 提高级] 第 42 题
43.
[CSP2019 提高级] 第 43 题