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

五子棋对弈

很典型的棋盘上的下棋问题，直接采用递归搜索大概率是不行的，我们需要有一定的剪枝策略。比如，我们知道最后的结果是平局，而下棋是交替进行的以及白棋执先，所以最后的棋盘上一定是 13 白棋和 12 黑棋。

根据此作为剪枝策略，写出代码如下：

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
#include <iostream>
#include <vector>
using namespace std;

// 检查某一种颜色是否已经形成五连
bool check(vector<vector<int>> &board, int color) {
    for (int i = 0; i < 5; i++) {
        if (board[i][0] == color && board[i][1] == color && board[i][2] == color && board[i][3] == color &&
            board[i][4] == color) {
            return false;
        }
        if (board[0][i] == color && board[1][i] == color && board[2][i] == color && board[3][i] == color &&
            board[4][i] == color) {
            return false;
        }
    }

    if (board[0][0] == color && board[1][1] == color && board[2][2] == color && board[3][3] == color &&
        board[4][4] == color) {
        return false;
    }

    if (board[0][4] == color && board[1][3] == color && board[2][2] == color && board[3][1] == color &&
        board[4][0] == color) {
        return false;
    }

    return true;
}

// pos：当前处理到第几个格子（0~24）
// black：当前已经放了多少个黑棋
void solve(vector<vector<int>> &board, int pos, int black, int &ans) {
    // 黑棋超过 12 个，不合法
    if (black > 12)
        return;
    // 剩余格子不够放满 12 个黑棋，剪枝
    if (25 - pos < 12 - black)
        return;
    // 25 个格子都处理完了
    if (pos == 25) {
        if (black == 12) {
            // 此时白棋自动是 13 个
            // 检查黑白双方都没有五连
            if (check(board, -1) && check(board, 1)) {
                ans++;
            }
        }
        return;
    }
    int x = pos / 5;
    int y = pos % 5;
    // 方案1：这个位置放黑棋
    board[x][y] = -1;
    if (check(board, -1))
        solve(board, pos + 1, black + 1, ans);

    // 方案2：这个位置放白棋
    board[x][y] = 1;
    if (check(board, 1))
        solve(board, pos + 1, black, ans);

    // 回溯
    board[x][y] = 0;
}
int main() {
    // 0->empty, 1->white, -1->black
    vector<vector<int>> board(5, vector<int>(5, 0));
    int ans = 0;
    solve(board, 0, 0, ans);
    cout << ans << endl;
    return 0;
}

训练士兵

设第 i 名士兵单独训练一次花费为 p_i，至少需要训练 c_i 次；组团训练一次花费 S，并且所有士兵都会同时获得 1 次训练。最直接的想法是：枚举购买了 k 次组团训练，那么总费用为
$$
kS+\sum_{i=1}^{n} p_i\max(0,c_i-k)
$$
其中：

  • kS 表示买了 k 次组团训练；
  • 若某个士兵还差 c_i-k 次训练，就补单独训练。

这个思路是正确的，但如果对每个 k 都重新计算一遍所有士兵，复杂度是
$$
O(n \cdot \max c_i)
$$
在本题数据范围下无法通过。

换一个角度思考，不去枚举“买了多少次组团训练”，而是按“第几轮训练”逐层考虑。假设当前还有一些士兵尚未完成训练，他们的单次训练费用之和为
$$
sum=\sum p_i
$$
那么这一轮训练有两种选择：

  • 让这些士兵各自单练一次，费用为 sum；
  • 购买一次组团训练，费用为 S。

因此这一轮的最优决策就是取两者较小值：
$$
\min(sum,S)
$$
做完这一轮后，那些恰好训练次数已经满足要求的士兵就不再参与后续训练，因此要从 sum 中减去他们的p_i。初始时，所有士兵都还需要训练，因此
$$
sum=\sum_{i=1}^{n} p_i
$$
同时用数组 finish[k] 记录：第 k+1 轮训练结束后完成训练的士兵，其 p_i 之和。这样每一轮只需：

  1. 累加本轮最小花费 min(sum,S)；

  2. 再令
    $$
    sum -= finish[k]
    $$

  3. 接着循环继续，进入下一轮

只需一次读入和一次按轮次扫描，时间复杂度为
$$
O(n+\max c_i)
$$
这样就可以通过本题。

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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef struct {
    int price;
    int time;
} solider;

int main() {
    int n = 0;
    long long s = 0;
    cin >> n >> s;

    vector<solider> people(n);

    int max_time = 0;
    long long cost_one_time = 0;
    long long sum = 0;

    for (int i = 0; i < n; i++) {
        cin >> people[i].price >> people[i].time;
        max_time = max(max_time, people[i].time);
        cost_one_time += people[i].price;
    }
    vector<long long> finish(max_time);
    for (int i = 0; i < n; i++) {
        int k = people[i].time - 1;
        finish[k] += people[i].price;
    }
    for (int k = 0; k < max_time; k++) {
        if (cost_one_time > s)
            sum += s;
        else
            sum += cost_one_time;
        cost_one_time -= finish[k];
    }
    cout << sum << endl;
    return 0;
}

团建

这道题可以设计状态 f(u,v)，表示第一棵树当前位于结点 u、第二棵树当前位于结点 v 时，从这两个位置开始能得到的最长公共前缀长度。若当前两个结点权值不同，那么公共前缀在这一层就已经中断，因此有
$$
f(u,v)=0 \qquad (w_1(u)\ne w_2(v))
$$
若当前权值相同，则当前这一层一定可以计入答案；接下来分别从 u 和 v 的所有孩子中各选一个继续向下走，因此状态转移为
$$
f(u,v)=1+\max_{x\in son(u)\ ,\ y\in son(v)} f(x,y)\qquad (w_1(u)=w_2(v))
$$
如果其中一边已经是叶子结点，那么后续无法继续匹配，此时直接返回 1。因此只需从两棵树的根结点同时开始递归计算 f(0,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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using vvector = vector<vector<int>>;
int solve(vvector &tree_m, vector<int> &weight_m, int u, vvector &tree_n, vector<int> &weight_n, int v) {
    if (weight_m[u] != weight_n[v])
        return 0;
    if (tree_m[u].empty() || tree_n[v].empty())
        return 1;
    int best = 0;
    for (int i = 0; i < tree_m[u].size(); i++) {
        int p = tree_m[u][i];
        for (int j = 0; j < tree_n[v].size(); j++) {
            int q = tree_n[v][j];
            best = max(best, solve(tree_m, weight_m, p, tree_n, weight_n, q));
        }
    }
    return best + 1;
}
int main() {
    int m, n;
    cin >> m >> n;

    vector<int> weight_m(m, 0);
    vector<int> weight_n(n, 0);

    for (int i = 0; i < m; i++)
        cin >> weight_m[i];
    for (int i = 0; i < n; i++)
        cin >> weight_n[i];

    vvector tree_m(m);
    vvector tree_n(n);
    for (int i = 0; i < m - 1; i++) {
        int u, v;
        cin >> u >> v;
        int p = max(u, v) - 1, q = min(u, v) - 1;
        tree_m[q].push_back(p);
    }
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        int p = max(u, v) - 1, q = min(u, v) - 1;
        tree_n[q].push_back(p);
    }
    int ans = solve(tree_m, weight_m, 0, tree_n, weight_n, 0);
    cout << ans << endl;
    return 0;
}

成绩统计

这题的关键在于把题目转化成一个带有单调性的判定问题。设 check(x) 表示在前 x 名同学中，是否已经能够选出 k 个成绩，使它们的方差严格小于 T。如果前 x 个人已经可行，那么前 x+1 个人显然也仍然可行，因为原来那 k 个人依旧可以被选到，所以答案具有明显的单调性，我们可以二分最小的前缀长度。

接下来考虑如何实现 check(x)。假设我们已经取出了前 x 个成绩，并将它们从小到大排序。此时有一个很重要的性质：如果要从中选出 k 个数，使得方差尽可能小，那么这 k 个数在排序后一定对应一段连续区间。直观理解也不难，如果当前选出的集合中间存在“空档”，那么把更远的数替换成中间的数，只会让整体更加集中，从而使方差不增。因此，判定时不需要枚举任意 k 个数，只需要枚举排序后所有长度为 k 的连续子段即可。

对于某一段长度为 k 的区间，设其元素和为 S1，平方和为 S2，那么它的方差可以写成：

$$
Var = \frac{S_2}{k} - (\frac{S_1}{k})^2
$$

为了避免浮点误差，我们把它改写成整数比较的形式：

$$
Var < T \iff kS_2 - S_1^2 < k^2T
$$

这样一来，只要预处理出排序数组的前缀和与平方前缀和，就可以在 O(1) 的时间内求出任意一个长度为 k 的连续区间对应的 S1 和 S2，从而完成一次判断。单次 check(x) 的复杂度是排序的 O(x log x) 加上线性扫描的 O(x)，总复杂度为 O(xlogx)。结合二分答案，整体复杂度就是 O(nlog^2n)，足以通过这道题。

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

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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

bool check(int x, vector<int> &grade, int k, long long t) {
    if (x < k) return false;

    vector<int> data;
    for (int i = 0; i < x; i++)
        data.push_back(grade[i]);

    sort(data.begin(), data.end());

    vector<long long> pre1;
    vector<long long> pre2;
    long long s1 = 0, s2 = 0;

    pre1.push_back(0);
    pre2.push_back(0);

    for (int i = 0; i < data.size(); i++) {
        s1 += data[i];
        pre1.push_back(s1);
        s2 += 1LL * data[i] * data[i];
        pre2.push_back(s2);
    }

    for (int i = 1; i <= x + 1 - k; i++) {
        long long S1 = pre1[i + k - 1] - pre1[i - 1];
        long long S2 = pre2[i + k - 1] - pre2[i - 1];
        if (1LL * k * S2 - S1 * S1 < 1LL * k * k * t)
            return true;
    }
    return false;
}

int main() {
    int n, k;
    long long t;
    cin >> n >> k >> t;

    vector<int> grade(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> grade[i];
    }

    int ans = -1;
    if (check(n, grade, k, t)) {
        int l = k, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            if (check(mid, grade, k, t))
                r = mid;
            else
                l = mid + 1;
        }
        ans = l;
    }

    cout << ans << endl;
    return 0;
}

零食采购

显然算法有点问题，超时了，只能混上一部分的分了。我的思路很显然，利用 BFS 计算最短路，同时记录最短路径，最后用一个哈希表记录出现的零食种类即可。

代码如下：

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
#include <algorithm>
#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>
using namespace std;
using vvector = vector<vector<int>>;
using project = pair<int, int>;
int solve(vvector &road, vector<int> &c, int begin, int end) {
    int n = road.size();
    vector<int> vis(n, 0);
    vector<int> parent(n, -1);
    queue<int> q;
    q.push(begin);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 1;
        if (u == end)
            break;
        for (int i = 0; i < road[u].size(); i++) {
            int v = road[u][i];
            if (vis[v] != 1) {
                q.push(v);
                parent[v] = u;
            }
        }
    }
    unordered_set<int> res;
    int cur = end;
    while (cur != -1) {
        res.insert(c[cur]);
        if (cur == begin)
            break;
        cur = parent[cur];
    }
    return res.size();
}
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> c(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    vvector road(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        road[u - 1].push_back(v - 1);
        road[v - 1].push_back(u - 1);
    }
    vector<project> plan(q);
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        plan[i] = {u - 1, v - 1};
    }
    for (int i = 0; i < q; i++) {
        int ans = solve(road, c, plan[i].first, plan[i].second);
        cout << ans << endl;
    }
    return 0;
}

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

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

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