开始整卷作答
按大题分页，翻页自动存草稿，做完统一交卷。
## 一、单项选择题（共 $15$ 题，每题 $2$ 分，共 $30$ 分）
第 1–15 题 · 共 15 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分）
第 16–16 题 · 共 1 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分）
1.
```cpp
#include <iostream>
using namespace std;
int n;
int d[1000];
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> d[i];
int ans = -1;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (d[i] < d[j])
ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
cout << ans;
return 0;
}
```
假设输入的 $n$ 和 $d[i]$ 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题：
第 17–21 题 · 共 5 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分）
第 22–22 题 · 共 1 题
2.
```cpp
#include <iostream>
#include <cstdlib>
using namespace std;
int n;
int d[10000];
int find(int L, int R, int k) {
int x = rand() % (R - L + 1) + L;
swap(d[L], d[x]);
int a = L + 1, b = R;
while (a < b) {
while (a < b && d[a] < d[L])
++a;
while (a < b && d[b] >= d[L])
--b;
swap(d[a], d[b]);
}
if (d[a] < d[L])
++a;
if (a - L == k)
return d[L];
if (a - L < k)
return find(a, R, k - (a - L));
return find(L + 1, a - 1, k);
}
int main() {
int k;
cin >> n;
cin >> k;
for (int i = 0; i < n; ++i)
cin >> d[i];
cout << find(0, n - 1, k);
return 0;
}
```
假设输入的 $n,k$ 和 $d[i]$ 都是不超过 $10000$ 的正整数，且 $k$ 不超过 $n$，并假设 `rand()` 函数产生的是均匀的随机数，完成下面的判断题和单选题：
第 23–27 题 · 共 5 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分）
第 28–28 题 · 共 1 题
3.
```cpp
#include <iostream>
#include <queue>
using namespace std;
const int maxl = 20000000;
class Map {
struct item {
string key; int value;
} d[maxl];
int cnt;
public:
int find(string x) {
for (int i = 0; i < cnt; ++i)
if (d[i].key == x)
return d[i].value;
return -1;
}
static int end() { return -1; }
void insert(string k, int v) {
d[cnt].key = k; d[cnt++].value = v;
}
} s[2];
class Queue {
string q[maxl];
int head, tail;
public:
void pop() { ++head; }
string front() { return q[head + 1]; }
bool empty() { return head == tail; }
void push(string x) { q[++tail] = x; }
} q[2];
string st0, st1;
int m;
string LtoR(string s, int L, int R) {
string t = s;
char tmp = t[L];
for (int i = L; i < R; ++i)
t[i] = t[i + 1];
t[R] = tmp;
return t;
}
string RtoL(string s, int L, int R) {
string t = s;
char tmp = t[R];
for (int i = R; i > L; --i)
t[i] = t[i - 1];
t[L] = tmp;
return t;
}
bool check(string st , int p, int step) {
if (s[p].find(st) != s[p].end())
return false;
++step;
if (s[p ^ 1].find(st) == s[p].end()) {
s[p].insert(st, step);
q[p].push(st);
return false;
}
cout << s[p ^ 1].find(st) + step << endl;
return true;
}
int main() {
cin >> st0 >> st1;
int len = st0.length();
if (len != st1.length()) {
cout << -1 << endl;
return 0;
}
if (st0 == st1) {
cout << 0 << endl;
return 0;
}
cin >> m;
s[0].insert(st0, 0); s[1].insert(st1, 0);
q[0].push(st0); q[1].push(st1);
for (int p = 0;
!(q[0].empty() && q[1].empty());
p ^= 1) {
string st = q[p].front(); q[p].pop();
int step = s[p].find(st);
if ((p == 0 &&
(check(LtoR(st, m, len - 1), p, step) ||
check(RtoL(st, 0, m), p, step)))
||
(p == 1 &&
(check(LtoR(st, 0, m), p, step) ||
check(RtoL(st, m, len - 1), p, step))))
return 0;
}
cout << -1 << endl;
return 0;
}
```
第 29–33 题 · 共 5 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
第 34–34 题 · 共 1 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
1.（分数背包）小 S 有 $n$ 块蛋糕，编号从 $1$ 到 $n$。第 $i$ 块蛋糕的价值是 $w_i$，体积是 $v_i$。他有一个大小为 $B$ 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 $B$。他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $a(0<a<1)$，并将一块价值是 $w$，体积为 $v$ 的蛋糕切割成两 块，其中一块的价值是 $a\times w$，体积是 $a\times v$，另一块的价值是$(1-a)\times w$，体积是 $(1-a)\times v$。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如 $n=3,B=8$，三块蛋糕的价值分别是 $4,4,2$，体积分别是 $5,3,2$。那么最优的方案就是将体积为 $5$ 的蛋糕切成两份，一份体积是 $3$，价值是 $2.4$，另一份体积是 $2$，价值是 $1.6$，然后把体积是 $3$ 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 $8.4$，故程序输出 $\dfrac{42}{5}$。
输入的数据范围为：$1\leq n\leq 1000$，$1\leq B\leq 10^5$，$1\leq w_i,v_i\leq 100$。
提示：将所有的蛋糕按照性价比 $\dfrac{w_i}{v_i}$ 可从大到小排序后进行贪心选择。
试补全程序。
```cpp
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n, B, w[maxn], v[maxn];
int gcd(int u, int v) {
if (v == 0)
return u;
return gcd(v, u % v);
}
void print(int w, int v) {
int d = gcd(w, v);
w = w / d;
v = v / d;
if (v == 1)
printf("%d\n", w);
else
printf("%d/%d\n" w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("%d %d" &n, &B);
for (int i = 1; i <= n; i ++) {
scanf("%d %d", &w[i], &v[i]);
}
for (int i = 1; i < n; i ++)
for (int j = 1; j < n; j ++)
if (①) {
swap(w[j], w[j + 1]);
swap(v[j], v[j + 1]);
}
int curV, curW;
if (②) {
③
} else {
print(B * w[1] , v[1]);
return 0;
}
for (int i = 2; i <= n; i ++)
if (curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print (④);
return 0;
}
print(⑤);
return 0;
}
```
第 35–38 题 · 共 4 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
第 39–39 题 · 共 1 题
2.（最优子序列）取 $m = 16$，给出长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n(0 \le a_i < 2^m)$。对于一个二进制数 $x$，定义其分值 $w(x)$ 为 $x + \operatorname {popcnt}(x)$，其中 $\operatorname{popcnt}(x)$ 表示 $x$ 二进制表示中 $1$ 的个数。对于一个子序列 $b_1,b_2,\dots,b_k$，定义其子序列分值 $S$ 为 $w(b_1 \oplus b_2) + w(b_2 \oplus b_3) + w(b_3 \oplus b_4) + \cdots + w(b_{k-1} \oplus b_k)$。其中 $\oplus$ 表示按位异或。对于空子序列，规定其子序列分值为 $0$ 求一个子序列使得其子序列分值最大，输出这个最大值。
输入第一行包含一个整数 $n(1 \le n \le 40000)$ 接下来一行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。
提示：考虑优化朴素的动态规划算法，将前 $\dfrac{m}{2}$ 位和后 $\dfrac{m}{2}$ 位分开计算。
`Max[x][y]` 表示当前的子序列下一个位置的高 $8$ 位是 $x$、最后一个位置的低 $8$ 位是 $y$ 时的最大价值。
试补全程序。
```cpp
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];
int w(int x)
{
int s = x;
while(x)
{
①;
s++;
}
return s;
}
void to_max(LL &x, LL y)
{
if(x < y)
x = y;
}
int main()
{
int n;
LL ans = 0;
cin >> n;
for(int x = 0; x <= MS; x++)
for(int y = 0; y <= MS; y++)
Max[x][y] = -INF;
for(int i = 1; i <= n ; i++)
{
LL a;
cin >> a;
int x = ② , y = a & MS;
LL v = ③;
for(int z = 0; z < = MS; z++)
to_max(v, ④);
for(int z = 0; z < = MS; z++)
⑤;
to_max(ans , v);
}
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 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分）
1.
```cpp
#include <iostream>
using namespace std;
int n;
int d[1000];
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> d[i];
int ans = -1;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (d[i] < d[j])
ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
cout << ans;
return 0;
}
```
假设输入的 $n$ 和 $d[i]$ 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题：
17.
[CSP2020 提高级] 第 17 题
18.
[CSP2020 提高级] 第 18 题
19.
[CSP2020 提高级] 第 19 题
20.
[CSP2020 提高级] 第 20 题
21.
[CSP2020 提高级] 第 21 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分）
22.
[CSP2020 提高级] 第 22 题
2.
```cpp
#include <iostream>
#include <cstdlib>
using namespace std;
int n;
int d[10000];
int find(int L, int R, int k) {
int x = rand() % (R - L + 1) + L;
swap(d[L], d[x]);
int a = L + 1, b = R;
while (a < b) {
while (a < b && d[a] < d[L])
++a;
while (a < b && d[b] >= d[L])
--b;
swap(d[a], d[b]);
}
if (d[a] < d[L])
++a;
if (a - L == k)
return d[L];
if (a - L < k)
return find(a, R, k - (a - L));
return find(L + 1, a - 1, k);
}
int main() {
int k;
cin >> n;
cin >> k;
for (int i = 0; i < n; ++i)
cin >> d[i];
cout << find(0, n - 1, k);
return 0;
}
```
假设输入的 $n,k$ 和 $d[i]$ 都是不超过 $10000$ 的正整数，且 $k$ 不超过 $n$，并假设 `rand()` 函数产生的是均匀的随机数，完成下面的判断题和单选题：
23.
[CSP2020 提高级] 第 23 题
24.
[CSP2020 提高级] 第 24 题
25.
[CSP2020 提高级] 第 25 题
26.
[CSP2020 提高级] 第 26 题
27.
[CSP2020 提高级] 第 27 题
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分）
28.
[CSP2020 提高级] 第 28 题
3.
```cpp
#include <iostream>
#include <queue>
using namespace std;
const int maxl = 20000000;
class Map {
struct item {
string key; int value;
} d[maxl];
int cnt;
public:
int find(string x) {
for (int i = 0; i < cnt; ++i)
if (d[i].key == x)
return d[i].value;
return -1;
}
static int end() { return -1; }
void insert(string k, int v) {
d[cnt].key = k; d[cnt++].value = v;
}
} s[2];
class Queue {
string q[maxl];
int head, tail;
public:
void pop() { ++head; }
string front() { return q[head + 1]; }
bool empty() { return head == tail; }
void push(string x) { q[++tail] = x; }
} q[2];
string st0, st1;
int m;
string LtoR(string s, int L, int R) {
string t = s;
char tmp = t[L];
for (int i = L; i < R; ++i)
t[i] = t[i + 1];
t[R] = tmp;
return t;
}
string RtoL(string s, int L, int R) {
string t = s;
char tmp = t[R];
for (int i = R; i > L; --i)
t[i] = t[i - 1];
t[L] = tmp;
return t;
}
bool check(string st , int p, int step) {
if (s[p].find(st) != s[p].end())
return false;
++step;
if (s[p ^ 1].find(st) == s[p].end()) {
s[p].insert(st, step);
q[p].push(st);
return false;
}
cout << s[p ^ 1].find(st) + step << endl;
return true;
}
int main() {
cin >> st0 >> st1;
int len = st0.length();
if (len != st1.length()) {
cout << -1 << endl;
return 0;
}
if (st0 == st1) {
cout << 0 << endl;
return 0;
}
cin >> m;
s[0].insert(st0, 0); s[1].insert(st1, 0);
q[0].push(st0); q[1].push(st1);
for (int p = 0;
!(q[0].empty() && q[1].empty());
p ^= 1) {
string st = q[p].front(); q[p].pop();
int step = s[p].find(st);
if ((p == 0 &&
(check(LtoR(st, m, len - 1), p, step) ||
check(RtoL(st, 0, m), p, step)))
||
(p == 1 &&
(check(LtoR(st, 0, m), p, step) ||
check(RtoL(st, m, len - 1), p, step))))
return 0;
}
cout << -1 << endl;
return 0;
}
```
29.
[CSP2020 提高级] 第 29 题
30.
[CSP2020 提高级] 第 30 题
31.
[CSP2020 提高级] 第 31 题
32.
[CSP2020 提高级] 第 32 题
33.
[CSP2020 提高级] 第 33 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
34.
[CSP2020 提高级] 第 34 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
1.（分数背包）小 S 有 $n$ 块蛋糕，编号从 $1$ 到 $n$。第 $i$ 块蛋糕的价值是 $w_i$，体积是 $v_i$。他有一个大小为 $B$ 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 $B$。他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $a(0<a<1)$，并将一块价值是 $w$，体积为 $v$ 的蛋糕切割成两 块，其中一块的价值是 $a\times w$，体积是 $a\times v$，另一块的价值是$(1-a)\times w$，体积是 $(1-a)\times v$。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如 $n=3,B=8$，三块蛋糕的价值分别是 $4,4,2$，体积分别是 $5,3,2$。那么最优的方案就是将体积为 $5$ 的蛋糕切成两份，一份体积是 $3$，价值是 $2.4$，另一份体积是 $2$，价值是 $1.6$，然后把体积是 $3$ 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 $8.4$，故程序输出 $\dfrac{42}{5}$。
输入的数据范围为：$1\leq n\leq 1000$，$1\leq B\leq 10^5$，$1\leq w_i,v_i\leq 100$。
提示：将所有的蛋糕按照性价比 $\dfrac{w_i}{v_i}$ 可从大到小排序后进行贪心选择。
试补全程序。
```cpp
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n, B, w[maxn], v[maxn];
int gcd(int u, int v) {
if (v == 0)
return u;
return gcd(v, u % v);
}
void print(int w, int v) {
int d = gcd(w, v);
w = w / d;
v = v / d;
if (v == 1)
printf("%d\n", w);
else
printf("%d/%d\n" w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("%d %d" &n, &B);
for (int i = 1; i <= n; i ++) {
scanf("%d %d", &w[i], &v[i]);
}
for (int i = 1; i < n; i ++)
for (int j = 1; j < n; j ++)
if (①) {
swap(w[j], w[j + 1]);
swap(v[j], v[j + 1]);
}
int curV, curW;
if (②) {
③
} else {
print(B * w[1] , v[1]);
return 0;
}
for (int i = 2; i <= n; i ++)
if (curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print (④);
return 0;
}
print(⑤);
return 0;
}
```
35.
[CSP2020 提高级] 第 35 题
36.
[CSP2020 提高级] 第 36 题
37.
[CSP2020 提高级] 第 37 题
38.
[CSP2020 提高级] 第 38 题
## 三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）
39.
[CSP2020 提高级] 第 39 题
2.（最优子序列）取 $m = 16$，给出长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n(0 \le a_i < 2^m)$。对于一个二进制数 $x$，定义其分值 $w(x)$ 为 $x + \operatorname {popcnt}(x)$，其中 $\operatorname{popcnt}(x)$ 表示 $x$ 二进制表示中 $1$ 的个数。对于一个子序列 $b_1,b_2,\dots,b_k$，定义其子序列分值 $S$ 为 $w(b_1 \oplus b_2) + w(b_2 \oplus b_3) + w(b_3 \oplus b_4) + \cdots + w(b_{k-1} \oplus b_k)$。其中 $\oplus$ 表示按位异或。对于空子序列，规定其子序列分值为 $0$ 求一个子序列使得其子序列分值最大，输出这个最大值。
输入第一行包含一个整数 $n(1 \le n \le 40000)$ 接下来一行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。
提示：考虑优化朴素的动态规划算法，将前 $\dfrac{m}{2}$ 位和后 $\dfrac{m}{2}$ 位分开计算。
`Max[x][y]` 表示当前的子序列下一个位置的高 $8$ 位是 $x$、最后一个位置的低 $8$ 位是 $y$ 时的最大价值。
试补全程序。
```cpp
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];
int w(int x)
{
int s = x;
while(x)
{
①;
s++;
}
return s;
}
void to_max(LL &x, LL y)
{
if(x < y)
x = y;
}
int main()
{
int n;
LL ans = 0;
cin >> n;
for(int x = 0; x <= MS; x++)
for(int y = 0; y <= MS; y++)
Max[x][y] = -INF;
for(int i = 1; i <= n ; i++)
{
LL a;
cin >> a;
int x = ② , y = a & MS;
LL v = ③;
for(int z = 0; z < = MS; z++)
to_max(v, ④);
for(int z = 0; z < = MS; z++)
⑤;
to_max(ans , v);
}
cout << ans << endl;
return 0;
}
```
40.
[CSP2020 提高级] 第 40 题
41.
[CSP2020 提高级] 第 41 题
42.
[CSP2020 提高级] 第 42 题
43.
[CSP2020 提高级] 第 43 题