第十六届蓝桥杯C/C++大学A组做题记录

寻找质数

题目要求我们找出第 2025 个质数，同时这是一道填空题，没有时间限制。所以我们可以使用试除法也可以用埃氏筛，为了快点我们还是采用埃氏筛求解，埃氏筛的原理也非常简单：

如果一个数是质数，那么这个数的倍数也是质数，根据此，写出代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 手搓第2025个质数
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int n) {
    vector<bool> nums(n + 1, true);
    nums[0] = false;
    nums[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (nums[i] == true) {
            for (int j = i * i; j <= n; j += i) {
                nums[j] = false;
            }
        }
    }
    return nums[n];
}
int main() {
    int i = 0, res = 2;
    while (i < 2025) {
        if (is_prime(res) == true) {
            i++;
        }
        res++;
    }
    cout << res - 1 << endl;
    return 0;
}

黑白棋

棋盘上的问题，我们可以看作是图上的问题，然后利用搜索求解。值得注意的是边界条件的确定，以及把题目中约束条件翻译为对应的代码，完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;
bool is_valid(vector<vector<int>> &board, int x, int y, int color) {
    if (x >= 2 && board[x - 1][y] == color && board[x - 2][y] == color)
        return false;
    if (y >= 2 && board[x][y - 1] == color && board[x][y - 2] == color)
        return false;
    int x_cnt = 0, y_cnt = 0;
    for (int i = 0; i < 6; i++) {
        if (board[x][i] == color)
            x_cnt++;
    }
    if (x_cnt >= 3)
        return false;
    for (int i = 0; i < 6; i++) {
        if (board[i][y] == color)
            y_cnt++;
    }
    if (y_cnt >= 3)
        return false;
    return true;
}
bool compare(vector<vector<int>> &board) {
    for (int i = 0; i < (6 - 1); i++) {
        for (int j = i + 1; j < 6; j++) {
            if (board[i] == board[j])
                return false;
            bool flag = true;
            for (int k = 0; k < 6; k++) {
                if (board[k][i] != board[k][j]) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                return false;
        }
    }
    return true;
}
bool solve(vector<vector<int>> &board, int x, int y) {
    if (x == 6)
        return compare(board);
    int nx = 0, ny = 0;
    if (y == 5) {
        nx = x + 1;
        ny = 0;
    } else {
        nx = x;
        ny = y + 1;
    }
    if (board[x][y] != -1)
        return solve(board, nx, ny);
    for (auto &color : {0, 1}) {
        if (is_valid(board, x, y, color) == true) {
            board[x][y] = color;
            if (solve(board, nx, ny) == true)
                return true;
            board[x][y] = -1;
        }
    }
    return false;
}
int main() {
    // -1 -> empty, 0 -> white, 1 -> black
    vector<vector<int>> board(6, vector<int>(6, -1));
    board[0][0] = 1;
    board[0][1] = 0;
    board[0][3] = 0;
    board[1][3] = 0;
    board[2][4] = 0;
    board[2][5] = 0;
    board[4][2] = 1;
    board[4][5] = 1;
    board[5][1] = 0;
    board[5][4] = 1;
    bool flag = solve(board, 0, 0);
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            cout << board[i][j];
        }
    }
    cout << endl;
    return 0;
}

抽奖

没啥好说，纯模拟就行了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n = 0;
    cin >> n;
    vector<vector<int>> disks(3, vector<int>(n, 0));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n; j++) {
            cin >> disks[i][j];
        }
    }
    int m = 0;
    cin >> m;
    vector<vector<int>> works(m, vector<int>(3, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> works[i][j];
        }
    }
    int sum = 0;
    int a = 0, b = 0, c = 0;
    for (int i = 0; i < m; i++) {
        a = (a + works[i][0]) % n;
        b = (b + works[i][1]) % n;
        c = (c + works[i][2]) % n;
        // 三个相同图案
        if (disks[0][a] == disks[1][b] && disks[1][b] == disks[2][c])
            sum += 200;
        // 两个相同图案
        if (disks[0][a] == disks[1][b] && disks[1][b] != disks[2][c])
            sum += 100;
        if (disks[0][a] == disks[2][c] && disks[1][b] != disks[2][c])
            sum += 100;
        if (disks[1][b] == disks[2][c] && disks[0][a] != disks[2][c])
            sum += 100;
        // 对于连续的三个数
        if (disks[1][b] - disks[0][a] == 1 && disks[2][c] - disks[1][b] == 1) {
            sum += 200;
        } else {
            vector<int> temp = {disks[0][a], disks[1][b], disks[2][c]};
            sort(temp.begin(), temp.end());
            if (temp[1] - temp[0] == 1 && temp[2] - temp[1] == 1)
                sum += 100;
        }
    }
    cout << sum << endl;
    return 0;
}

红黑树

我们将红黑树中的所有节点按照从上往下，从左往右的顺序进行编号，再将对应节点的十进制编号转为二进制串，接着我们会发现二进制串中 ‘1’ 的个数为奇数的节点是红色。

因此，代码就很好写了，具体如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
int count_1(int n, int k) {
    int cnt = 0;
    int num = k - 1;
    while (num != 0) {
        if (num % 2 == 1)
            cnt++;
        num = num / 2;
    }
    return cnt;
}
int main() {
    int m = 0;
    cin >> m;
    vector<vector<int>> n_k(m, vector<int>(2, 0));
    for (int i = 0; i < m; i++) {
        cin >> n_k[i][0] >> n_k[i][1];
    }
    for (int i = 0; i < m; i++) {
        int flag = count_1(n_k[i][0], n_k[i][1]);
        if (flag % 2 == 0)
            cout << "RED" << endl;
        else
            cout << "BLACK" << endl;
    }
    return 0;
}

黑客

这道题大概率我的代码超时了，毕竟涉及到了排列组合，不可避免地要计算阶乘这样的东西。我还是简单的讲讲算法，首先我们记元素总个数为 L ，然后我们建立一个哈希表，将元素与其出现的次数存入，通过枚举，找到总个数减去 2 的因子 m ： L − 2 = mn 接着我们检验 n 是否在哈希表中出现，如果也存在，那么根据排列组合的知识，所有的可能数应该等于： $$ S = \frac{(L-2)!}{\prod_0^nc_k!} $$ 其中，ck 为除去选中的两个元素 m, n 后其余元素的出现次数。为了简化运算，我们做预处理： $$ A =\frac{(L-2)!}{\prod_0^nb_k!} $$ 其中，bk 为所有元素的出现次数，选中对应元素后，可能数求解为： $$ S=\begin{cases} A\times m \times n & m\neq n \\ A\times m \times (m-1) & m = n \end{cases} $$ 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int f(int n) {
    if (n == 1 || n == 0) {
        return 1;
    }
    return n * f(n - 1);
}
int main() {
    int sum = 0;
    cin >> sum;
    vector<int> element(sum);
    unordered_map<int, int> cnt;
    for (int i = 0; i < sum; i++) {
        cin >> element[i];
        if (cnt.find(element[i]) != cnt.end())
            cnt[element[i]]++;
        else
            cnt.emplace(element[i], 1);
    }
    int base = f(sum - 2);
    for (auto &e : cnt) {
        base /= f(e.second);
    }
    int ans = 0;
    for (auto &e : cnt) {
        int x = e.first;
        if ((sum - 2) % x == 0 && cnt.find((sum - 2) / x) != cnt.end()) {
            int y = (sum - 2) / x;
            if (x != y && cnt[x] >= 1 && cnt[y] >= 1) {
                ans = ans + (base * cnt[x] * cnt[y]);
            }
            if (x == y && cnt[x] >= 2) {
                ans = ans + (base * cnt[x] * (cnt[x] - 1));
            }
        }
    }
    cout << ans << endl;
    return 0;
}

地雷阵

高中解析几何题来了，根据圆心坐标以及对应圆的半径，我们可以求出这颗地雷对应的危险角度范围，最后做一下区间合并，计算危险区间总长度即可。

对应代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
#define Pi 3.1415926
using namespace std;
// 定义炸弹结构体
typedef struct {
    int x;
    int y;
    int r;
} Bomb;
// 定义区间结构体
typedef struct {
    double left;
    double right;
} Interval;
int main() {
    int n = 0;
    cin >> n;
    // 读入数据
    vector<Bomb> danger(n);
    for (int i = 0; i < n; i++) {
        cin >> danger[i].x >> danger[i].y >> danger[i].r;
    }
    vector<Interval> res(n);
    for (int i = 0; i < n; i++) {
        double alpha = atan2(danger[i].y, danger[i].x);
        double d = sqrt(pow(danger[i].x, 2) + pow(danger[i].y, 2));
        double beta = asin(danger[i].r / d);
        res[i] = {alpha - beta, alpha + beta};
    }
    // 区间合并
    sort(res.begin(), res.end(), [](const Interval &a, const Interval &b) { return a.left < b.left; });
    double sum = 0;
    double current_left = res[0].left, current_right = res[0].right;
    for (int i = 1; i < n; i++) {
        if (res[i].left > current_right) {
            sum += (current_right - current_left);
            current_left = res[i].left;
            current_right = res[i].right;
        } else {
            current_left = min(current_left, res[i].left);
            current_right = max(current_right, res[i].right);
        }
    }
    sum += (current_right - current_left);
    double ans = 1 - (2 * sum / Pi);
    cout << fixed << setprecision(3) << ans << endl;
    return 0;
}

至于其余题目，本人的算法水平还是太菜了，写不来😫。

详细的代码源文件可以在我的 Github 仓库中找到，最后感谢你的耐心阅读。

算法题
#蓝桥杯
第十六届蓝桥杯C/C++大学A组做题记录
https://zijeff.github.io/2026/03/08/第十六届蓝桥杯C-C-大学A组做题记录/
作者
zijeff
发布于
2026年3月8日
许可协议