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

 1 | #include <iostream>
 2 | using namespace std;
 3 |
 4 | int n;
 5 | int d[1000];
 6 |
 7 | int main() {
 8 |     cin >> n;
 9 |     for (int i = 0; i < n; ++i)
10 |         cin >> d[i];
11 |     int ans = -1;
12 |     for (int i = 0; i < n; ++i)
13 |         for (int j = 0; j < n; ++j)
14 |             if (d[i] < d[j])
15 |                 ans = max(ans, d[i] + d[j] - (d[i] & d[j]);
16 |                 cout << ans;
17 |                 return 0;
18 | }

假设输入的 n 和 d[i]都是不超过 10000 的正整数，完成下面的判断题和单选题：

 1 | #include <iostream>
 2 | #include <cstdlib>
 3 | using namespace std;
 4 |
 5 | int n;
 6 | int d[10000];
 7 |
 8 | int find(int L, int R, int k) {
 9 |     int x = rand() % (R - L + 1) + L;
10 |     swap(d[L], d[x]);
11 |     int a = L + 1, b = R;
12 |     while (a < b) {
13 |         while (a < b && d[a] < d[L])
14 |             ++a;
15 |         while (a < b && d[b] >= d[L])
16 |             --b;
17 |         swap(d[a], d[b]);
18 |     }
19 |     if (d[a] < d[L])
20 |         ++a;
21 |     if (a - L == k)
22 |         return d[L];
23 |     if (a - L < k)
24 |         return find(a, R, k - (a - L));
25 |     return find(L + 1, a - 1, k);
26 | }
27 |
28 | int main() {
29 |     int k;
30 |     cin >> n;
31 |     cin >> k;
32 |     for (int i = 0; i < n; ++i)
33 |         cin >> d[i];
34 |     cout << find(0, n - 1, k);
35 |     return 0;
36 | }

假设输入的 n，k 和 d[i] 都是不超过 10000 的正整数，且 k 不超过 n，并假设 rand() 函数产生的是均匀的随机数，完成下面的判断题和单选题：

  1 | #include <iostream>
  2 | #include <queue>
  3 |
  4 | using namespace std;
  5 |
  6 | const int maxl = 2000000000;
  7 |
  8 | class Map {
  9 |     struct item {
 10 |         string key; int value;
 11 |     } d[maxl];
 12 |     int cnt;
 13 |     public:
 14 |     int find(string x) {
 15 |         for (int i = 0; i < cnt; ++i)
 16 |             if (d[i].key == x)
 17 |                 return d[i].value;
 18 |         }
 19 |         return -1;
 20 |     }
 21 | }
 22 |
 23 | }
 24 | static int end() { return -1; }
 25 | void insert(string k, int v) {
 26 | d[cnt].key = k; d[cnt++].value = v;
 27 | }
 28 | } s[2];
 29 |
 30 | class Queue {
 31 | string q[maxl];
 32 | int head, tail;
 33 | public:
 34 | void pop() { ++head; }
 35 | string front() { return q[head + 1]; }
 36 | bool empty() { return head == tail; }
 37 | void push(string x) { q[++tail] = x; }
 38 | } q[2];
 39 |
 40 | string st0, st1;
 41 | int m;
 42 |
 43 | string ltoR(string s, int L, int R) {
 44 | string t = s;
 45 | char tmp = t[L];
 46 | for (int i = L; i < R; ++i)
 47 | t[i] = t[i + 1];
 48 | t[R] = tmp;
 49 | return t;
 50 | }
 51 |
 52 | string RtoL(string s, int L, int R) {
 53 | string t = s;
 54 | char tmp = t[R];
 55 | for (int i = R; i > L; --i)
 56 | t[i] = t[i - 1];
 57 | t[L] = tmp;
 58 | return t;
 59 | }
 60 |
 61 | bool check(string st, int p, int step) {
 62 | if (s[p].find(st) != s[p].end())
 63 | return false;
 64 | ++step;
 65 | if (s[p ^ 1].find(st) == s[p].end()) {
 66 |
 67 | s[p].insert(st, step);
 68 | q[p].push(st);
 69 | return false;
 70 | }
 71 | cout << s[p ^ 1].find(st) + step << endl;
 72 | return true;
 73 | }
 74 |
 75 | int main() {
 76 | cin >> st0 >> st1;
 77 | int len = st0.length();
 78 | if (len != st1.length()) {
 79 | cout << -1 << endl;
 80 | return 0;
 81 | }
 82 | if (st0 == st1) {
 83 | cout << 0 << endl;
 84 | return 0;
 85 | }
 86 | cin >> m;
 87 | s[0].insert(st0, 0); s[1].insert(st1, 0);
 88 | q[0].push(st0); q[1].push(st1);
 89 | for (int p = 0;
 90 |     ! (q[0].empty() && q[1].empty());
 91 | p ^ = 1) {
 92 | string st = q[p].front(); q[p].pop();
 93 | int step = s[p].find(st);
 94 | if ((p == 0 &&
 95 |     (check(LtoR(st, m, len - 1), p, step) ||
 96 |     check(RtoL(st, 0, m), p, step))) ||
 97 |     ||
 98 |     (p == 1 &&
 99 |     (check(LtoR(st, 0, m), p, step) ||
100 |     check(RtoL(st, m, len - 1), p, step))))
101 |     return 0;
102 | }
103 | cout << -1 << endl;
104 | return 0;
105 | }

1. （分数背包）小 S 有 n 块蛋糕，编号从 1 到 n。第 i 块蛋糕的价值是 $w_i$，体积是 $v_i$。他有一个大小为 B 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 B。

他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $\alpha$（ $\theta < \alpha < 1$），并将一块价值是 w，体积为 v 的蛋糕切割成两块，其中一块的价值是 $\alpha \cdot w$，体积是 $\alpha \cdot v$，另一块的价值是 $(1 - \alpha) \cdot w$，体积是 $(1 - \alpha) \cdot v$。他可以重复无限次切割操作。

现要求编程输出最大可能的价值，以分数的形式输出。

比如 n=3，B=8，三块蛋糕的价值分别是 4、4、2，体积分别是 5、3、2。那么最优的方案就是将体积为 5 的蛋糕切成两份，一份体积是 3，价值是 2.4，另一份体积是 2，价值是 1.6，然后把体积是 3 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 8.4，故程序输出 42/5。

输入的数据范围为： $1 \leqslant n \leqslant 1000$， $1 \leqslant B \leqslant 10^5$； $1 \leqslant w_i, v_i \leqslant 100$。 提示：将所有的蛋糕按照性价比 $w_i/v_i$从大到小排序后进行贪心选择。 试补全程序。

#include <cstdio>
using namespace std;
03
const int maxn = 1005;
05
int n, B, w[maxn], v[maxn];
07
int gcd(int u, int v) {
if(v == 0)
return u;
return gcd(v, u % v);
}
13
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);
}
23
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
27
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;
}

2. （最优子序列）取 m = 16，给出长度为 n 的整数序列 $a_1, a_2, \cdots, a_n (0 \leq a_i < 2^m)$。对于一个二进制数 x，定义其分值 $w(x)$ 为 $x + \text{popcnt}(x)$，其中 $\text{popcnt}(x)$ 表示 x 二进制表示中 1 的个数。对于一个子序列 $b_1, b_2, \cdots, 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$ 表示按位异或。对于空子序列，规定其子序列分值为 $\theta$。求一个子序列使得其子序列分值最大，输出这个最大值。

输入第一行包含一个整数 $n (1 \leq n \leq 40000)$。接下来一行包含 n 个整数 $a_1, a_2, \cdots, a_n$。

提示：考虑优化朴素的动态规划算法，将前 $\frac{m}{2}$ 位和后 $\frac{m}{2}$ 位分开计算。

Max[x][y] 表示当前的子序列下一个位置的高 8 位是 x、最后一个位置的低 8 位是 y 时的最大价值。

试补全程序。

#include <iostream>
02
using namespace std;
04
typedef long long LL;
06
const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 10000000000000000LL;
LL Max[MS + 4][MS + 4];
10
int w(int x)
{
int s = x;
while (x)
    {
①;
s++;
}
return s;
}
20
21
void to_max(LL &x, LL y)
{
}

if (x < y)
x = y;
}
27
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;
}