2020 CCF CSP-J 第一轮（入门级 C++）

 1 | #include <cstdlib>
 2 | #include <iostream>
 3 | using namespace std;
 4 |
 5 | char encoder[26] = {'C', 'S', 'P', 0};
 6 | char decoder[26];
 7 | string st;
 8 |
 9 | int main() {
10 |     int k = 0;
11 |     for (int i = 0; i < 26; ++i)
12 |         if (encoder[i] != 0) ++k;
13 |     for (char x = 'A'; x <= 'Z'; ++x) {
14 |         bool flag = true;
15 |         for (int i = 0; i < 26; ++i)
16 |             if (encoder[i] == x) {
17 |                 flag = false;
18 |                 break;
19 |             }
20 |         if (flag) {
21 |             encoder[k] = x;
22 |             ++k;
23 |         }
24 |     }
25 |     for (int i = 0; i < 26; ++i)
26 |         decoder[encoder[i] - 'A'] = i + 'A';
27 |     cin >> st;
28 |     for (int i = 0; i < st.length(); ++i)
29 |         st[i] = decoder[st[i] - 'A'];
30 |     cout << st;
31 |     return 0;
32 | }

 1 | #include <iostream>
 2 | using namespace std;
 3 |
 4 | long long n, ans;
 5 | int k, len;
 6 | long long d[1000000];
 7 |
 8 | int main() {
 9 |     cin >> n >> k;
10 |     d[0] = 0;
11 |     len = 1;
12 |     ans = 0;
13 |     for (long long i = 0; i < n; ++i) {
14 |         ++d[0];
15 |         for (int j = 0; j + 1 < len; ++j) {
16 |             if (d[j] == k) {
17 |                 d[j] = 0;
18 |                 d[j + 1] += 1;
19 |                 ++ans;
20 |             }
21 |         }
22 |         if (d[len - 1] == k) {
23 |             d[len - 1] = 0;
24 |             d[len] = 1;
25 |             ++len;
26 |             ++ans;
27 |         }
28 |     }
29 |     cout << ans << endl;
30 |     return 0;
31 | }

假设输入的 n 是不超过 $2^{62}$ 的正整数，k 都是不超过 10000 的正整数，完成下面的判断题和单选题：

 1 | #include <algorithm>
 2 | #include <iostream>
 3 | using namespace std;
 4 |
 5 | int n;
 6 | int d[50][2];
 7 | int ans;
 8 |
 9 | void dfs(int n, int sum) {
10 |     if (n == 1) {
11 |         ans = max(sum, ans);
12 |         return;
13 |     }
14 |     for (int i = 1; i < n; ++i) {
15 |         int a = d[i - 1][0], b = d[i - 1][1];
16 |         int x = d[i][0], y = d[i][1];
17 |         d[i - 1][0] = a + x;
18 |         d[i - 1][1] = b + y;
19 |         for (int j = i; j < n - 1; ++j)
20 |             d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
21 |         int s = a + x + abs(b - y);
22 |         dfs(n - 1, sum + s);
23 |         for (int j = n - 1; j > i; --j)
24 |             d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
25 |         d[i - 1][0] = a, d[i - 1][1] = b;
26 |         d[i][0] = x, d[i][1] = y;
27 |     }
28 | }
29 |
30 | int main() {
31 |     cin >> n;
32 |     for (int i = 0; i < n; ++i)
33 |         cin >> d[i][0];
34 |     for (int i = 0; i < n; ++i)
35 |         cin >> d[i][1];
36 |     ans = 0;
37 |     dfs(n, 0);
38 |     cout << ans << endl;
39 |     return 0;
40 | }

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

（质因数分解）给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。

例如：输入 n=120，程序应该输出 2 2 2 3 5，表示 $120=2\times2\times2\times3\times5$。输入保证 $2\leq n\leq10^9$。提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。

试补全程序。

#include <stdio>
using namespace std;

int n, i;

int main() {
    scanf("%d", &n);
    for(i = ①; ② <= n; i++) {
        ③ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if(④)
        printf("%d ", ⑤);
    return 0;
}

（最小区间覆盖)给出 n 个区间，第 i 个区间的左右端点是 $[a_i, b_i]$。现在要在这些区间中选出若干个，使得区间 $[0, m]$被所选区间的并覆盖（即每一个$\theta \leq i \leq m$都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 n 和 m （$1 \leqslant n \leqslant 5000, 1 \leqslant m \leqslant 10^{9}$）。

接下来 n 行，每行两个整数 $a_i$， $b_i$（ $\theta \leqslant a_i$， $b_i \leqslant m$）。

提示：使用贪心法解决这个问题。先用 $\theta(n^{2})$ 的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

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