C/C++蓝桥杯算法真题打卡（Day9）

一、P9241 [蓝桥杯 2023 省 B] 飞机降落 - 洛谷

算法代码：

#include <bits/stdc++.h> // 包含所有标准库
using namespace std;int t, n, bk[15]; // t: 测试数据组数，n: 每组数据的飞机数量，bk: 标记数组，用于记录飞机是否已经降落
struct plane {int t, d, l; // t: 到达时间，d: 最大盘旋时间，l: 降落所需时间
} a[15]; // 存储每架飞机的信息// DFS 函数，dep 表示当前处理的飞机编号，tim 表示当前时间
bool dfs(int dep, int tim) {if (dep > n) // 如果所有飞机都已经处理完毕return 1; // 返回 1，表示可以全部安全降落for (int i = 1; i <= n; i++) { // 遍历所有飞机if (bk[i] || a[i].t + a[i].d < tim) // 如果飞机已经降落或者当前时间超过了飞机的最晚降落时间continue; // 跳过这架飞机bk[i] = 1; // 标记这架飞机为已降落if (dfs(dep + 1, max(tim, a[i].t) + a[i].l)) { // 递归处理下一架飞机，更新时间为当前时间与飞机到达时间的最大值加上降落时间bk[i] = 0; // 回溯，取消标记return 1; // 如果找到一种可行的降落顺序，返回 1}bk[i] = 0; // 回溯，取消标记}return 0; // 如果没有找到可行的降落顺序，返回 0
}int main() {scanf("%d", &t); // 读取测试数据组数while (t--) { // 处理每组数据scanf("%d", &n); // 读取每组数据的飞机数量for (int i = 1; i <= n; i++) {scanf("%d%d%d", &a[i].t, &a[i].d, &a[i].l); // 读取每架飞机的到达时间、最大盘旋时间和降落所需时间}memset(bk, 0, sizeof bk); // 初始化标记数组为 0if (dfs(1, 0)) // 从第一架飞机开始 DFS，初始时间为 0printf("YES\n"); // 如果可以全部安全降落，输出 YESelseprintf("NO\n"); // 否则输出 NO}
}

代码思路

1. 问题分析

问题描述：
- 有 N 架飞机需要降落到一条跑道上。
- 每架飞机有一个到达时间 T_i，最大盘旋时间 D_i，以及降落所需时间 L_i。
- 飞机必须在 [T_i, T_i + D_i] 时间内开始降落，且降落过程需要 L_i 时间。
- 跑道一次只能降落一架飞机，必须等前一架飞机降落完成后，下一架才能开始降落。
- 判断是否有一种降落顺序，使得所有飞机都能安全降落。
目标：
- 对于每组数据，判断是否存在一种降落顺序，使得所有飞机都能在限制时间内完成降落。

2. 解题思路

DFS（深度优先搜索）：
- 使用 DFS 枚举所有可能的降落顺序。
- 对于每架飞机，尝试在当前时间允许的情况下安排降落，并递归处理下一架飞机。
- 如果所有飞机都能安排降落，则返回 YES，否则返回 NO。
剪枝优化：
- 如果当前时间已经超过了某架飞机的最晚降落时间（T_i + D_i），则跳过这架飞机。
- 通过回溯法，尝试所有可能的顺序，确保不遗漏任何情况。

3. 代码结构

数据结构：
- 使用结构体 plane 存储每架飞机的信息（到达时间 t，最大盘旋时间 d，降落时间 l）。
- 使用数组 bk 标记某架飞机是否已经降落。
DFS 函数：
- 参数：
  - dep：当前处理的飞机编号。
  - tim：当前时间。
- 逻辑：
  1. 如果所有飞机都已处理完毕（dep > n），返回 1（表示找到一种可行的降落顺序）。
  2. 遍历所有飞机：
    - 如果飞机已经降落，或者当前时间超过了飞机的最晚降落时间（a[i].t + a[i].d < tim），跳过这架飞机。
    - 否则，标记这架飞机为已降落，并递归处理下一架飞机。
    - 更新时间为 max(tim, a[i].t) + a[i].l，表示当前时间与飞机到达时间的最大值加上降落时间。
    - 如果递归返回 1，表示找到一种可行的顺序，直接返回 1。
    - 否则，回溯并取消标记，继续尝试其他飞机。
  3. 如果所有飞机都尝试过但没有找到可行的顺序，返回 0。
主函数：
1. 读取测试数据组数 t。
2. 对于每组数据：
  - 读取飞机数量 n。
  - 读取每架飞机的信息（t、d、l）。
  - 初始化标记数组 bk 为 0。
  - 调用 dfs(1, 0)，从第一架飞机开始搜索，初始时间为 0。
  - 根据 DFS 的返回值输出 YES 或 NO。

4. 关键点

DFS 的核心：
- 通过递归枚举所有可能的降落顺序。
- 每次递归时，更新当前时间，并确保飞机在允许的时间范围内降落。
剪枝优化：
- 如果当前时间已经超过了某架飞机的最晚降落时间，直接跳过这架飞机，减少不必要的搜索。
回溯法：
- 在递归返回后，取消标记，确保其他顺序能够被正确尝试。

5. 代码流程

输入：
- 读取测试数据组数 t。
- 对于每组数据，读取飞机数量 n 和每架飞机的信息。
DFS 搜索：
- 从第一架飞机开始，尝试所有可能的降落顺序。
- 通过递归和回溯，确保所有顺序都被尝试。
输出：
- 如果找到一种可行的降落顺序，输出 YES。
- 否则，输出 NO。

6. 复杂度分析

时间复杂度：
- 最坏情况下，DFS 需要枚举所有飞机的排列顺序，时间复杂度为 O(N!)。
- 由于 N 最大为 10，10! = 3,628,800，在时间限制内可以完成。
空间复杂度：
- 主要用于存储飞机信息和标记数组，空间复杂度为 O(N)。

总结

该代码通过 DFS 和回溯法，枚举所有可能的降落顺序，并结合剪枝优化，高效地解决了飞机降落问题。
代码逻辑清晰，结构合理，能够正确处理题目要求的所有情况。

二、P8796 [蓝桥杯 2022 国 AC] 替换字符 - 洛谷（跳）

大佬题解：

#include <bits/stdc++.h>  // 包含所有标准库头文件
using namespace std;     // 使用标准命名空间const int N = 1e5 + 5, K = 26;  // 定义常量N为100005，K为26（表示字母表的大小）
int lzy[N * 2][K], ls[N * 2], rs[N * 2], val[N * 2], idx, n, m;  // 定义全局变量
// lzy[p][i]：表示节点p的懒标记，用于记录字符i的映射关系
// ls[p]：表示节点p的左子节点
// rs[p]：表示节点p的右子节点
// val[p]：表示节点p的值
// idx：用于生成新节点的唯一标识
// n：字符串的长度
// m：操作的次数char a[N];  // 存储输入的字符串inline int build(int l, int r) {  // 构建线段树的函数，l和r表示当前区间的左右边界int p = ++idx;  // 创建一个新节点，并分配唯一标识for (int i = 0; i < K; i++)  // 初始化当前节点的懒标记，初始时每个字符映射到自身lzy[p][i] = i;if (l == r) {  // 如果当前区间是叶子节点val[p] = a[l] - 'a';  // 将字符转换为0-25的整数并存储在val[p]中return p;  // 返回当前节点的标识}int mid = (l + r) >> 1;  // 计算区间的中点ls[p] = build(l, mid);  // 递归构建左子树rs[p] = build(mid + 1, r);  // 递归构建右子树return p;  // 返回当前节点的标识
}inline void pushdown(int p) {  // 下推懒标记的函数for (int i = 0; i < K; i++)  // 将当前节点的懒标记传递给左子节点lzy[ls[p]][i] = lzy[p][lzy[ls[p]][i]];for (int i = 0; i < K; i++)  // 将当前节点的懒标记传递给右子节点lzy[rs[p]][i] = lzy[p][lzy[rs[p]][i]];for (int i = 0; i < K; i++)  // 重置当前节点的懒标记为初始状态（每个字符映射到自身）lzy[p][i] = i;
}inline void modify(int p, int l, int r, int L, int R, int x, int y) {  // 修改区间的函数if (L <= l && r <= R) {  // 如果当前区间完全包含在目标区间[L, R]内for (int i = 0; i < K; i++)  // 遍历所有字符if (lzy[p][i] == x)  // 如果当前字符映射到xlzy[p][i] = y;  // 将其映射改为yreturn;  // 返回}pushdown(p);  // 下推懒标记int mid = (l + r) >> 1;  // 计算区间的中点if (L <= mid)  // 如果目标区间与左子区间有交集modify(ls[p], l, mid, L, R, x, y);  // 递归修改左子区间if (R > mid)  // 如果目标区间与右子区间有交集modify(rs[p], mid + 1, r, L, R, x, y);  // 递归修改右子区间
}inline void print(int p, int l, int r) {  // 打印结果的函数if (l == r) {  // 如果当前区间是叶子节点printf("%c", lzy[p][val[p]] + 'a');  // 根据懒标记映射后的字符打印return;  // 返回}pushdown(p);  // 下推懒标记int mid = (l + r) >> 1;  // 计算区间的中点print(ls[p], l, mid), print(rs[p], mid + 1, r);  // 递归打印左右子区间
}signed main() {  // 主函数cin.tie(nullptr)->sync_with_stdio(false);  // 加速输入输出cin >> a + 1;  // 从输入中读取字符串，存储在a数组中，从a[1]开始n = strlen(a + 1);  // 计算字符串的长度build(1, n);  // 构建线段树cin >> m;  // 读取操作次数for (int i = 1; i <= m; i++) {  // 循环处理每个操作int l, r;char x, y;cin >> l >> r >> x >> y;  // 读取操作的参数：区间[l, r]，将字符x替换为yx = x - 'a', y = y - 'a';  // 将字符转换为0-25的整数modify(1, 1, n, l, r, x, y);  // 调用modify函数进行修改}print(1, 1, n);  // 打印最终结果return 0;  // 程序结束
}