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

 1 | #include <cstdio>
 2 | #include <cstring>
 3 | using namespace std;
 4 | char st[100];
 5 | int main() {
 6 |     scanf("%s", st);
 7 |     int n = strlen(st);
 8 |     for (int i = 1; i <= n; ++i) {
 9 |         if (n % i == 0) {
10 |             char c = st[i - 1];
11 |             if (c >= 'a')
12 |                 st[i - 1] = c - 'a' + 'A';
13 |         }
14 |     }
15 |     printf("%s", st);
16 |     return 0;
17 | }

 1 | #include <cstdio>
 2 | using namespace std;
 3 | int n, m;
 4 | int a[100], b[100];
 5 |
 6 | int main() {
 7 |     scanf("%d%d", &n, &m);
 8 |     for (int i = 1; i <= n; ++i)
 9 |         a[i] = b[i] = 0;
10 |     for (int i = 1; i <= m; ++i) {
11 |         int x, y;
12 |         scanf("%d%d", &x, &y);
13 |         if (a[x] < y && b[y] < x) {
14 |             if (a[x] > 0)
15 |                 b[a[x]] = 0;
16 |             if (b[y] > 0)
17 |                 a[b[y]] = 0;
18 |             a[x] = y;
19 |             b[y] = x;
20 |         }
21 |     }
22 |     int ans = 0;
23 |     for (int i = 1; i <= n; ++i) {
24 |         if (a[i] == 0)
25 |             ++ans;
26 |         if (b[i] == 0)
27 |             ++ans;
28 |     }
29 |     printf("%d\n", ans);
30 |     return 0;
31 | }

假设输入的 n 和 m 都是正整数，x 和 y 都是在 [1, n] 的范围内的整数，完成下面的判断题和单选题：

 1 | #include <iostream>
 2 | using namespace std;
 3 | const int maxn = 10000;
 4 | int n;
 5 | int a[maxn];
 6 | int b[maxn];
 7 | int f(int l, int r, int depth) {
 8 |     if (l > r)
 9 |         return 0;
10 |     int min = maxn, mink;
11 |     for (int i = l; i <= r; ++i) {
12 |         if (min > a[i]) {
13 |             min = a[i];
14 |             mink = i;
15 |         }
16 |     }
17 |     int lres = f(l, mink - 1, depth + 1);
18 |     int rres = f(mink + 1, r, depth + 1);
19 |     return lres + rres + depth * b[mink];
20 | }
21 | int main() {
22 |     cin >> n;
23 |     for (int i = 0; i < n; ++i) {
24 |         cin >> a[i];
25 |     }
26 |     for (int i = 0; i < n; ++i) {
27 |         cin >> b[i];
28 |     }
29 |     cout << f(0, n - 1, 1) << endl;
30 |     return 0;
31 | }
32 | 判断题

（矩阵变幻）有一个奇幻的矩阵，在不停的变幻，其变幻方式为：数字0变成矩阵 $\begin{bmatrix}0 & 0 \\ 0 & 1\end{bmatrix}$，数字1变成矩阵 $\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}$。最初该矩阵只有一个元素0，变幻n次后，矩阵会变成什么样？

例如，矩阵最初为： $[0]$；矩阵变幻1次后： $\begin{bmatrix}0 & 0 \\ 0 & 1\end{bmatrix}$；矩阵变幻2次后：

$$\begin{bmatrix}{{{0}}}&{{{0}}}&{{{0}}}&{{{0}}} \\{{{0}}}&{{{1}}}&{{{0}}}&{{{1}}} \\{{{0}}}&{{{0}}}&{{{1}}}&{{{1}}} \\{{{0}}}&{{{1}}}&{{{1}}}&{{{0}}}\end{bmatrix}。$$输入一行一个不超过 10 的正整数 n。输出变幻 n 次后的矩阵。

试补全程序。

提示：

“<<”表示二进制左移运算符，例如$(11)_2<<2=(1100)_2$;

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

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;
int res[max_size][max_size];
void recursive(int x, int y, int n, int t) {
    if (n == 0) {
        res[x][y] = ①;
        return;
    }
    int step = 1 << (n - 1);
    recursive(②, n - 1, t);
    recursive(x, y + step, n - 1, t);
    recursive(x + step, y, n - 1, t);
    recursive(③, n - 1, !t);
}
int main() {
    scanf("%d", &n);
    recursive(0, 0, ④);
    int size = ⑤;
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j)
            printf("%d", res[i][j]);
        puts("");
    }
    return 0;
}

（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将 n 对 10000 以内的整数，从小到大排序。

例如有三对整数（3, 4）、（2, 4）、（3, 3），那么排序之后应该是 （2, 4）、（3, 3）、（3, 4）。 输入第一行为 n，接下来 n 行，第 i 行有两个数 a[i] 和 b[i]，分别表示第 i 对整数的第一关键字和第二关键字。 从小到大排序后输出。

数据范围 $1 \leq n \leq 10^{7}, 1 \leq a[i], b[i] \leq 10^{4}$。

提示：应先对第二关键字排序，再对第一关键字排序。数组 ord[] 存储第二关键字排序的结果，数组 res[] 存储双关键字排序的结果。 试补全程序。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;

int n;
unsigned a[maxn], b[maxn], res[maxn], ord[maxn];
unsigned cnt[maxs + 1];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &a[i], &b[i]);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ①; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 记录初步排序结果

    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④; // 记录最终排序结果
    for (int i = 0; i < n; ++i)
        printf("%d %d\\n", ⑤);
    return 0;
}