09.25 第45课基础算法复习

Kaito

2026-10-05 22:47:32

发布于：上海

16阅读

0回复

0点赞

09.25 基础算法复习

0. 模拟算法

题目推荐

模拟分类	题目（点击直达）	核心考点与训练点
基础/规则模拟	P1042 [NOIP2003 普及组] 乒乓球	规则翻译。将 11 分制和 21 分制的计分规则翻译成代码。注意判断比赛结束的条件（不仅要到分，还要相差 2 分以上）。
基础/字符模拟	P1055 [NOIP2008 普及组] ISBN 号码	字符与数字的转换。提取字符串中的数字进行计算，并处理最后一位可能是 `X` 的特殊情况。
网格/方向模拟 (非常经典)	P2670 [NOIP2015 普及组] 扫雷游戏	二维矩阵与方向数组。对每个格子去寻找它周围 8 个方向的地雷数量。必学 `dx` 和 `dy` 方向数组技巧！
字符串解析模拟	P1308 [NOIP2011 普及组] 统计单词数	独立的单词匹配。难点在于：大小写不敏感（需全部转小写）；以及如何防止把 `to` 错误匹配到 `tomato` 里面（边界判断）。
环形/状态模拟 (强烈推荐)	P1563 [NOIP2016 提高组] 玩具谜题	环形数组与朝向逻辑。小人围成一圈，有面朝内/朝外，指令有向左/向右。巧用异或运算或组合判断，以及 `% N` 取模来实现环形移动。
极端特判模拟 (魔鬼训练)	P1067 [NOIP2009 普及组] 多项式输出	无穷无尽的边界特判。系数为正或负？系数为 `1` 或 `-1` 时省不省略？次数为 `1` 和 `0` 怎么输出？这题能完美测出你的细心程度。

1. 结构体排序

通常是 sort + cmp + struct 的组合，用于解决单个对象具有多个属性的排序问题。

例题：A4758 奥特曼身高问题

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
struct stu {
    string name;
    int h, y;
} a[N];

int n;

bool cmp(stu a, stu b) {
    if (a.h != b.h) return a.h > b.h; // 第一关键字：身高不相等时，高的在前
    if (a.y != b.y) return a.y < b.y; // 第二关键字：身高相等时，年龄小的在前
    return a.name < b.name;          // 第三关键字：全相等按字典序排
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].name >> a[i].h >> a[i].y;
    sort(a + 1, a + 1 + n, cmp);
    cout << a[1].name << " " << a[1].h << " " << a[1].y;
    return 0;
}

题目推荐

分类阶段	题目（点击直达）	核心考点与训练点
基础入门	P5740 【深基7.例9】最厉害的学生	基础结构体定义、信息记录与读写
基础入门	P5742 【深基7.例11】评优	结构体内计算、简单条件组合判断
基础入门	P1104 生日	多关键字比较、处理“输入顺序”隐性关键字
基础入门	P5143 攀爬者	结构体排序 + 空间几何距离公式计算
必刷真题<br>(重点)	P1093 [NOIP2007 普及组] 奖学金	经典三重条件多关键字排序（必背模板题）
必刷真题<br>(重点)	P1068 [NOIP2009 普及组] 分数线划定	排序结合逻辑统计、处理“同分并列录取”
进阶提升	P1781 宇宙总统	结构体排序 + `string` 大整数比较（防溢出）
进阶提升	P1051 [NOIP2005 提高组] 谁拿了最多奖学金	复杂题意阅读理解、多属性逻辑计算与排序
进阶提升	P1116 车厢重组	排序本质理解（求逆序对 / 冒泡交换次数）

2. 筛法（试除法、埃氏筛）

注意：

判断单个数是否为质数与批量求质数是两个完全不同的应用场景。

这里仅讨论正整数范围，若遇到负数情况通常取绝对值后处理。

试除法（朴素）

核心思想：暴力枚举 $2 \sim (n-1)$ 是否为 $n$ 的因数。
时间复杂度： $O(n)$

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

试除法（ $\sqrt{n}$ 优化）

核心思想：因数成对出现，若 $n$ 存在因数，较小的一个必 $\le \sqrt{n}$ 。
时间复杂度： $O(\sqrt{n})$

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

埃氏筛（Eratosthenes Sieve）

核心思想：质数的倍数一定不是质数。从小到大遍历，如果当前数未被标记，则它必定是质数；随后将其所有倍数全部标记为合数。
时间复杂度： $O(n \log \log n)$

bool notp[100005]; // true 表示合数
int primes[100005], cnt;

void sieve(int n) {
    notp[0] = notp[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!notp[i]) {
            primes[++cnt] = i;
            for (long long j = (long long)i * i; j <= n; j += i) {
                notp[j] = 1;
            }
        }
    }
}

3. 枚举算法

枚举三要素

确定枚举对象：枚举什么？（答案？分割点？子集？）
确定枚举范围：循环从哪里开始、到哪里结束。
合法判断条件：满足哪些条件的枚举对象是合法的解。

识别信号

求解“所有方案”、“总共多少个解”、“是否存在某种解”。
数据范围极小（如 $N \le 20$ 、 $N \le 100$ 等）。

枚举分类

盲目枚举：遍历所有可能数值，时间复杂度通常极高。
构造枚举：利用题目规则和性质直接构造符合条件的解。

题目推荐

枚举类型	题目（点击直达）	核心考点与训练点
基础/边界枚举	P1149 [NOIP2008 提高组] 火柴棒等式	确定枚举边界。看似是提高组，实际极简单。思考： $A+B=C$ ， $A$ 和 $B$ 最大需要枚举到多少？
排列枚举	P1008 [NOIP1998 普及组] 三连击	全排列枚举。可以用多层 `for` 循环，也可以使用 STL 中的 `next_permutation`。
构造枚举 (强烈推荐)	P1217 [USACO1.5] 回文质数	构造枚举 + 质数判断。盲目枚举必超时。必须“先构造回文数，再判断质数”，结合 $O(\sqrt{n})$ 算法。
区间/图形枚举	P2241 统计方形（数据加强版）	二维枚举/数学归纳。在 $N \times M$ 的网格中枚举正方形和长方形的数量。
递归/组合枚举	P1036 [NOIP2002 普及组] 选数	DFS 枚举组合。从 $N$ 个数中选 $K$ 个数求和并判素数。CSP-J 经典模板题。
状态/剪枝枚举	P2089 烤鸡	暴力 DFS + 简单剪枝。体会当循环层数过多时，如何用递归函数代替深层嵌套循环。

4. 贪心算法

核心思想：每一步都做出当前的最优选择，期望局部最优解能推导出全局最优解。

常见贪心策略

排序后贪心
每次选择极值（最大/最小）
区间调度贪心（按起点、终点或持续时长排序）

识别信号

题目要求最值（最大、最小、最少操作等）。
注意区分与 DP：如果当前的选择不影响后续决策的可行性，优先考虑贪心；如果每一步选择都会对后续状态产生连锁约束，通常需要 DP。

题目推荐

贪心模型	题目（点击直达）	核心考点与训练点
基础排序贪心	P1223 排队接水	最短处理时间优先。接水耗时短的人排在前面可使总等待时间最短，结合结构体记录原序号。
双指针/匹配贪心	P1094 [NOIP2007 普及组] 纪念品分组	首尾配对贪心。排序后用双指针指向最重与最轻，能打包则一同打包，否则最重的单独一组。
区间调度贪心 (绝对重点!)	P1803 凌乱的yyy / 线段覆盖	区间不重叠问题。必背结论：按比赛的“结束时间”从小到大排序！
数组遍历贪心	P3817 小A的糖果	局部修改最优解。相邻两盒不超过 $X$ ，优先吃右边盒子里的糖，能同时惠及下一个区间。
思维/脑筋急转弯	P1007 独木桥	物理模型转化。相遇转身等价于“灵魂穿透”继续往前走。想通这一点代码仅需几行。

5. 二分算法（二分查找 & 二分答案）

前提：使用二分算法的前提是定义域或值域必须具有单调性。

二分查找

核心思路：在单调有序区间中查找目标值，每次取中点判断，将搜索区间减半。

例题 1：A49567 第一个大于等于 x 的数

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int a[N], n, x, ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> x;
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] >= x) {
            ans = mid;
            r = mid - 1; // 寻找左边界，继续往左收缩
        } else {
            l = mid + 1;
        }
    }
    cout << ans;
    return 0;
}

例题 2：A8021 第一个大于 x 的数

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int a[N], n, x, ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> x;
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] > x) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans;
    return 0;
}

二分答案

核心思路：当答案所在区间具备单调性时，不再直接求解结果，而是二分猜测答案，通过 check(mid) 验证当前答案是否合法。

标准模板：

bool check(int mid) {
    // 验证 mid 是否符合条件，通常结合贪心或前缀和遍历
    return true; 
}

int main() {
    int l = /* 答案下界 */, r = /* 答案上界 */, ans = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2; // 防溢出写法
        if (check(mid)) {
            ans = mid;
            r = mid - 1; // 或 l = mid + 1，视题目求最大还是最小而定
        } else {
            l = mid + 1; // 与上方相反
        }
    }
    return 0;
}

题目推荐

二分类型	题目（点击直达）	核心考点与训练点
二分查找 (基础)	P2249 【深基13.例1】查找	纯二分查找模板。在有序数组中找首次出现位置。掌握手写二分与 `lower_bound`。
二分查找	P1102 A-B 数对	变形为 $A = B + C$ 。遍历 $B$ ，二分查找数组中 $B+C$ 的数量（或利用 `upper_bound - lower_bound`）。
二分答案 (入门)	P2440 木材加工	基础二分答案模板。砍木头问题，长度越长段数越少，具备单调性，手写 `check()`。
二分答案 (必考核心)	P2678 [NOIP2015 提高组] 跳石头	“最小值最大”经典模型。二分最短跳跃距离 `mid`，用贪心统计需要移走的石头数。
二分答案 (必考核心)	P1182 数列分段 Section II	“最大值最小”经典模型。将数列分为 $M$ 段求最大和的最小值，体会与跳石头的对偶逻辑。
二分答案 (综合应用)	P1824 进击的奶牛	距离分配问题。同《跳石头》逻辑一致，强化“最小值最大”贪心检验思维。

6. 双指针

核心思想：用两个变量作为指针在序列上同向或反向扫描，利用单调性剔除无效状态，避免冗余遍历。
复杂度优化：通常能将暴力 $O(n^2)$ 降低到 $O(n)$ 。

常见类型

同向双指针（滑动窗口 / 尺取法）：左右指针向同一方向推进，维护一个合法的子串/子数组区间。
相向双指针（对撞指针）：一个从左端、一个从右端向中间靠拢，常用于有序数组的两数求和/配对问题。

题目推荐

双指针分类	题目（点击直达）	核心考点与训练点
相向双指针 (贪心结合)	P1094 [NOIP2007 普及组] 纪念品分组	首尾对撞模型。排序后首尾指针向中靠拢。
同向双指针 (基础滑窗)	P1147 连续自然数和	尺取法基础。求和为 $M$ 的连续区间， $R$ 负责加、 $L$ 负责减。
同向双指针 (二分平替)	P1102 A-B 数对	多指针寻找区间。排序后双指针分别维护目标值的左右边界， $O(n)$ 通关。
滑动窗口 (必刷核心)	P1638 逛画展	满足条件的最短区间。滑窗统计区间包含的画师种类数，达到种类上限后收缩左指针。
双指针进阶 (组合应用)	P3143 [USACO16OPEN] Diamond Collector S	双指针 + 前缀预处理。双指针计算每点往右的最长区间，再组合求解最大双段。

7. 前缀和与差分

前缀和

核心思想：预处理前缀和数组 $sum[i] = sum[i-1] + a[i]$ 。
区间查询：任意区间 $[l, r]$ 的区间和可在 $O(1)$ 时间内求得： $sum[r] - sum[l-1]$ 。

例题：T75839 求区间和

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int a[N];
long long sum[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    int m, l, r;
    cin >> m;
    while (m--) {
        cin >> l >> r;
        cout << sum[r] - sum[l - 1] << "\n";
    }
    return 0;
}

差分

核心思想：前缀和的逆运算。构建差分数组 $d[i] = a[i] - a[i-1]$ 。
区间修改：对区间 $[l, r]$ 整体加减一个值 $v$ ，只需修改两个端点： $d[l] += v,\; d[r+1] -= v$ 。最后做一次前缀和即可还原原数组。

例题：A21132 语文成绩

#include <bits/stdc++.h>
using namespace std;

const int N = 5e6 + 5;
int a[N], d[N], n, p;

int main() {
    cin >> n >> p;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        d[i] = a[i] - a[i - 1]; // 构造差分
    }
    while (p--) {
        int x, y, z;
        cin >> x >> y >> z;
        d[x] += z;
        d[y + 1] -= z;
    }
    for (int i = 1; i <= n; i++) {
        a[i] = d[i] + a[i - 1]; // 差分还原前缀和
    }
    sort(a + 1, a + 1 + n);
    cout << a[1];
    return 0;
}

识别信号

$q$ 次查询区间和 $\to$ 前缀和预处理。
$q$ 次区间批量增减 $\to$ 差分数组。

题目推荐

算法分类	题目（点击直达）	核心考点与训练点
一维前缀和 (基础模板)	P8218 【深进1.例1】求区间和	纯模板题。熟练掌握公式：`sum[R] - sum[L-1]`。
一维差分 (基础模板)	P2367 语文成绩	区间修改模板。体会差分数组端点修改的极速性。
前缀和 + 同余 (高频技巧)	P3131 [USACO16JAN] Subsequences Summing to Sevens S	前缀和 + 模运算。必背结论：若两个前缀和对 7 取模相等，它们之间的子段和必定是 7 的倍数！

8. 递归与深度优先搜索 (DFS)

递归核心思想：函数自己调用自己，将大问题逐层分解为同类子问题。
DFS 核心思想：从一个初始状态出发，沿着一条路径走到底，无法前行时回溯到上一步（恢复现场），尝试其他分支。

识别信号

求解“所有排列”、“所有组合”、“所有可行路径”。
二维连通块、染色（Flood Fill）。
数据规模极小（ $N \le 20$ ）。

题目推荐

DFS 分类	题目（点击直达）	核心考点与训练点
基础排列模板	P1706 全排列问题	DFS 入门必背。用 `vis` 数组记录使用标记，递归结束前必须“恢复现场”（回溯）。
基础组合拆分	P2404 自然数的拆分问题	搜索顺序去重。为了避免 `1+2` 和 `2+1` 重复，通过传参保证“后一个数 $\ge$ 前一个数”。
二维网格迷宫 (必考重点)	P1605 迷宫	二维坐标搜索 + 回溯。求两点间合法路径总数。结合 $dx, dy$ 方向数组。
连通块/染色 (必考重点)	P1451 求细胞数量	Flood Fill 算法。统计连通块数量。注意：本题不需要回溯，走过标记即可。
DFS 实际应用	P2392 kkksc03考前临时抱佛脚	集合划分/选或不选。把耗时题目划分为时间最接近的两组，每题仅有“放左脑”或“放右脑”两种分支。
综合回溯进阶 (魔鬼训练)	P1019 [NOIP2000 提高组] 单词接龙	字符串拼接 + 复杂状态回溯。处理重叠部分的计算，记录单词使用次数上限，适合冲刺高分。

9. 广度优先搜索 (BFS)

核心思想：逐层展开搜索。先访问与起点距离为 1 的所有状态，再访问距离为 2 的状态，依次向外辐射。
核心特性：在无权图 / 步长相等的图上，BFS 首次到达某个状态时必定是最短路径。

题目推荐

BFS 分类	题目（点击直达）	核心考点与训练点
一维 BFS 模板	P1135 奇怪的电梯	纯基础模板。仅上下两向。掌握队列的基本操作与步数统计。
二维 BFS 模板 (必刷核心)	P1443 马的遍历	求单源全局最短路。经典走日字方向数组。输出全图可达点的最短步数，不可达输出 -1。
BFS 连通块/染色	P1162 填涂颜色	逆向思维（外围扩展法）。从地图最外围一圈开始做 BFS 把外圈的 0 染色，剩下的就是闭合圈内的。
多源 BFS (巧妙思维)	P1332 血色先锋队	多起点同时扩散。技巧：初始将所有传染源一次性全部入队，如同多颗石子同时激起水波涟漪。
动态障碍 BFS (进阶提升)	P2895 [USACO08FEB] Meteor Shower S	带时间维度的地图。流星会定时摧毁方格，转移时需判断“到达该点的时间”是否早于“流星落下的时间”。

10. 递推与动态规划 (DP)

递推：根据已知的数学递推公式，自底向上由小项逐步算出大项（偏向规律）。
动态规划：划分子问题，用状态数组描述子结构，通过状态转移方程与无后效性推导最优值（偏向决策）。

题目推荐

DP 分类	题目（点击直达）	核心考点与训练点
基础/数字三角形 (入门必刷)	P1216 [USACO1.5] [IOI1994]数字三角形	自底向上推导。逆向思考从最底层往上推：`dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + a[i][j]`。
网格 DP (必刷核心)	P1002 [NOIP2002 普及组] 过河卒	路径方案数 + 障碍排除。`dp[i][j] = dp[i-1][j] + dp[i][j-1]`，细心标记马控制点及边界初值。
线性 DP	P1115 最大子段和	状态定义的艺术。设 `dp[i]` 为“以第 i 个数结尾的最大连续和”：`dp[i] = max(a[i], dp[i-1] + a[i])`。
0-1 背包 (绝对重点)	P1048 [NOIP2005 普及组] 采药	0-1 背包经典。每个物品仅能选一次。掌握一维滚动优化，容量必须倒序枚举！
完全背包 (绝对重点)	P1616 疯狂的采药	完全背包经典。物品可重复选取无限次。与 0-1 背包唯一区别：容量必须正序枚举（注意开 `long long`）。
背包变种应用	P1049 [NOIP2001 普及组] 装箱问题	价值等于体积的 0-1 背包。剩余空间最小即装入体积最大，将重量视作价值直接套用背包模板即可。

11. STL 常用数据结构（部分）

容器	底层/特点	常见算法场景
`stack`	后进先出（LIFO）	括号匹配、单调栈、表达式求值、中缀转后缀、递归模拟
`queue`	先进先出（FIFO）	广度优先搜索（BFS）、拓扑排序、流水线调度
`map`	键值对映射（内部红黑树有序）	频次统计、字符串离散化、哈希模拟
`set`	有序且不重复的集合	自动去重与升序排序、对数级快速查找（`count` / `find`）