开始整卷作答
按大题分页，翻页自动存草稿，做完统一交卷。
## 一、单项选择题（共 $15$ 题，每题 $2$ 分，共 $30$ 分）
第 1–15 题 · 共 15 题
## 二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×。除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分)
第 16–16 题 · 共 1 题
### 程序阅读题
```cpp
#include <cstdlib>
#include <iostream>
using namespace std;
char encoder[26] = {'C','S','P',0};
char decoder[26];
string st;
int main() {
int k = 0;
for (int i = 0; i < 26; ++i)
if (encoder[i] != 0) ++k;
for (char x ='A'; x <= 'Z'; ++x) {
bool flag = true;
for (int i = 0; i < 26; ++i)
if (encoder[i] ==x) {
flag = false;
break;
}
if (flag) {
encoder[k]= x;
++k;
}
}
for (int i = 0; i < 26; ++i)
decoder[encoder[i]- 'A'] = i + 'A';
cin >> st;
for (int i = 0; i < st.length( ); ++i)
st[i] = decoder[st[i] -'A'];
cout << st;
return 0;
}
```
第 17–20 题 · 共 4 题
第 21 题
共 1 题
## 二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×。除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分)
第 22–22 题 · 共 1 题
### 程序阅读题
```cpp
#include <iostream>
using namespace std;
long long n, ans;
int k, len;
long long d[1000000];
int main() {
cin >> n >> k;
d[0] = 0;
len= 1;
ans = 0;
for (long long i = 0; i <n; ++i) {
++d[0];
for (int j = 0; j + 1<len; ++j) {
if (d[j] == k) {
d[j] = 0;
d[j + 1] += 1;
++ans;
}
}
if (d[len- 1] == k) {
d[len - 1] = 0;
d[len] =1;
++len;
++ans;
}
}
cout << ans << endl;
return 0;
}
```
假设输入的 $n$ 是不超过 $2^{62}$ 的正整数，$k$ 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题：
第 23–27 题 · 共 5 题
## 二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×。除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分)
第 28–28 题 · 共 1 题
### 程序阅读题
```cpp
#include <algorithm>
#include <iostream>
using namespace std;
int n;
int d[50][2];
int ans;
void dfs(int n, int sum) {
if (n == 1) {
ans = max(sum, ans);
return;
}
for (int i = 1; i < n; ++i) {
int a = d[i - 1][0], b = d[i - 1][1];
int x = d[i][0], y = d[i][1];
d[i - 1][0] = a + x;
d[i - 1][1] = b + y;
for (int j = i; j < n - 1; ++j)
d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
int s = a + x + abs(b - y);
dfs(n - 1, sum + s);
for (int j = n - 1; j > i; --j)
d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
d[i - 1][0] = a, d[i - 1][1] = b;
d[i][0] = x, d[i][1] = y;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> d[i][0];
for (int i = 0; i < n;++i)
cin >> d[i][1];
ans = 0;
dfs(n, 0);
cout << ans << endl;
return 0;
}
```
假设输入的 $n$ 是不超过 $50$ 的正整数，`d[i][0]`、`d[i][1]` 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题：
第 29–33 题 · 共 5 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
第 34–34 题 · 共 1 题
第 35–38 题
共 4 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
第 39–39 题 · 共 1 题
### 完善程序题
2.
（最小区间覆盖）给出 $n$ 个区间，第 $i$ 个区间的左右端点是 $[a_i,b_i]$。现在要在这些区间中选出若干个，使得区间 $[0, m]$ 被所选区间的并覆盖（即每一个 $0\leq i\leq m$ 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。
输入第一行包含两个整数 $n$ 和 $m$ （$1\le n \le 5000,1\le m \le 10^9$）
接下来 $n$ 行，每行两个整数 $a_i,b_i$ （$0\le a_i,b_i \le m$）。
提示：使用贪心法解决这个问题。先用 $O(n^2)$ 的时间复杂度排序，然后贪心选择这些区间。
试补全程序。
```cpp
#include <iostream>
using namespace std;
const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];
void sort() // 排序
{
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
if (①)
{
segment t = A[j];
②
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> A[i].a >> A[i].b;
sort();
int p = 1;
for (int i = 1; i < n; i++)
if (③)
A[p++] = A[i];
n = p;
int ans =0, r = 0;
int q = 0;
while (r < m)
{
while (④)
q++;
⑤;
ans++;
}
cout << ans << endl;
return 0;
}
```
第 40–43 题 · 共 4 题
展开逐题清单（单独练某一道）
● 绿=已通过 ● 橙=做过没全对 ● 灰=没做过
## 一、单项选择题（共 $15$ 题，每题 $2$ 分，共 $30$ 分）
1.
[CSP2020 入门级] 第 1 题
2.
[CSP2020 入门级] 第 2 题
3.
[CSP2020 入门级] 第 3 题
4.
[CSP2020 入门级] 第 4 题
5.
[CSP2020 入门级] 第 5 题
6.
[CSP2020 入门级] 第 6 题
7.
[CSP2020 入门级] 第 7 题
8.
[CSP2020 入门级] 第 8 题
9.
[CSP2020 入门级] 第 9 题
10.
[CSP2020 入门级] 第 10 题
11.
[CSP2020 入门级] 第 11 题
12.
[CSP2020 入门级] 第 12 题
13.
[CSP2020 入门级] 第 13 题
14.
[CSP2020 入门级] 第 14 题
15.
[CSP2020 入门级] 第 15 题
## 二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×。除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分)
16.
[CSP2020 入门级] 第 16 题
### 程序阅读题
```cpp
#include <cstdlib>
#include <iostream>
using namespace std;
char encoder[26] = {'C','S','P',0};
char decoder[26];
string st;
int main() {
int k = 0;
for (int i = 0; i < 26; ++i)
if (encoder[i] != 0) ++k;
for (char x ='A'; x <= 'Z'; ++x) {
bool flag = true;
for (int i = 0; i < 26; ++i)
if (encoder[i] ==x) {
flag = false;
break;
}
if (flag) {
encoder[k]= x;
++k;
}
}
for (int i = 0; i < 26; ++i)
decoder[encoder[i]- 'A'] = i + 'A';
cin >> st;
for (int i = 0; i < st.length( ); ++i)
st[i] = decoder[st[i] -'A'];
cout << st;
return 0;
}
```
17.
[CSP2020 入门级] 第 17 题
18.
[CSP2020 入门级] 第 18 题
19.
[CSP2020 入门级] 第 19 题
20.
[CSP2020 入门级] 第 20 题
21.
题目 936 不存在
## 二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×。除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分)
22.
[CSP2020 入门级] 第 22 题
### 程序阅读题
```cpp
#include <iostream>
using namespace std;
long long n, ans;
int k, len;
long long d[1000000];
int main() {
cin >> n >> k;
d[0] = 0;
len= 1;
ans = 0;
for (long long i = 0; i <n; ++i) {
++d[0];
for (int j = 0; j + 1<len; ++j) {
if (d[j] == k) {
d[j] = 0;
d[j + 1] += 1;
++ans;
}
}
if (d[len- 1] == k) {
d[len - 1] = 0;
d[len] =1;
++len;
++ans;
}
}
cout << ans << endl;
return 0;
}
```
假设输入的 $n$ 是不超过 $2^{62}$ 的正整数，$k$ 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题：
23.
[CSP2020 入门级] 第 23 题
24.
[CSP2020 入门级] 第 24 题
25.
[CSP2020 入门级] 第 25 题
26.
[CSP2020 入门级] 第 26 题
27.
[CSP2020 入门级] 第 27 题
## 二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×。除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分)
28.
[CSP2020 入门级] 第 28 题
### 程序阅读题
```cpp
#include <algorithm>
#include <iostream>
using namespace std;
int n;
int d[50][2];
int ans;
void dfs(int n, int sum) {
if (n == 1) {
ans = max(sum, ans);
return;
}
for (int i = 1; i < n; ++i) {
int a = d[i - 1][0], b = d[i - 1][1];
int x = d[i][0], y = d[i][1];
d[i - 1][0] = a + x;
d[i - 1][1] = b + y;
for (int j = i; j < n - 1; ++j)
d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
int s = a + x + abs(b - y);
dfs(n - 1, sum + s);
for (int j = n - 1; j > i; --j)
d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
d[i - 1][0] = a, d[i - 1][1] = b;
d[i][0] = x, d[i][1] = y;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> d[i][0];
for (int i = 0; i < n;++i)
cin >> d[i][1];
ans = 0;
dfs(n, 0);
cout << ans << endl;
return 0;
}
```
假设输入的 $n$ 是不超过 $50$ 的正整数，`d[i][0]`、`d[i][1]` 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题：
29.
[CSP2020 入门级] 第 29 题
30.
[CSP2020 入门级] 第 30 题
31.
[CSP2020 入门级] 第 31 题
32.
[CSP2020 入门级] 第 32 题
33.
[CSP2020 入门级] 第 33 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
34.
[CSP2020 入门级] 第 34 题
35.
题目 950 不存在
36.
题目 951 不存在
37.
题目 952 不存在
38.
题目 953 不存在
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
39.
[CSP2020 入门级] 第 39 题
### 完善程序题
2.
（最小区间覆盖）给出 $n$ 个区间，第 $i$ 个区间的左右端点是 $[a_i,b_i]$。现在要在这些区间中选出若干个，使得区间 $[0, m]$ 被所选区间的并覆盖（即每一个 $0\leq i\leq m$ 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。
输入第一行包含两个整数 $n$ 和 $m$ （$1\le n \le 5000,1\le m \le 10^9$）
接下来 $n$ 行，每行两个整数 $a_i,b_i$ （$0\le a_i,b_i \le m$）。
提示：使用贪心法解决这个问题。先用 $O(n^2)$ 的时间复杂度排序，然后贪心选择这些区间。
试补全程序。
```cpp
#include <iostream>
using namespace std;
const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];
void sort() // 排序
{
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
if (①)
{
segment t = A[j];
②
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> A[i].a >> A[i].b;
sort();
int p = 1;
for (int i = 1; i < n; i++)
if (③)
A[p++] = A[i];
n = p;
int ans =0, r = 0;
int q = 0;
while (r < m)
{
while (④)
q++;
⑤;
ans++;
}
cout << ans << endl;
return 0;
}
```
40.
[CSP2020 入门级] 第 40 题
41.
[CSP2020 入门级] 第 41 题
42.
[CSP2020 入门级] 第 42 题
43.
[CSP2020 入门级] 第 43 题