小编整理的算法学习知识目录
读大学时，小编有幸参加过ACM算法比赛，也收集了不少算法模板，现在整理了一个算法目录，大家可以根据相关的介绍，找一些学习资料。学习某个算法时，大家可以使用关键字ACM+算法名称在搜索引擎搜索，搜出来的算法文章内容一般质量更高。
动态规划
- 「背包问题：」 解决背包问题的动态规划算法，涉及如何在有限容量下选择物品以达到最优价值。
- 「树形 DP：」 处理树形结构上的动态规划问题，通常通过递归或DFS来计算子树状态。
- 「状态压缩 DP：」 使用状态压缩技巧来简化动态规划问题，通常在状态较多时有效。
- 「概率 DP：」 利用概率的动态规划方法解决问题，考虑事件发生的可能性和期望价值。
- 「插头 DP：」 插头DP是一种处理序列问题的动态规划方法，通常用于求解字符串匹配等问题。
- 「区间 DP：」 解决涉及区间操作的动态规划问题，考虑如何将问题划分为多个互不重叠的区间进行求解。
- 「数位 DP：」 处理数字位操作的动态规划问题，通常用于解决数字相关的排列组合问题。
- 「最长公共子序列：」 使用动态规划求解两个序列中的最长公共子序列。
- 「最大连续和：」 动态规划方法解决数组中找出最大连续和的问题。
- 「数字三角形：」 利用动态规划处理三角形形状的数据结构，通常用于求解最优路径问题。
- 「最长上升子序列：」 使用动态规划找出序列中的最长上升子序列。
- 「贪心：」 贪心算法的应用，通常用于求解一些最优化问题，每一步都做出当前最优选择。
- 「嵌套矩形：」 解决嵌套矩形问题的动态规划算法，通常用于求解最大嵌套矩形数量。
- 「斜率优化 DP：」 在动态规划中使用斜率优化方法，通常用于优化状态转移方程的计算。
字符串算法
- 「最小表示法：」 最小表示法是用于求解循环同构字符串的算法，通过比较字符串的循环同构性质，找到字符串的最小表示形式。
- 「KMP 算法模板：」 Knuth-Morris-Pratt（KMP）算法是一种高效的字符串匹配算法，通过构建部分匹配表（next数组）来加速字符串匹配过程。
- 「扩展 KMP：」 扩展 KMP 算法是在 KMP 算法基础上拓展得到的，用于解决更复杂的字符串匹配问题，可以同时匹配多个模式串。
- 「AC 自动机：」 AC 自动机是一种用于多模式匹配的高效算法，利用Trie树和失败指针实现，在一个文本中同时查找多个模式串的出现位置。
- 「Trie 树：」 Trie 树（字典树）是一种用于存储动态集合或关联数组的树状数据结构，常用于字符串检索和前缀匹配。
- 「Manacher 算法：」 Manacher 算法用于查找字符串中的最长回文子串，通过预处理字符串，避免了传统动态规划算法中重复计算的问题，提高了效率。
- 「后缀数组：」 后缀数组是一种用于解决字符串相关问题的数据结构，它存储了字符串的所有后缀的排列顺序，可以高效解决很多字符串匹配和排序问题。
- 「括号匹配问题：」 解决括号匹配问题的算法，通过栈的数据结构或其他方法来判断字符串中的括号是否匹配正确。
- 「Hash 字符串：」 Hash 字符串是通过哈希函数将字符串映射为一个固定大小的哈希值，常用于加速字符串比较和匹配的过程，尤其在大规模文本数据中的应用。
数学专题
- 「剩余类：」 剩余类是解决同余方程的概念，通过对模数的选择，可以简化模运算的问题。
- 「扩展欧几里得：」 扩展欧几里得算法用于求解整数的最大公约数，并计算满足 Bézout 等式的系数。
- 「欧拉函数：」 欧拉函数是计算小于某个正整数的与该数互质的正整数个数，常用于解决模运算中的问题。
- 「莫比乌斯函数：」 莫比乌斯函数用于表示正整数的因数个数和符号，常用于组合数学和数论中的计算。
- 「乘法逆元：」 乘法逆元是对于给定的模数和整数，找到满足乘法逆元关系的整数，常用于解决除法取模的问题。
- 「素数：」 素数是仅有两个正因数（1和自身）的正整数，常用于解决数论和密码学中的问题。
- 「miller_rabin 和 pollard_rho：」 两种用于素数判定和整数分解的算法，分别基于 Miller-Rabin 素数测试和 Pollard Rho 整数分解算法。
- 「快速筛法：」 一种高效求解素数的算法，常用于生成素数表。
- 「大模拟：」 处理大整数运算和模运算的问题，包括高斯消元和分数加减乘除的实现。
- 「组合数学：」 解决组合数学中的问题，包括容斥定理的应用。
- 「卢卡斯定理：」 卢卡斯定理用于计算组合数的模，通过将组合数问题转化为模运算问题。
- 「Burnside 定理：」 Burnside 定理用于计算循环置换群的不动点数量，常用于组合计数问题。
- 「快速幂：」 快速幂算法是高效计算幂运算的方法，通过分治和二进制思想降低计算复杂度。
- 「中国剩余定理：」 中国剩余定理用于解决一组同余方程，通过对模数的两两互质性质降低问题的复杂度。
- 「高次同余方程：」 解决高次同余方程的问题，通过模运算和扩展欧几里得算法求解。
- 「鸽巢原理：」 鸽巢原理是一种基于抽屉原理的计数方法，常用于解决放置对象到有限数量的容器中的问题。
- 「数位统计问题：」 处理整数的数位表示和统计问题，通常用于计数问题的求解。
- 「二分搜索：」 二分搜索是一种通过减半搜索空间的方法，常用于解决有序数组或有序序列中的查找问题。
- 「三分搜索：」 三分搜索是一种通过减小或增大搜索空间的方法，常用于解决某个函数的极值问题。
- 「模拟退火：」 模拟退火是一种通过模拟物理退火过程的优化算法，常用于求解复杂问题的近似最优解。
- 「函数最值求解问题：」 解决函数最值问题的算法，通过搜索函数的极值点来找到最优解。
- 「TSP 问题：」 旅行商问题（TSP）是一种求解旅行商遍历所有城市的最短路径问题，通过动态规划等方法求解。
- 「卡特兰数：」 卡特兰数是一种计数数学中的数列，通常用于解决组合计数问题。
- 「那罗延数：」 那罗延数是一种数论中的数列，用于表示阶乘的另一种形式。
- 「平面上的直线问题：」 解决平面上直线交点等问题的算法，常用于几何学中的计算。
- 「伯努利数：」 伯努利数是一种数学中的数列，用于表示数学中的一些常见问题，如组合数。
- 「斐波那契数：」 斐波那契数列是一种数学中的数列，通过递归或动态规划求解。
- 「斯特林数：」 斯特林数是一种数学中的数列，用于计算排列组合问题。
- 「贝尔数：」 贝尔数是一种数学中的数列，表示将集合分割的方法数。
- 「进制转换模板：」 处理进制转换问题的算法模板，通常用于不同进制间的数值转换。
- 「异或的一道题：」 解决异或运算相关的问题，常用于位运算和密码学中。
- 「错排问题：」 错排问题是一种计数问题，表示排列中所有元素都不在其原始位置上的方法数。
- 「快速傅里叶变换：」 快速傅里叶变换是一种高效计算离散傅里叶变换的算法，常用于信号处理和多项式求解。
- 「快速数论变换：」 快速数论变换是一种高效计算离散傅里叶变换的算法，常用于数论和密码学中。
- 「线性规划模板：」 解决线性规划问题的算法模板，通常用于优化问题的求解。
数据结构专题
- 「Vector、Pair：」 Vector是C++标准模板库(STL)中的动态数组实现，Pair是一个可以容纳两个不同类型的值的模板类，常用于构建简单的数据结构。
- 「Bitset：」 Bitset是C++标准模板库(STL)中的一个类，用于存储位序列，支持位运算，通常用于位操作和压位。
- 「优先队列：」 优先队列是一种支持高效插入和删除最大或最小元素的数据结构，通常用堆实现。
- 「双端队列：」 双端队列是一种允许在两端进行插入和删除操作的数据结构，常用于需要在队列两端进行操作的场景。
- 「二叉堆：」 二叉堆是一种特殊的堆实现，分为最大堆和最小堆，常用于优先队列的底层实现。
- 「Map：」 Map是C++ STL中的关联容器，实现了键-值对的存储和访问，通常基于红黑树实现。
- 「Multimap：」 Multimap是Map的一种变体，允许多个相同键对应不同的值，通常用于多对一关系的存储。
- 「Set：」 Set是C++ STL中的关联容器，存储唯一值的有序集合，通常基于红黑树实现。
- 「求交集、并集、对称差积的自带函数：」 C++ STL提供了用于集合操作的算法函数，包括set_intersection、set_union、set_symmetric_difference等，用于求两个集合的交集、并集、对称差积。
- 「Stack：」 Stack是C++ STL中的容器适配器，实现了后进先出（LIFO）的操作，通常基于deque实现。
- 「区间查询：」 区间查询是一类数据结构和算法，包括树状数组、ST算法、滚动实现ST、线段树等，用于处理区间查询和更新操作。
- 「树状数组：」 一种用于高效计算前缀和的数据结构，支持单点更新和区间查询。
- 「ST算法：」 通过预处理得到每个区间内的最值，用于高效查询区间最值。
- 「滚动实现ST：」 对ST算法的一种优化，通过滚动更新方式减小计算复杂度。
- 「线段树：」 一种用于高效处理区间查询和更新的数据结构，通常用于解决一维和二维区间问题。
博弈论
- 「巴什博奕：」 巴什博奕是一种经典的博弈问题，两个玩家轮流从一堆物品中取若干个，每次可以取1至m个，最后取光者获胜，通过分析得到取胜策略。
- 「威佐夫博弈：」 威佐夫博弈是一种博弈问题，两个玩家轮流从两堆物品中取若干个，每次可以取相同数量，最后取光者获胜，通过数学方法得到取胜策略。
- 「斐波那契博弈：」 斐波那契博弈是一种博弈问题，两个玩家轮流从一堆物品中取若干个，每次可以取斐波那契数个，最后取光者获胜，通过分析得到取胜策略。
- 「尼姆博弈：」 尼姆博弈是一种经典的博弈问题，有若干堆物品，两个玩家轮流取若干个，每次可以取一堆的任意数量，最后取光者获胜，通过异或运算得到取胜策略。
- 「组合博弈：」 组合博弈是一类博弈问题，通过多个独立的博弈状态的组合，推导出整个博弈的胜负情况，常用于解决一些复杂的博弈问题。
- 「Sg 定理：」 Sg（Sprague-Grundy）定理是一种数学定理，用于分析组合游戏的必胜态和必败态，通过计算游戏状态的Grundy数。
- 「Sg 模板：」 Sg（Sprague-Grundy）模板是通过计算每个局面的Grundy数，从而判断整个博弈的胜负情况，通常使用深度优先搜索（DFS）实现。
图论
- 「二叉树层次遍历：」 通过广度优先搜索（BFS）实现，按层次遍历二叉树的节点，逐层访问。
- 「二叉树递归遍历：」 通过深度优先搜索（DFS）实现，递归遍历二叉树的节点，包括先序、中序和后序遍历。
- 「求连通块的方法及相关题目：」 通过深度优先搜索（DFS）或广度优先搜索（BFS）实现，找出图中的所有连通块，常用于解决图的连通性问题。
- 「欧拉回路：」 欧拉回路是指通过图中每条边一次且仅一次，最后回到起点的路径。通过深度优先搜索（DFS）实现，通常用于解决图的遍历问题。
- 「最小生成树：」 通过Prim算法或Kruskal算法实现，找出连通图中权重和最小的生成树，常用于解决网络布线和城市规划问题。
- 「克鲁斯卡尔算法：」 通过贪心策略，按边权递增的顺序选择边，构建最小生成树。
- 「最短路：」 通过Dijkstra算法或Bellman-Ford算法实现，找出图中两点之间最短路径，常用于解决路径规划问题。
- 「拓扑排序：」 通过深度优先搜索（DFS）或广度优先搜索（BFS）实现，找出有向无环图中节点的一种线性序列，用于表示事件的发生顺序。
- 「第 k 短路：」 通过最短路算法的变种实现，找出图中第 k 短的路径。
- 「最近公共祖先：」 通过Tarjan算法或倍增法实现，找出有根树或森林中两个节点的最近公共祖先。
- 「最大匹配：」 通过匈牙利算法实现，找出二分图中边数最大的匹配。
- 「强连通：」 通过Kosaraju算法或Tarjan算法实现，找出有向图中的所有强连通分量。
- 「双连通分量：」 通过割点和桥的概念实现，找出无向图中的双连通分量。
- 「割点和桥：」 通过DFS实现，找出无向图中的割点和桥。
- 「主席树：」 通过线段树的变种实现，支持区间修改和区间查询。
- 「树的同构：」 通过哈希或DFS实现，判断两棵树是否同构。
- 「最大团问题：」 通过图论算法实现，找出无向图中的最大完全子图。
- 「费用流：」 通过网络流算法实现，找出网络中的最小费用最大流。
- 「2-sat 问题：」 通过拓扑排序和缩点实现，判断一个布尔公式是否可满足。
- 「二分图最大匹配：」 通过匈牙利算法实现，找出二分图中边数最大的匹配。
- 「二分图最佳完美匹配：」 通过带权匈牙利算法实现，找出二分图中边权和最大的完美匹配。
- 「稳定婚姻：」 通过稳定婚姻算法实现，找出一个稳定的婚姻匹配方案。
几何专题
- 「几何模板：」 提供了一系列几何学基本操作和算法，包括点、线、面的表示与计算，以及几何问题的解决方法。
- 「极角排序：」 通过计算点相对于参考点的极角，实现对点集的极角排序，通常用于解决凸包等几何问题。
- 「凸包：」 通过Graham扫描法或Jarvis算法实现，找出给定点集的最小凸多边形，通常用于解决点集的包围问题。
- 「求凸包周长：」 通过遍历凸包的边，计算其长度之和，得到凸包的周长。
- 「回溯法：」 回溯法是一种穷举搜索的算法，通过递归实现，通常用于解决组合优化、排列组合等问题。
- 「八皇后问题：」 八皇后问题是回溯法的典型应用，通过递归搜索所有可能的放置方式，找出八个皇后不相互攻击的摆放方案。
- 「打印两点之间全部路径：」 通过深度优先搜索（DFS）实现，找出两点之间的所有路径，并输出。
- 「Cdq 分治：」 Cdq分治是一种高效解决一维偏序问题的算法，通常用于解决一些复杂的计算几何问题。
- 「Kd-tree：」 Kd-tree是一种空间划分树，通过递归地对k维空间进行划分，用于高效地进行范围查询。
- 「DLX 舞蹈链算法：」 舞蹈链是一种实现精确覆盖问题的数据结构，通常用于解决数独等问题。
- 「回文树：」 回文树是一种用于处理回文串的数据结构，通过动态维护回文串的信息，用于解决回文串相关的问题。
- 「动态树：」 动态树是一种支持树上路径操作的数据结构，通过维护轻链和重链实现动态修改。
