我的算法书 - 题目模式识别

第一章基础数据结构

题面特征	可能的思考方向 (触发器)	经典/备注	经典题目 (必刷)
只涉及两端的插入删除 / “滑动窗口” / “保持队列单调性”	双端队列 / 单调队列	滑动窗口最大值	P1886 滑动窗口 LeetCode 239
“后进先出” / “括号匹配” / “后缀表达式”	栈 (Stack)	简单的语法解析	P1739 表达式括号匹配 P1449 后缀表达式
“找左边/右边第一个比它大/小的数”	单调栈	接雨水, 柱状图最大矩形	P5788 单调栈模板 LeetCode 84 (柱状图)
“中位数动态维护” / “动态第 K 大”	堆 (Heap) / 优先队列	对顶堆维护中位数	P1168 中位数 P1090 合并果子
“合并果子” / “最小代价合并” / “带权路径长度最短”	哈夫曼树 (Huffman)	贪心合并策略	P1090 合并果子
“最近最久未使用 (LRU)” / “频繁的中间删除与插入”	双向链表	通常结合 Hash 使用	LeetCode 146 LRU缓存

第二章基本算法

题面特征	可能的思考方向 (触发器)	经典/备注	经典题目 (必刷)
“区间和” / “求某段连续子数组的和”	前缀和	二维前缀和	P1719 最大加权矩形 P1387 最大正方形
“区间修改，单点查询” / “原序列差分后变单点修改”	差分数组	频繁区间加减	P1083 借教室 P3397 地毯
“连续子区间” + “满足某条件”	尺取法 / 滑动窗口	找和 $\ge S$ 的最短子数组	P1638 逛画展 POJ 3061
“最大值最小” / “最小值最大”	二分答案	Check 函数判定	P2440 木材加工 P2678 跳石头
“求单峰函数的极值” (如抛物线)	三分法	物理/几何求极值	P3382 三分法模板
“静态区间最值查询 (RMQ)” / “不可修改”	ST 表	倍增思想	P3865 ST 表模板
“求第 K 个祖先” / “路径上的跳跃”	倍增法	LCA 的基础	P3379 LCA 模板
“坐标范围很大 ( $10^9$ )” 但 “点数很少”	离散化	只关心相对大小	P1496 火烧赤壁 P1955 程序自动分析
“求逆序对” / “只交换相邻元素还原序列的最小次数”	归并排序 / 树状数组		P1908 逆序对
“区间调度” / “局部最优致全局最优”	贪心	活动安排问题	P1803 凌乱的yyy P1223 排队接水

第三章搜索

题面特征	可能的思考方向 (触发器)	经典/备注	经典题目 (必刷)
“最小步数” / “最短路” (边权为1)	BFS	迷宫问题	P1443 马的遍历 P1162 填涂颜色
“连通块计数” / “填充颜色”	Flood Fill	岛屿数量	LeetCode 200 岛屿数量
“求所有方案” / “全排列” / “棋盘摆放”	DFS + 回溯	N 皇后, 数独	P1219 八皇后 P1784 数独
“已知起点和终点” + “状态空间巨大但深度已知”	双向广搜	单词接龙, 华容道	P1379 八数码难题
“网格图最短路” + “有启发式估价函数”	*A 算法**	K 短路问题	*P1379 八数码 (A版)** P2483 K短路
“状态极多” + “要求最短路” + “内存受限”	IDA*	埃及分数	P1763 埃及分数 P2324 骑士精神
“决策树极大” / “博弈”	Minimax + Alpha-Beta	棋类 AI	LeetCode 486 预测赢家

第四章高级数据结构

题面特征	可能的思考方向 (触发器)	经典/备注	经典题目 (必刷)
“判断连通性” / “集合合并”	并查集 (DSU)	关押罪犯	P3367 并查集模板 P1525 关押罪犯
“边带权值的集合关系” (A比B大1…)	带权并查集	食物链	P2024 食物链 P1196 银河英雄传说
“单点修改 + 区间查询” / “求逆序对”	树状数组 (BIT)	简单高效	P3374 树状数组 1
“区间修改 + 区间查询”	线段树	懒标记	P3372 线段树 1 P3373 线段树 2
“查询历史版本” / “静态区间第 K 小”	主席树	强制在线	P3834 可持久化线段树 1
“离线区间查询” + “区间端点移动代价小”	莫队算法	奇偶排序优化	P1494 小Z的袜子 P2709 小B的询问
“树上两点的距离” / “树上路径信息”	LCA	倍增或 Tarjan	P3379 LCA 模板
“修改树上路径权值” / “修改子树权值”	树链剖分	树拉直成序列	P3384 树链剖分模板
“平衡树操作” + “区间翻转/移动”	Splay / FHQ Treap	文艺平衡树	P3369 普通平衡树 P3391 文艺平衡树
“动态维护森林连通性” / “动态加删边”	LCT	动态树问题	P3690 LCT 模板
“二维平面最近点对”	K-D Tree	多维二分	P1429 平面最近点对

第五章动态规划 (DP)

题面特征	可能的思考方向 (触发器)	经典/备注	经典题目 (必刷)
“N $\le$ 20” / “集合状态” / “哈密顿路径”	状压 DP	TSP 问题	P1879 Corn Fields P1896 互不侵犯
“求区间 $[L, R]$ 内满足某条件的数”	数位 DP	不要 62	P2602 数字计数 P2657 Windy 数
“合并石子” / “括号匹配”	区间 DP	枚举断点	P1880 石子合并 P1063 能量项链
“树上最大独立集” / “树的直径”	树形 DP	选父不选子	P1352 没有上司的舞会 P2015 二叉苹果树
“求总方案数” + “N 很大” + “线性递推”	矩阵快速幂优化	斐波那契	P1939 矩阵加速 P1962 斐波那契
“状态转移方程类似 $dp[i] = \min(dp[j]) + \dots$ ”	单调队列优化	滑动窗口最值	P1886 滑动窗口 (DP基础) P2627 修剪草坪
“状态转移含乘积项” ( $A[i] \times B[j]$ )	斜率优化	维护凸包	P3195 玩具装箱 P2365 任务安排
“区间 DP 的决策点单调”	四边形不等式优化		P1880 石子合并 (优化版)

第六章数论与线性代数

题面特征	可能的思考方向 (触发器)	经典/备注	经典题目 (必刷)
“最大公约数” / “不定方程”	GCD / ExGCD	裴蜀定理	P1082 同余方程 P5656 ExGCD模板
“求逆元” / “组合数取模”	费马小定理 / 逆元	$a^{p-2}$	P3811 乘法逆元
“求 $1 \sim N$ 中与 $N$ 互质的数”	欧拉函数	欧拉定理	P2158 仪仗队 P2303 Longge的问题
“求解模线性方程组” (韩信点兵)	中国剩余定理 (CRT)	模数互质	P1495 曹冲养猪
“大组合数取模” ( $N$ 大, $P$ 小)	卢卡斯定理		P3807 Lucas 模板
“求解异或方程组” / “子集异或最大值”	线性基	异或空间基底	P3812 线性基模板
“求解线性方程组” / “图的生成树计数”	高斯消元	矩阵行列式	P3389 高斯消元模板
“求 $\sum \lfloor n/i \rfloor$ ”	数论分块	$O(\sqrt{n})$	P2261 余数求和
“涉及 GCD 求和” / “含有 $\mu$ 函数”	莫比乌斯反演		P2522 Problem b P2257 YY的GCD
“0/1 分数规划” ( $\max \frac{\sum a}{\sum b}$ )	二分答案		POJ 2976 Dropping Tests
“前缀和求得慢 ( $N=10^9$ )”	杜教筛	积性函数前缀和	P4213 杜教筛模板

第七章组合数学

题面特征	可能的思考方向 (触发器)	经典/备注	经典题目 (必刷)
“证明存在性” / “同余类个数”	鸽巢原理		POJ 2356 Find a multiple
“求方案数” / “多重集组合”	二项式定理 / 组合数		P1313 计算系数
“合法方案 = 总方案 - 非法方案”	容斥原理	错排问题	P1450 硬币购物 P2197 lookback
“进出栈序列数” / “多边形三角剖分”	卡特兰数		P1044 栈
“第一类/第二类斯特林数”	Stirling Number	环排列/集合划分	P1287 盒子与球
“本质不同的染色方案”	Burnside / Polya	群论计数	POJ 2409 Let it Bead
“博弈游戏” / “多堆石子取物”	SG 函数 / Nim 游戏	异或和为 0	P2197 Nim游戏

第八章计算几何

题面特征	可能的思考方向 (触发器)	经典/备注	经典题目 (必刷)
“点在直线的哪一侧” / “线段相交”	叉积	右手法则	POJ 1269 Intersecting Lines
“围住所有点的最小周长多边形”	凸包	Andrew 算法	P2742 二维凸包模板
“最远点对” / “最小矩形覆盖”	旋转卡壳	基于凸包	P1452 Beauty Contest
“矩形面积并” / “轮廓线长度”	扫描线	线段树维护	P5490 扫描线模板
“半平面交” / “多边形核”	半平面交算法	线性规划	P4196 半平面交模板

第九章字符串

题面特征	可能的思考方向 (触发器)	经典/备注	经典题目 (必刷)
“字符串匹配” / “判断字符串相等”	哈希 (Hash)	滚动哈希	P3370 字符串哈希模板
“最长回文子串”	Manacher	$O(N)$ 复杂度	P3805 Manacher 模板
“多模式串匹配”	AC 自动机	Trie + KMP	P3808 AC自动机模板
“前缀出现次数” / “循环节”	KMP	Next 数组	P3375 KMP 模板 POJ 2406 Power Strings
“异或最大值” / “前缀查询”	字典树 (Trie)	01-Trie	P2580 于是他错误的… P4551 最长异或路径
“最长公共子串” / “本质不同子串”	SA / SAM	终极武器	P3804 后缀自动机模板 P3809 后缀排序
“回文串计数” / “本质不同回文串”	回文树 (PAM)		P5496 回文自动机模板

第十章图论 (重中之重)

题面特征	可能的思考方向 (触发器)	经典/备注	经典题目 (必刷)
“依赖关系” / “有向无环图”	拓扑排序	判环	P1038 神经网络 P4017 最大食物链计数
“所有边恰好经过一次”	欧拉路	一笔画	P6066 Watchcow P7771 欧拉路径模板
“任意两点间最短路” / N $\le$ 500	Floyd	传递闭包	P1364 医院设置
“单源最短路” + “非负边权”	Dijkstra	堆优化	P4779 单源最短路模板
“单源最短路” + “负权边”	SPFA	判负环	P3385 负环
“连通所有点的最小代价”	最小生成树 (MST)	Kruskal	P3366 最小生成树模板
“强连通分量 (SCC)” / “缩点转 DAG”	Tarjan	缩点做 DP	P2863 The Cow Prom P3387 缩点
“割点 / 割边” / “必经点”	Tarjan (无向图)	连通性	P3388 割点模板
“二分图匹配” / “最小点覆盖”	匈牙利 / 网络流	柯尼希定理	P3386 二分图匹配模板
“流量分配” / “最大收益”	最大流	Dinic	P3376 最大流模板 P2756 飞行员配对
“花费最小代价割断图”	最小割	最大流最小割定理	P2763 试题库问题
“流量有费用” / “总成本最低”	最小费用最大流	SPFA 找增广路	P3381 MCMF 模板
“N个点 N条边” / “树上多了一条边”	基环树	拆掉环上一条边	P2607 骑士
“布尔变量满足条件”	2-SAT	建图跑 SCC	P4782 2-SAT 模板
“DAG最少路径覆盖所有点”	最小路径覆盖	转化为二分图匹配	P2764 最小路径覆盖

如何使用这个表格？

索引而非背诵：不要死记硬背。当你做题卡住时，看一眼题目属于哪个领域（比如是图论），然后扫一遍该领域的“题面特征”，看看有没有哪个击中了你。
不断扩充：遇到一个新题，如果它用了一个你没想到的模型（比如 P6628 把重复走转化为欧拉回路），就把它加到表格对应的备注里。
组合拳：省选/NOI 难度的题目通常是 2-3 个特征的组合。比如“树上”+“第K大” -> 主席树上树；“网格图”+“最短路”+“钥匙限制” -> 分层图最短路。

这个表格是你建立**“条件反射”**的基石。加油！