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

 1 | #include <iostream>
 2 | using namespace std;
 3 |
 4 | int n;
 5 | int a[1000];
 6 |
 7 | int f(int x)
 8 | {
 9 |     int ret = 0;
10 |     for (; x; x &= x - 1) ret++;
11 |     return ret;
12 | }
13 |
14 | int g(int x)
15 | {
16 |     return x & -x;
17 | }
18 |
19 | int main()
20 | {
21 |     cin >> n;
22 |     for (int i = 0; i < n; i++) cin >> a[i];
23 |     for (int i = 0; i < n; i++)
24 |         cout << f(a[i]) + g(a[i]) << ' ';
25 |     cout << endl;
26 |     return 0;
27 | }

 1 | #include <iostream>
 2 | #include <string>
 3 | using namespace std;
 4 |
 5 | char base[64];
 6 | char table[256];
 7 |
 8 | void init()
 9 | {
10 |     for (int i = 0; i < 26; i++) base[i] = 'A' + i;
11 |     for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
12 |     for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
13 |     base[62] = '+', base[63] = '/';
14 |
15 |     for (int i = 0; i < 256; i++) table[i] = 0xff;
16 |     for (int i = 0; i < 64; i++) table[base[i]] = i;
17 |     table['='] = 0;
18 | }
19 |
20 | string decode(string str)
21 | {
22 |     string ret;
23 |     int i;
24 |     for (i = 0; i < str.size(); i += 4) {
25 |         ret += table[str[i]] << 2 | table[str[i + 1]] >> 4;
26 |         if (str[i + 2] != '=')
27 |             ret += (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
28 |         if (str[i + 3] != '=')
29 |             ret += table[str[i + 2]] << 6 | table[str[i + 3]];
30 |     }
31 |     return ret;
32 | }
33 |
34 | int main()
35 | {
36 |     init();
37 |     cout << int(table[0]) << endl;
38 |
39 |     string str;
40 |     cin >> str;
41 |     cout << decode(str) << endl;
42 |     return 0;
43 | }

 1 | #include <iostream>
 2 | using namespace std;
 3 |
 4 | const int n = 100000;
 5 | const int N = n + 1;
 6 |
 7 | int m;
 8 | int a[N], b[N], c[N], d[N];
 9 | int f[N], g[N];
10 |
11 | void init()
12 | {
13 |     f[1] = g[1] = 1;
14 |     for (int i = 2; i <= n; i++) {
15 |         if (!a[i]) {
16 |             b[m++] = i;
17 |             c[i] = 1, f[i] = 2;
18 |             d[i] = 1, g[i] = i + 1;
19 |         }
20 |         for (int j = 0; j < m && b[j] * i <= n; j++) {
21 |             int k = b[j];
22 |             a[i * k] = 1;
23 |             if (i % k == 0) {
24 |                 c[i * k] = c[i] + 1;
25 |                 f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
26 |                 d[i * k] = d[i];
27 |                 g[i * k] = g[i] * k + d[i];
28 |                 break;
29 |             }
30 |             else {
31 |                 c[i * k] = 1;
32 |                 f[i * k] = 2 * f[i];
33 |                 d[i * k] = g[i];
34 |                 g[i * k] = g[i] * (k + 1);
35 |             }
36 |         }
37 |     }
38 | }
39 |
40 | int main()
41 | {
42 |     init();
43 |
44 |     int x;
45 |     cin >> x;
46 |     cout << f[x] << ' ' << g[x] << endl;
47 |     return 0;
48 | }

假设输入的 x 是不超过 1000 的自然数，完成下面的判断题和单选题：

（Josephus 问题）有 n 个人围成一个圈，依次标号 0 至 n-1。从 0 号开始，依次 0,1,0,1,... 交替报数，报到 1 的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。

试补全模拟程序。

#include <iostream>

using namespace std;

const int MAXN = 1000000;
int F[MAXN];

int main() {
    int n;
    cin >> n;
    int i = 0, p = 0, c = 0;
    while (①) {
        if (F[i] == 0) {
            if (②) {
                F[i] = 1;
                ③;
            }
            ④;
        }
        ⑤;
    }
    int ans = -1;
    for (i = 0; i < n; i++)
        if (F[i] == 0)
            ans = i;
    cout << ans << endl;
    return 0;
}

（矩形计数）平面上有 n 个关键点，求有多少个四条边都和 x 轴或者 y 轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全校举算法。

#include <iostream>

using namespace std;

struct point {
    int x, y, id;
};

bool equals(point a, point b) {
    return a.x == b.x && a.y == b.y;
}

bool cmp(point a, point b) {
    return ①;
}

void sort(point A[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (cmp(A[j], A[j - 1])) {
                point t = A[j];
                A[j] = A[j - 1];
                A[j - 1] = t;
            }
}

int unique(point A[], int n) {
    int t = 0;
    for (int i = 0; i < n; i++)
        if (②)
            A[t++] = A[i];
    return t;
}

bool binary_search(point A[], int n, int x, int y) {
    point p;
    p.x = x;
    p.y = y;
    p.id = n;
    int a = 0, b = n - 1;
    while (a < b) {
        int mid = ③;
        if (④)
            a = mid + 1;
        else
            b = mid;
    }
    return equals(A[a], p);
}

const int MAXN = 1000;
point A[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> A[i].x >> A[i].y;
        A[i].id = i;
    }
    sort(A, n);
    n = unique(A, n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (⑤ && binary_search(A, n, A[i].x, A[j].y) &&
                binary_search(A, n, A[j].x, A[i].y)) {
                ans++;
            }
    cout << ans << endl;
    return 0;
}