AcWing 模板总览与章节索引
AcWing 模板总览与章节索引
这个页面按章节整理常见算法题型，目标是做到两件事：
- 章节划分清楚，方便查找
- 每个章节都能快速找到对应模板
使用说明
建议把这个页面当成一个总索引：
- 学新章节时，先看这一章有哪些固定题型
- 刷题时，先定位题型，再回查模板
- 复习时，按章节逐个过模板
目录
章节笔记直达：
基础算法
章节笔记：基础算法章节笔记
二分
适用场景：
- 答案具有单调性
- 左右边界明确
- 需要找第一个满足条件的位置或最后一个满足条件的位置
模板关键词：
check(mid)- 左边界二分
- 右边界二分
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 整数二分 | l, r, mid 边界收缩 |
待补充 | 最基础 |
| 浮点二分 | 精度控制 | 待补充 | 注意误差 |
| 二分答案 | check(mid) 判定 |
待补充 | 最常见 |
双指针
适用场景：
- 区间具有单调扩展性质
- 需要维护一个连续窗口
- 两个序列需要同步扫描
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 同向双指针 | 滑动窗口 | 待补充 | 子数组类常见 |
| 相向双指针 | 首尾夹逼 | 待补充 | 有序数组常见 |
| 双序列扫描 | 两数组匹配 | 待补充 | 归并思想 |
前缀和与差分
适用场景：
- 快速求区间和
- 频繁进行区间加减
- 二维矩阵统计
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 一维前缀和 | s[i] = s[i-1] + a[i] |
待补充 | 区间求和 |
| 二维前缀和 | 矩阵前缀和 | 待补充 | 子矩阵统计 |
| 一维差分 | 区间加法 | 待补充 | 批量修改 |
| 二维差分 | 子矩阵修改 | 待补充 | 综合性强 |
排序与离散化
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 快速排序思想 | 分治模板 | 待补充 | 基础 |
| 归并排序思想 | 逆序对 | 待补充 | 高频 |
| 离散化 | 排序去重映射 | 待补充 | 值域压缩 |
| 区间合并 | 排序后扫描 | 待补充 | 常规题 |
数据结构
章节笔记：数据结构章节笔记
栈、队列、单调栈、单调队列
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 普通栈 | push / pop / top |
待补充 | 基础操作 |
| 表达式求值 | 运算符栈 | 待补充 | 易错 |
| 单调栈 | 找左边/右边最近更大更小 | 待补充 | 高频 |
| 单调队列 | 滑动窗口最值 | 待补充 | 高频 |
链表、哈希、Trie、并查集
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 静态链表 | e / ne / head |
待补充 | AcWing 风格明显 |
| 哈希表 | 拉链法/开放寻址 | 待补充 | 常见基础题 |
| Trie | 字符串统计 | 待补充 | 字典树 |
| 并查集 | find / merge |
待补充 | 连通性问题 |
堆与 KMP
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 小根堆 | down / up |
待补充 | 优先队列 |
| 模拟堆 | 支持删除和修改 | 待补充 | 进阶 |
| KMP | next 数组 |
待补充 | 字符串匹配 |
搜索与图论
章节笔记：搜索与图论章节笔记
DFS 与 BFS
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 树与图的 DFS | 邻接表遍历 | 待补充 | 基础搜索 |
| 全排列 / 组合 | 回溯模板 | 待补充 | 入门必练 |
| 最短路 BFS | 队列分层 | 待补充 | 无权图 |
| 多源 BFS | 多起点入队 | 待补充 | 常见变形 |
最短路、最小生成树、拓扑排序
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| Dijkstra | 堆优化最短路 | 待补充 | 正权图 |
| Bellman-Ford | 边数限制/负权边 | 待补充 | 经典 |
| SPFA | 队列优化 | 待补充 | 注意最坏情况 |
| Floyd | 多源最短路 | 待补充 | 点数小 |
| Prim / Kruskal | 最小生成树 | 待补充 | 高频 |
| 拓扑排序 | 入度数组 | 待补充 | DAG |
染色法、二分图与树
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 染色法判二分图 | DFS/BFS 染色 | 待补充 | 基础 |
| 匈牙利算法 | 二分图匹配 | 待补充 | 经典 |
| 树的重心 | DFS 统计子树 | 待补充 | 树上基础 |
数学知识
章节笔记：数学知识章节笔记
数论基础
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 质数判定 | 试除法 | 待补充 | 基础 |
| 分解质因数 | 试除分解 | 待补充 | 高频 |
| 筛质数 | 埃氏筛/线性筛 | 待补充 | 常考 |
| 约数个数与约数和 | 分解后计算 | 待补充 | 公式题 |
| 最大公约数 | gcd |
待补充 | 基础 |
快速幂、扩展欧几里得、组合计数
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 快速幂 | qmi(a, k, p) |
待补充 | 高频 |
| 扩展欧几里得 | exgcd |
待补充 | 线性同余 |
| 组合数 I | 递推/预处理 | 待补充 | 基础 |
| 组合数 II | 阶乘逆元 | 待补充 | 高频 |
| 容斥原理 | 子集枚举 | 待补充 | 需要熟练 |
动态规划
章节笔记：动态规划章节笔记
线性 DP 与背包 DP
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 数字三角形 | 线性转移 | 待补充 | 入门 |
| 最长上升子序列 | 一维 DP / 贪心优化 | 待补充 | 高频 |
| 01 背包 | 倒序枚举体积 | 待补充 | 核心模板 |
| 完全背包 | 正序枚举体积 | 待补充 | 核心模板 |
| 多重背包 | 二进制优化 | 待补充 | 进阶 |
| 分组背包 | 分组选择 | 待补充 | 常见变形 |
区间 DP、状态压缩 DP、树形 DP
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 区间 DP | 枚举区间长度 | 待补充 | 石子合并类 |
| 状压 DP | 二进制状态表示 | 待补充 | 进阶 |
| 树形 DP | 先子树后根 | 待补充 | 重要专题 |
| 数位 DP | 按位限制 | 待补充 | 难度稍高 |
DP 做题提醒
- 先定义状态含义
- 再写状态转移
- 最后确定初始化与答案位置
很多 DP 写不出来，不是代码问题，而是状态定义不清楚。
贪心与综合技巧
章节笔记：贪心专题章节笔记
区间问题、排序贪心、绝对值模型
推荐整理内容：
| 题型 | 对应模板 | 代表题 | 备注 |
|---|---|---|---|
| 区间选点 | 按右端点排序 | 待补充 | 典型贪心 |
| 区间分组 | 小根堆维护 | 待补充 | 高频 |
| 区间覆盖 | 贪心推进 | 待补充 | 经典 |
| 排队打水 | 排序最优 | 待补充 | 基础 |
| 货仓选址 | 中位数模型 | 待补充 | 经典结论 |
综合建议
- 贪心题一定要先想“为什么这样选一定最优”
- 如果证明说不清，先别急着写
- 看到“局部最优推出整体最优”时再考虑贪心
如何继续补全这个合集
你后续可以按这个格式持续扩展：
- 每个章节先补“代表题”
- 每个题型单独再开文章写题解
- 在题解里反链回这个合集页
- 每个模板都保留一份标准写法
快速入口
- 返回 AcWing 主页：AcWing 基础算法专题导航
- 在线题库：打开在线题库
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 EnxianW的Blog！
相关推荐
2026-05-28
AcWing 搜索与图论章节笔记
AcWing 搜索与图论章节笔记这一章的主线是“建模 -> 存图 -> 选算法”。很多题目代码不复杂，难的是第一步选对方法。 本章核心模板DFS / 回溯1234567891011121314void dfs(int u) { if (u > n) { // 输出答案 return; } for (int i = 1; i <= n; i++) { if (!st[i]) { st[i] = true; path[u] = i; dfs(u + 1); st[i] = false; } }} BFS123456789101112131415queue<pair<int,int>> q;q.push({0, 0});dist[0][0] = 0;while (!q.emp...
2026-05-28
AcWing算法专题总览
AcWing算法专题总览这篇文章是我整理的 AcWing 基础算法专题入口，核心目标不是单纯罗列题目，而是把： 章节 模板 代表题 复习路径 放到同一个学习体系里。 这个专题适合谁 正在刷 AcWing 基础课的人 想按章节系统复习算法的人 想把题型和模板真正对应起来的人 建议使用方式更推荐按这个顺序用： 先看专题总览，明确章节结构 再进章节笔记，看模板和题解要点 最后到在线题库里做对应题目 专题入口 专题导航页 模板总览与章节索引 在线题库入口 章节笔记 基础算法章节笔记 数据结构章节笔记 搜索与图论章节笔记 数学知识章节笔记 动态规划章节笔记 贪心专题章节笔记 内容结构目前每个章节笔记页都已经补了两部分： 该章节最核心的模板代码 对应题目的简要题解和切入思路 后面还会继续补： 每章代表题的完整代码 更详细的题型分类 容易写错的边界与坑点总结 说明如果你是第一次使用，建议先看： 模板总览与章节索引 如果你已经在做题，建议直接按章节进入对应笔记。
2026-05-28
AcWing 基础算法专题导航
AcWing 基础算法专题导航这篇文章是我整理的 AcWing 基础算法学习入口，用来配合在线题库、章节索引和模板合集一起使用。 这是什么这套内容的目标不是单纯刷题，而是把 题目分类、模板、典型题、复习路径 放在同一个体系里，方便： 初学时按章节推进 复习时按题型回查 卡题时快速定位对应模板 面试前做专题突击 适合谁 正在学基础算法与数据结构的同学 需要整理 AcWing 入门路线的人 想把“题目”和“模板”一一对应起来的人 如何使用1. 先按章节学，不要乱刷建议顺序： 基础算法 数据结构 搜索与图论 数学知识 动态规划 贪心与综合技巧 2. 每道题都对应到一个模板做题时不要只记答案，要先问自己两件事： 这题属于哪个章节、哪个小题型？ 它最终落到哪个模板？ 如果一道题做完之后还说不清它对应什么模板，那这题实际上还没有掌握。 3. 先看思路，再自己敲模板更推荐下面的使用方式： 先独立思考题意和做法 明确题型归属 对照模板查缺补漏 自己重新手敲一遍 最后做同类题巩固 4. 复习时按“章节 -> 模板 -> 题目”回看不要从零散题目开始复习，效率太低。更适...
2026-05-28
AcWing 基础算法章节笔记
AcWing 基础算法章节笔记基础算法这一章的关键，不是把题一题一题硬背下来，而是把“题型 -> 模板 -> 复杂度”这条线打通。 本章核心模板快速排序1234567891011void quick_sort(vector<int>& q, int l, int r) { if (l >= r) return; int x = q[(l + r) >> 1], i = l - 1, j = r + 1; while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j + 1, r);} 归并排序与逆序对123456789101112131415161718long long merge_...
2026-05-28
AcWing 贪心专题章节笔记
AcWing 贪心专题章节笔记贪心题的关键不在代码，而在于“为什么当前选择不会让未来更差”。如果这一点说不清，十有八九还不能直接上贪心。 本章核心模板区间选点 / 最大不相交区间数量1234567891011sort(segs.begin(), segs.end(), [](auto& a, auto& b) { return a.second < b.second;});int res = 0, ed = -2e9;for (auto [l, r] : segs) { if (l > ed) { res++; ed = r; }} 区间分组12345678910sort(segs.begin(), segs.end());priority_queue<int, vector<int>, greater<int>> heap;for (auto [l, r] : segs) { if (heap....
2026-05-28
AcWing 数学知识章节笔记
AcWing 数学知识章节笔记数学这一章题很多，但真正要背下来的核心模板并不算多。关键在于分清“结论”“适用条件”和“代码实现”。 本章核心模板质数 / 约数 / gcd12345678910bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) if (n % i == 0) return false; return true;}int gcd(int a, int b) { return b ? gcd(b, a % b) : a;} 线性筛1234567for (int i = 2; i <= n; i++) { if (!st[i]) primes[cnt++] = i; for (int j = 0; primes[j] <= n / i; j++) { st[primes[j] * i] = true; ...