蓝桥杯真题

第十五届蓝桥杯A组

1.五子棋对弈

思路

1. 棋盘表示：

   • 使用二维数组 a[10][10] 来表示棋盘。

2. 全局变量：

   • ans 用于记录满足条件的棋局数量。

3. 深度优先搜索函数 dfs：

   • 参数：
     • n1：当前放置的白棋数量。
     • n2：当前放置的黑棋数量。
     • id：当前格子的序号（用于一维到二维的转换）。
     • c：当前放置的棋子的颜色（1 代表白棋，2 代表黑棋）。

4. 边界条件检查：

   • 如果白棋数量超过 13 或黑棋数量超过 12，或者 id 超过 25，立即返回，停止搜索。

5. 棋子放置：

   • 将当前格子的序号转换为二维坐标 (x, y)，并将其设为当前棋子。

6. 连成一线的检查：

   • 行检查：当当前行填满（y == 4）时，检查该行是否存在不同颜色的棋子。如果全是同色棋子，返回。
   • 列检查：当当前列填满（x == 4）时，进行同样的检查。
   • 对角线检查：在特定的格子（id 为 20 和 24）时，检查两条对角线是否同色。

7. 有效棋局的计数：

   • 当所有棋子都放置完（id >= 24），增加有效棋局数量 ans。

8. 递归放置棋子：

   • 尝试在下一个格子放置白棋和黑棋，递归调用 dfs。
   • 撤销放置，恢复棋盘状态，以便进行下一次尝试。

#include <bits/stdc++.h>
using namespace std;// 棋盘表示
int a[10][10]; // 5×5 的棋盘表示
int ans = 0;   // 记录满足条件的棋局数量// 深度优先搜索函数
void dfs(int n1, int n2, int id, int c) {// 如果白棋超过 13 个或黑棋超过 12 个，或者格子序号超出范围，停止搜索if (n1 >= 14 || n2 >= 13 || id >= 25) return;// 将一维的格子序号 id 转换为二维棋盘的坐标 (x, y)int x = id / 5, y = id % 5;a[x][y] = c; // 将当前格子放置对应棋子// 检查当前行是否连成一线if (y == 4) { // 行填满时才进行检查bool flag = 0;for (int i = 0; i <= 4; i++) {if (a[x][i] != a[x][0]) flag = 1; // 检查是否有不同颜色}if (flag == 0) return; // 如果全同色，返回}// 检查当前列是否连成一线if (x == 4) { // 列填满时才进行检查bool flag = 0;for (int i = 0; i <= 4; i++) {if (a[i][y] != a[0][y]) flag = 1; // 检查是否有不同颜色}if (flag == 0) return; // 如果全同色，返回}// 检查第一条对角线是否连成一线if (id == 20) { // 对角线填满时进行检查bool flag = 0;for (int i = 0; i <= 4; i++) {if (a[i][4-i] != a[0][4]) flag = 1; // 检查是否有不同颜色}if (flag == 0) return; // 如果全同色，返回}// 检查第二条对角线是否连成一线if (id == 24) { // 对角线填满时进行检查bool flag = 0;for (int i = 0; i <= 4; i++) {if (a[i][i] != a[0][0]) flag = 1; // 检查是否有不同颜色}if (flag == 0) return; // 如果全同色，返回}// 若已经枚举完最后一个棋子，说明是平局if (id >= 24) {ans++; // 增加符合条件的棋局数量return;}// 尝试将下一个格子放白棋dfs(n1 + 1, n2, id + 1, 1);// 撤销白棋a[(id + 1) / 5][(id + 1) % 5] = 0;// 尝试将下一个格子放黑棋dfs(n1, n2 + 1, id + 1, 2);// 撤销黑棋a[(id + 1) / 5][(id + 1) % 5] = 0;
}int main() {// 从第一个格子开始，尝试放白棋dfs(1, 0, 0, 1);// 从第一个格子开始，尝试放黑棋dfs(0, 1, 0, 2);// 输出结果cout << ans;return 0;
}

2.训练士兵

使用后缀和从 rN（最大的训练次数）开始，向下遍历到 1。
对于每个 i，将 mp[i] 的值增加 mp[i + 1]。这意味着如果某训练次数为 i，则至少进行 i 次训练的士兵费用就应该包括进行 i + 1 次训练的费用（因为进行 i 次至少也会进行 i + 1 次的费用）。
这使得 mp[i] 最终包含了所有至少进行 i 次训练的士兵的费用总和

#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
const int N = 1e6 + 5, rN = 1e6;
ll n, s; // 士兵数量 n 和组团训练的成本 s
ll p, c, ans; // p 为每名士兵的单次训练成本，c 为士兵需要的训练次数，ans 用于记录最终总花费
map<ll, ll> mp; // 使用 map 存储不同训练次数对应的总训练成本int main() {cin >> n >> s; for(int i = 1; i <= n; i++) {cin >> p >> c; mp[c] += p; // 将该士兵的训练成本累加到对应训练次数 c 的总费用中}// 计算后缀和，更新每种训练次数的总费用for(int i = rN; i >= 1; i--) {mp[i] += mp[i + 1]; // 从 rN 开始累加，将每个训练次数对应的费用更新为所有大于等于该次数的总费用}// 计算所有士兵的最小训练费用for(int i = 1; i <= rN; i++) {ans += min(mp[i], s); // 取每种训练次数的费用和组团训练费用 s 的最小值，累加到 ans 中}cout << ans; return 0;
}

3.团建

思路

1. 邻接表构建

   • 使用map<int, vector<int>>存储两棵树的无向结构，每个节点维护其子节点列表。

2. 同步DFS遍历

   // 关键遍历逻辑
   for (子节点A in 树1的当前节点子节点列表)for (子节点B in 树2的当前节点子节点列表)DFS递归比较(A, B)
   

   • 从根节点(1,1)出发，若当前节点权值相同，则路径长度+1
   • 暴力遍历两棵树当前节点的所有子节点组合（双重循环）

3. 终止条件

   • 当节点权值不同时终止当前路径
   • 自动处理叶子节点（子节点列表为空时递归自然结束）

#include <bits/stdc++.h>
#define N 200005 using namespace std;// 声明两个映射，存储两棵树的邻接表
map<int, vector<int>> m1, m2;int n, m, a[N], b[N], ans, u, v; // n和m是树的节点数，a和b分别存储两棵树的节点权值，ans用于存储最长公共前缀的长度。void dfs(int x, int y, int count) {if (a[x] != b[y]) return; // 如果当前节点权值不相同，则终止搜索ans = max(ans, count + 1); // 更新最长公共前缀长度// 遍历第一棵树的所有子节点for (int i = 0; i < m1[x].size(); i++)// 遍历第二棵树的所有子节点for (int j = 0; j < m2[y].size(); j++) {int a1 = m1[x][i]; // 取得第一棵树的子节点int b1 = m2[y][j]; // 取得第二棵树的子节点dfs(a1, b1, count + 1); // 递归调用DFS以继续比较子节点}
}int main() {cin >> n >> m; // 读取第一棵树每个节点的权值for (int i = 1; i <= n; i++)cin >> a[i];// 读取第二棵树每个节点的权值for (int i = 1; i <= m; i++)cin >> b[i];// 读取第一棵树的边，构建邻接表for (int i = 1; i <= n - 1; i++) {cin >> u >> v; // 读入边的两个节点m1[u].push_back(v); // 将边加入第一棵树的邻接表m1[v].push_back(u); // 由于树是无向的，反向添加边}// 读取第二棵树的边，构建邻接表for (int i = 1; i <= m - 1; i++) {cin >> u >> v; // 读入边的两个节点m2[u].push_back(v); // 将边加入第二棵树的邻接表m2[v].push_back(u); // 由于树是无向的，反向添加边}dfs(1, 1, 0); // 从第一棵树的根节点和第二棵树的根节点开始进行DFS，初始公共前缀长度为0cout << ans; 
}