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

（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

 1 | #include <algorithm>
 2 | #include <cstdio>
 3 | #include <cstring>
 4 | inline int gcd(int a, int b) {
 5 |     if (b == 0)
 6 |         return a;
 7 |     return gcd(b, a % b);
 8 | }
 9 | int main() {
10 |     int n;
11 |     scanf("%d", &n);
12 |     int ans = 0;
13 |     for (int i = 1; i <= n; ++i) {
14 |         for (int j = i + 1; j <= n; ++j) {
15 |             for (int k = j + 1; k <= n; ++k) {
16 |                 if (gcd(i, j) == 1 && gcd(j, k) == 1 && gcd(i, k) == 1) {
17 |                     ++ans;
18 |                 }
19 |             }
20 |         }
21 |     }
22 |     printf("%d\n", ans);
23 |     return 0;
24 | }

 1 | #include <algorithm>
 2 | #include <cstdio>
 3 | #include <cstring>
 4 | #define ll long long
 5 | int n, k;
 6 | int a[200007];
 7 | int ans[200007];
 8 | int main() {
 9 |     scanf("%d%d", &n, &k);
10 |     for (int i = 1; i <= n; ++i) {
11 |         scanf("%d", &a[i]);
12 |     }
13 |     std::sort(a + 1, a + n + 1);
14 |     n = std::unique(a + 1, a + n + 1) - a - 1;
15 |     for (int i = 1, j = 0; i <= n; ++i) {
16 |         for (; j < i && a[i] - a[j + 1] > k; ++j)
17 |             ;
18 |         ans[i] = ans[j] + 1;
19 |     }
20 |     printf("%d\n", ans[n]);
21 |     return 0;
22 | }

 1 | #include <algorithm>
 2 | #include <cstdio>
 3 | #include <cstring>
 4 | #define ll long long
 5 | int f[5007][5007];
 6 | int a[5007], b[5007];
 7 | int n;
 8 | int main() {
 9 |     scanf("%d", &n);
10 |     for (int i = 1; i <= n; ++i) {
11 |         scanf("%d", &a[i]);
12 |     }
13 |     for (int i = 1; i <= n; ++i) {
14 |         scanf("%d", &b[i]);
15 |     }
16 |     for (int i = 1; i <= n; ++i) {
17 |         for (int j = 1; j <= n; ++j) {
18 |             f[i][j] = std::max(f[i][j], std::max(f[i - 1][j], f[i][j - 1]));
19 |             if (a[i] == b[j]) {
20 |                 f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1);
21 |             }
22 |         }
23 |     }
24 |     printf("%d\n", f[n][n]);
25 |     return 0;
26 | }

（1）（字符串解码）“行程长度编码”（Run-Length Encoding）是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。压缩规则如下：i) 如果原始字符串中一个字符连续出现 $N$ 次（$N \geq 2$），在压缩字符串中它被表示为“字符 + 数字 $N$”。例如，编码 `A12` 代表 $12$ 个连续的字符 A。ii) 如果原始字符串中一个字符只出现 $1$ 次，在压缩字符串中它就表示为该字符本身。例如，编码 `B` 代表 $1$ 个字符 B。

以下程序实现读取压缩字符串并输出其原始的、解压后的形式。试补全程序。

#include <cctype>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string z;
    cin >> z;
    string s = "";

    for (int i = 0; i < z.length(); ) {
        char ch = z[i];

        if (__①__ && isdigit(z[i + 1])) {
            i++;
            int count = 0;
            while (i < z.length() && isdigit(z[i])) {
                count = __②__;
                i++;
            }
            for (int j = 0; j < __③__; ++j) {
                s += ch;
            }
        } else {
            s += __④__;
            __⑤__;
        }
    }

    cout << s << endl;
    return 0;
}

（2）（精明与糊涂）有 $N$ 个人，分为两类： i) 精明人：永远能正确判断其他人是精明还是糊涂； ii)糊涂人：判断不可靠，会给出随机的判断。

已知精明人严格占据多数，即如果精明人有 $k$ 个，则满足 $k > N/2$。

你只能通过函数 $\text{query}(i, j)$ 让第 $i$ 个人判断第 $j$ 个人：返回 $\text{true}$ 表示判断结果为“精明人”；返回 $\text{false}$ 表示判断结果为“糊涂人”。你的目标是，通过这些互相判断，找出至少一个百分之百确定的精明人。同时，你无需关心 $\text{query}(i, j)$ 的内部实现。

以下程序利用“精明人占多数”的优势。设想一个“消除”的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选人必然属于多数派，即精明人。

例如，假设有三人 $0, 1, 2$。如果 $0$ 说 $1$ 是糊涂人，而 $1$ 也说 $0$ 是糊涂人，则 $0$ 和 $1$ 至少有一个是糊涂人。程序将同时淘汰 $0$ 和 $1$。由于三人里至少有两个精明人，我们确定 $2$ 是精明人。

试补全程序。

#include <iostream>
#include <vector>
using namespace std;

int N;
bool query(int i, int j);

int main() {
    cin >> N;

    int candidate = 0;
    int count = __①__;
    for (int i = 1; i < N; ++i) {
        if (__②__) {
            candidate = i;
            count = 1;
        } else {
            if (__③__) {
                __④__;
            } else {
            count++;
            }
        }
    }
    cout << __⑤__ << endl;
    return 0;
}