算法汇总大全

明白了，你的要求是：既要覆盖所有算法大类（像第二个表格那样全），又要对每个算法都写出“在题目中的具体用途”（像第三个表格那样细）。下面是一个合并后的完整表格：

排序算法

算法	在题目中的具体用途
快速排序	一般性排序的默认选择，配合 `nth_element` 可用于求第 k 大/小的元素（快速选择）。
归并排序	需要稳定排序时使用；求逆序对数量（归并过程中统计）；链表排序。
堆排序	实现优先队列，用于动态维护最值，如 Dijkstra 中的取最小点、多路归并中的取最小元素。
计数排序	数据范围小且为整数时，线性排序；常见于基数排序的低位排序。
基数排序	对整数或定长字符串按位排序，例如后缀数组（SA）的倍增优化中用于对二元组排序。
桶排序	数据均匀分布时线性排序，或在分块中用于维护块内元素的快速排序。

搜索算法

算法	在题目中的具体用途
DFS（深度优先搜索）	图的连通性检测（求连通块）；拓扑排序的递归实现；树的重心/直径的递归求解；剪枝搜索（如八皇后、数独）。
BFS（广度优先搜索）	无权图的最短路；分层遍历（如求矩阵中从起点到终点的最短步数）；状态转移的最少步数（如八数码问题）。
双向 BFS	已知起点和终点的最短路搜索，状态空间爆炸时可将复杂度降至 O(b^(d/2))，如“单词接龙”、“K 步之内能否到达”。
*A 算法**	有可行启发函数（如曼哈顿距离）的最短路搜索，如八数码、K 短路的辅助搜索。
IDA*	结合迭代加深和 A*，用于空间受限且启发函数良好的搜索，典型如“骑士周游”或“十五数码”。
迭代加深 DFS	搜索树深度较大但答案深度较浅，且 DFS 可能陷入死循环时使用，如“埃及分数”问题。

动态规划 (DP)

算法	在题目中的具体用途
线性 DP	解决 LIS（最长上升子序列）、LCS（最长公共子序列）、背包问题（0/1背包、完全背包、多重背包）、最大子段和等基础序列问题。
区间 DP	区间合并或分割的最优解，如“石子合并”（最小/最大得分）、“矩阵链乘”、“回文串分割”等。
树形 DP	树上统计问题：树的直径、树上最大独立集（选不相邻点的最大权）、树上背包（如“选课”问题，依赖关系形成树）、换根 DP（求每个点到所有点的距离和）。
状压 DP	状态为集合（n ≤ 20），典型应用：TSP（旅行商问题）、覆盖问题（用多米诺骨牌覆盖棋盘）、分配问题（如“排列”的最优值）。
数位 DP	统计区间 [L,R] 内满足特定数字性质（如不含 4、各位和能被 K 整除、数字单调递增）的数的个数。
插头 DP	解决棋盘上的连通性状态压缩问题，如“棋盘覆盖”、“回路计数”、“哈密顿路径计数”等，常见于 n,m ≤ 12 的网格。
斜率优化	优化转移方程形如 dp[i] = min(dp[j] + (sum[i]-sum[j])² + C) 的 DP，将 O(n²) 降为 O(n)，经典题如“玩具装箱”、“土地购买”。
四边形不等式优化	当 cost(l,r) 满足四边形不等式时，优化区间 DP 的决策点，将 O(n³) 降为 O(n²)，如“石子合并”的优化版本。
WQS 二分（带权二分）	解决“恰好选 K 个”的 DP 最优化问题。通过二分附加惩罚项，将限制转化为无限制 DP，经典题如“Aliens trick”、“邮局问题”的变体。
CDQ 分治优化 DP	将 DP 的转移视为偏序关系，用 CDQ 分治处理左半部分对右半部分的贡献，常用于三维偏序下的 DP 优化。

图论

图论基础

算法	在题目中的具体用途
拓扑排序	DAG 上的 DP（如最长路、方案数）；判断图中是否有环；任务调度（课程表问题）；依赖关系处理（如编译顺序）。
欧拉回路/路径	一笔画问题：判断能否不重复地经过所有边，并输出路径（如“单词接龙”中拼接欧拉路径）。
哈密尔顿回路/路径	NP 完全问题，仅在 n ≤ 20 时用状压 DP 求是否存在经过每个点恰好一次的路径（TSP 的变体）。
2-SAT	求解布尔变量之间的成对约束（如“A 为真或 B 为假”），典型题如“Peaceful Commission”（和平委员会）、雷达站布局问题。

最短路

算法	在题目中的具体用途
Dijkstra（堆优化）	非负权单源最短路，适用于稀疏图（O(m log n)），如“最短路计数”、“最短路径输出”。
SPFA	处理含负权边的单源最短路；判断负环（如“虫洞”问题）。注意在 OI 中常被卡，建议谨慎使用。
Bellman-Ford	功能同 SPFA，但复杂度高（O(nm)），通常只用于理论证明或极小的图。
Floyd-Warshall	多源最短路（n ≤ 400）；传递闭包（判断两点是否可达）；最小环（求图中最小权值的环）。
差分约束	将形如 x_i - x_j ≤ c 的不等式组转化为最短路问题，求解一组可行解，典型如“糖果”问题（求最小值）。
K 短路	求从 s 到 t 的第 K 短路径，常用 A* 算法（估价函数为当前点到终点的最短路）或 Yen 算法。

生成树

算法	在题目中的具体用途
Kruskal	最小生成树（MST），适用于稀疏图；次小生成树（枚举非树边替换树边）。
Prim	最小生成树（MST），适用于稠密图（O(n²) 或 O(m log n)）。
Kruskal 重构树	构建“最小瓶颈路”的树形结构，解决树上两点路径中最大边权最小值的问题；也用于处理动态连通性下的查询。
Matrix-Tree 定理	计算生成树个数，用于无向图或有向图的生成树计数问题。
斯坦纳树	在图中连接指定点集（关键点）的最小树，通常用状压 DP 解决，典型应用如“最小费用连接若干城市”。
朱刘算法	求解有向图的最小树形图（以某点为根，能到达所有点的最小总边权）。

连通性

算法	在题目中的具体用途
Tarjan（求 SCC）	将有向图缩点为 DAG，用于后续 DP、拓扑排序；解决 2-SAT 问题；判断强连通关系。
Tarjan（求割点）	识别网络中删除后会使连通分量增多的关键节点，如“服务器故障”问题。
Tarjan（求桥）	识别删除后会使连通分量增多的关键边，如“网络连接可靠性”分析。
Tarjan（求点双/边双连通分量）	用于缩成点双连通分量树或边双连通分量树，处理仙人掌图问题或路径必经点/边查询。
圆方树	将一般图（或仙人掌图）转化为树，将图上的最短路、DP、连通性问题转化为树上问题。

二分图

算法	在题目中的具体用途
二分图判定（染色法）	判断一个图是否为二分图，如“关押罪犯”问题中二分答案后用染色法验证。
匈牙利算法	求解二分图最大匹配（无权），典型题如“假期的宿舍”、“机器任务分配”、“棋盘放置（车、马）”。
KM 算法	求解二分图带权最大匹配（完美匹配），如“运动员最佳匹配”、“任务与工人”的最优分配。

网络流

算法	在题目中的具体用途
Dinic / ISAP	最大流：求解“圆桌问题”（单位代表不能同桌）、“教辅的组成”（书-练习册-答案三级匹配）、“最大闭合权图”（选项目必须选前置项目）、“二分图最大匹配”（比匈牙利更高效）。
费用流（SSP / Primal-Dual）	最小费用最大流：带权匹配、运输问题、任务调度（成本最小化）。
带上下界网络流	处理边的流量有上下限的问题，如“有源汇可行流”、“最小费用可行流”，用于“网络扩容”等实际问题。

树相关

算法	在题目中的具体用途
LCA（倍增/Tarjan/树剖）	求树上两点的最近公共祖先；支持路径距离查询（dist = depth[u]+depth[v]-2depth[lca]）；路径上点权/边权修改与查询*（配合树链剖分）。
树链剖分（重链剖分）	路径操作：将路径拆成 O(log n) 个区间，用线段树维护，支持路径加、路径求和、路径最大值；子树操作：利用 DFS 序转为区间；求 LCA。
长链剖分	优化与深度相关的 DP，如“树上 k 级祖先”的 O(1) 查询，或“树上深度相关统计”的 O(n) 合并。
点分治	统计树上所有路径的信息，如“路径长度为 K 的路径条数”、“路径上点权异或和为 0 的路径数”、“距离小于等于 K 的点对数”。
虚树	多次询问，每次只涉及树上少数关键点，构建只含关键点及其 LCA 的压缩树，优化树形 DP，如“战争”、“消耗战”问题。
DSU on Tree（树上启发式合并）	离线统计子树内信息（如子树颜色种数、众数），将 O(n²) 优化到 O(n log n)，典型题“树上数颜色”。
动态树（LCT）	维护动态森林：支持加边、删边、连通性查询、路径异或和、路径最值等操作，用于“动态 MST”、“树上路径修改与查询”。

其他

算法	在题目中的具体用途
MCS（最大势算法）	用于弦图的完美消除序列（PEO）求解；进而求弦图的最大团、最小色数、最大独立集等。
仙人掌图判定与处理	判断每条边是否至多属于一个简单环，然后利用圆方树将仙人掌转化为树，处理最短路、DP 等问题。

字符串

算法	在题目中的具体用途
KMP	单模式串匹配（判断 s 是否在 t 中出现）；利用 PMT 求循环节（如“Period”问题）；求最短周期。
扩展 KMP（Z 算法）	求原串的每个后缀与模式串的 LCP（最长公共前缀）；用于字符串匹配、重复子串检测。
Trie（字典树）	字符串前缀查询（如自动补全）；异或最大对（将数字二进制插入 Trie，贪心查找）；AC 自动机的前置结构。
AC 自动机	多模式串匹配：给定文本串，输出所有模式串出现的位置和次数；在 Trie 上做 DP（如“病毒”问题，找不含某些模式串的字符串）。
后缀数组（SA）	求不同子串个数；结合 height 数组求任意两后缀的 LCP；最长重复子串；模式串出现次数（二分查找区间）。
后缀自动机（SAM）	子串出现次数统计；本质不同子串个数；最长公共子串（多串）；字典序第 K 大子串；子串是否存在。
Manacher	最长回文子串；回文子串总数统计。
回文自动机（PAM）	统计本质不同回文子串个数及其出现次数；支持在末尾添加字符后动态维护回文信息。
字符串哈希（双哈希）	快速比较任意两个子串是否相等（O(1)）；配合二分求 LCP；用于模式串匹配、去重，需注意防卡哈希。

数学

数论

算法	在题目中的具体用途
欧几里得 / 扩展欧几里得	求 gcd；解 ax + by = c 的整数解；求模质数下的逆元。
素数筛（埃氏/欧拉线性筛）	预处理素数表、最小质因子（用于快速质因数分解）、欧拉函数 φ(n)、莫比乌斯函数 μ(n)。
快速幂 / 矩阵快速幂	计算大数幂取模（如 a^b mod p）；线性递推加速（如斐波那契数列的第 n 项，用矩阵快速幂 O(log n)）。
Miller-Rabin	大素数判断（概率性），常用于 Pollard-Rho 的前置步骤。
Pollard-Rho	大整数因数分解，用于 n ≤ 1e18 的情况。
BSGS / exBSGS	求解离散对数：a^x ≡ b (mod p) 的最小非负整数 x。
中国剩余定理（CRT） / exCRT	求解同余方程组：x ≡ a_i (mod m_i)，模数互质用 CRT，不互质用 exCRT。

组合数学

算法	在题目中的具体用途
组合数预处理（阶乘+逆元）	处理多次查询 C(n,k) mod p（p 为大质数），O(1) 回答。
Lucas / exLucas	求 C(n,k) mod p，其中 p 为小质数（Lucas），或 p 为任意数（exLucas）。
容斥原理	计算多个集合并集大小，如“错排问题”、“多个约束条件的计数”。
莫比乌斯反演	处理数论函数与卷积，经典题如“求 gcd=1 的数对个数”、“约数个数和”。
Polya 定理	等价类计数（如旋转/翻转下不重复的染色方案数）。
卡特兰数 / 斯特林数	卡特兰数：括号匹配、出栈序列、二叉数形态数；斯特林数：集合划分、排列统计。

线性代数

算法	在题目中的具体用途
高斯消元	解线性方程组（实数或模意义）；求矩阵的秩；解异或方程组（如“开关灯”问题）。
线性基	维护一组数的异或空间，求最大值、最小值、第 K 小；判断某数能否被异或表示；典型题“XOR 最大”、“异或第 K 大”。

多项式

算法	在题目中的具体用途
FFT / NTT	加速多项式乘法，用于大整数乘法、卷积型 DP 优化、生成函数计算。
FWT	加速位运算卷积（AND / OR / XOR 卷积），用于集合幂级数相关 DP。
多项式求逆/ln/exp	用于生成函数的更高级运算，如求组合数幂级数、生成函数封闭形式。

博弈论

算法	在题目中的具体用途
Nim 游戏	经典公平组合游戏：判断胜负（异或和是否为 0），求必胜方案。
SG 函数	将任意公平组合游戏转化为 Nim 和：对每个状态求 mex{后继的 SG}，异或判断胜负，用于“取石子变体”、“棋盘棋子移动”。
威佐夫博弈 / 斐波那契博弈	特定规则的双人博弈，直接套用公式判定（如威佐夫：判断 (a,b) 是否满足奇异局势）。
树上删边游戏	树上的删边博弈，通过 SG 定理 + 树的“ Green Hackenbush ” 转化为异或问题。
图博弈	在有向图上移动棋子的公平博弈，用 DFS 记忆化搜索求每个点的 SG 值，或直接判定胜负态（如“图上取石子”）。
对抗搜索（Alpha-Beta 剪枝）	用于双人完全信息博弈的搜索，如国际象棋、五子棋的 AI 决策（OI 中较少考）。

数据结构

数据结构	在题目中的具体用途
并查集	动态连通性：维护集合合并与查询；Kruskal 的前置；带撤销并查集用于离线分治。
带权并查集	维护集合内元素间的距离/差值关系，如“食物链”（种类关系）、“奇偶游戏”（前缀异或关系）。
树状数组	单点修改 + 区间查询（如求逆序对）；区间修改 + 单点查询（差分实现）；二维树状数组。
线段树	区间修改 + 区间查询（求和、最值、gcd）；扫描线求矩形面积并；动态开点线段树；线段树合并。
主席树（可持久化线段树）	静态区间第 K 大；动态区间第 K 大（配合树状数组）；历史版本查询；树上路径第 K 大（配合树链剖分/主席树前缀和）。
平衡树（Treap / Splay）	动态有序序列：插入、删除、前驱后继、排名查询；区间翻转（Splay）；文艺平衡树。
左偏树 / 配对堆	可并堆：支持合并两个堆，用于堆优化 Dijkstra 的变体或“猴子打架”问题。
分块	根号暴力优化：维护区间修改/查询，复杂度 O(√n)，常用于替代复杂数据结构，如“数列分块入门”系列。
莫队算法	离线区间查询：已知 [l,r] 的答案可 O(1) 扩展到相邻区间，处理大量区间询问（如区间众数、区间不同数个数）。带修莫队支持单点更新；树上莫队处理树上路径查询。
KD-Tree	多维空间最近邻/最远点对搜索，也可用于高维偏序查询。

其他重要思想与技巧

思想/技巧	在题目中的具体用途
贪心	局部最优即全局最优：区间调度（选择最多不相交区间）、哈夫曼编码、删数问题。
二分答案	答案具有单调性时，将最优化问题转化为判定性问题，如“最大值最小化”（最小化最大边权）、“最小值最大化”（最大化最小间距）。
三分	求单峰函数的极值，如“凸函数最值”、“曲线凸性优化”。
CDQ 分治	偏序问题（如三维偏序计数、逆序对变体）；DP 优化（用左半更新右半）。
整体二分	同时处理多个具有单调性的询问（如区间第 K 大），将二分答案和数据结构合并处理。
扫描线	处理矩形面积并/周长并；区间覆盖事件（如给每个区间赋权，求总覆盖长度）。
模拟退火 / 爬山	求解最优化问题的近似解（如计算几何中的最小覆盖圆），OI 中仅作为骗分或最后手段。
分数规划	求解形如最大化 `Σ(a_i) / Σ(b_i)` 的问题，如“最优比率生成树”、“最优比率环”（结合二分 + 最短路/生成树）。

这个表格覆盖了从基础排序到冷门算法（MCS、WQS、插头 DP、图博弈等）的全部内容，并对每个算法都给出了它在具体题目中的典型用途。如有遗漏或需要进一步补充的，随时告诉我。