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

 1 | #include <cstdio>
 2 | using namespace std;
 3 | int n;
 4 | int a[100];
 5 | int main() {
 6 |     scanf("%d", &n);
 7 |     for (int i = 1; i <= n; ++i)
 8 |         scanf("%d", &a[i]);
 9 |     int ans = 1;
10 |     for (int i = 1; i <= n; ++i) {
11 |         if (i > 1 && a[i] < a[i - 1])
12 |             ans = i;
13 |         while (ans < n && a[i] >= a[ans + 1])
14 |             ++ans;
15 |         printf("%d\n", ans);
16 |     }
17 |     return 0;
18 | }

 1 | #include <iostream>
 2 | using namespace std;
 3 |
 4 | const int maxn = 1000;
 5 | int n;
 6 | int fa[maxn], cnt[maxn];
 7 | int getRoot(int v) {
 8 |     if (fa[v] == v) return v;
 9 |     return getRoot(fa[v]);
10 | }
11 |
12 | int main() {
13 |     cin >> n;
14 |     for (int i = 0; i < n; ++i) {
15 |         fa[i] = i;
16 |         cnt[i] = 1;
17 |     }
18 |     int ans = 0;
19 |     for (int i = 0; i < n - 1; ++i) {
20 |         int a, b, x, y;
21 |         cin >> a >> b;
22 |         x = getRoot(a);
23 |         y = getRoot(b);
24 |         ans += cnt[x] * cnt[y];
25 |         fa[x] = y;
26 |         cnt[y] += cnt[x];
27 |     }
28 |     cout << ans << endl;
29 |     return 0;
30 | }

3. 本题 t 是 s 的子序列的意思是：从 s 中删去若干个字符，可以得到 t；特别的，如果 s = t，那么 t 也是 s 的子序列；空串是任何串的子序列。例如 “acd” 是 “abcde” 的子序列，“acd” 是 “acd” 的子序列，但 “adc” 不是 “abcde” 的子序列。

s[x..y] 表示 s[x] ... s[y] 共 y - x + 1 个字符构成的字符串，若 x > y 则 s[x..y] 是空串。t[x..y] 同理。

 1 | #include <iostream>
 2 | #include <string>
 3 | using namespace std;
 4 | const int max1 = 202;
 5 | string s, t;
 6 | int pre[max1], suf[max1];
 7 |
 8 | int main() {
 9 | cin >> s >> t;
10 | int slen = s.length(), tlen = t.length();
11 | for (int i = 0, j = 0; i < slen; ++i) {
12 | if (j < tlen && s[i] == t[j]) ++j;
13 | pre[i] = j; // t[0..j-1] 是 s[0..i] 的子序列
14 | }
15 | for (int i = slen - 1, j = tlen - 1; i >= 0; --i) {
16 | if (j >= 0 && s[i] == t[j]) --j;
17 | suf[i] = j; // t[j+1..tlen-1] 是 s[i..slen-1] 的子序列
18 | }
19 | suf[slen] = tlen - 1;
20 | int ans = 0;
21 |
22 | for (int i = 0, j = 0, tmp = 0; i <= slen; ++i) {
23 | while (j <= slen && tmp >= suf[j] + 1) ++j;
24 | ans = max(ans, j - i - 1);
25 | tmp = pre[i];
26 | }
27 | cout << ans << endl;
28 | return 0;
29 | }

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

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

输入第一行有两个数，分别为新技术个数 $n\left(1 \leq n \leq 10^{3}\right)$，以及已有经验值 $\left(\leq 10^{7}\right)$。

接下来 n 行。第 i 行的两个正整数，分别表示学习第 i 个技术所需的最低经验值（≤ 10⁷），以及学会第 i 个技术后可获得的经验值（≤ 10⁴）。

接下来 n 行。第 i 行的第一个数 $m_i$（ $0 \leq m_i < n$），表示第 i 个技术的相关技术数量。紧跟着 m 个两两不同的数，表示第 i 个技术的相关技术编号。输出最多能学会的新技术个数。

下面的程序以 $O(n^{2})$的时间复杂度完成这个问题，试补全程序。

#include <cstdio>
using namespace std;
const int maxn = 1001;

int n;
int cnt[maxn];
int child[maxn][maxn];
int unlock[maxn];
int points;
int threshold[maxn], bonus[maxn];

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;
}

2. （取石子）Alice 和 Bob 两个人在玩取石子游戏。他们制定了 n 条取石子的规则，第 i 条规则为：如果剩余石子的个数大于等于 a[i] 且大于等于 b[i]，那么他们可以取走 b[i] 个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了。一开始石子有 m 个。请问先取石子的人是否有必胜的方法？

输入第一行有两个正整数，分别为规则个数 n（1 ≤ n ≤ 64），以及石子个数 m（≤ 10⁷）。

接下来 n 行。第 i 行有两个正整数 a[i] 和 b[i]。（1 ≤ a[i] ≤ 10⁷, 1 ≤ b[i] ≤ 64）

如果先取石子的人必胜，那么输出 “Win”，否则输出 “Loss”。

提示:

可以使用动态规划解决这个问题。由于 b[i] 不超过 64，所以可以使用 64 位无符号整数去压缩必要的状态。

status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。

试补全程序。

代码说明：

“~”表示二进制补码运算符，它将每个二进制位的0变为1、1变为0；

而 “^” 表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 0，反之为 1。

ull 标识符表示它前面的数字是 unsigned long long 类型。

#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;
}