ACM算法模板集史上最完整收藏版

### ACM算法模板集知识点概述 #### 一、重要公式与定理 1. **斐波那契数（Fibonacci Number）**： - 斐波那契数列定义为：`F(n) = F(n-1) + F(n-2)`，其中`F(0)=0`，`F(1)=1`。 - 斐波那契数在很多算法问题中都有应用，例如动态规划、递归等。 2. **卢卡斯数（Lucas Number）**： - 卢卡斯数列与斐波那契数列相似，但起始项不同：`L(0)=2`，`L(1)=1`。 - 卢卡斯数列同样可以用于解决许多数列相关的计算问题。 3. **卡特兰数（Catalan Number）**： - 定义为：`C(n) = (1/(n+1)) * (2n choose n) = (2n)! / [(n+1)!n!]`。 - 应用于组合数学中的多种场景，如括号序列的数量、二叉树的数量等。 4. **斯特林数第二类（Stirling Number of the Second Kind）**： - 用于计算将`n`个不同的元素分成`k`个非空集合的方法数。 - 计算公式复杂，通常通过递推的方式进行计算。 5. **贝尔数（Bell Number）**： - 表示将`n`个元素分成任意数量的不相交子集的方法数。 - 贝尔数可以通过斯特林数第二类进行计算。 6. **斯特林近似公式（Stirling's Approximation）**： - 用于近似计算阶乘`n!`的值，特别是在`n`较大的情况下。 - 公式为：`n! ≈ sqrt(2πn) * (n/e)^n`。 7. **倒数和近似公式（Sum of Reciprocal Approximation）**： - 计算`∑ 1/n`的近似值，其中`n`为正整数。 - 可以使用调和级数或自然对数来近似计算。 8. **杨表（Young Tableau）**： - 在组合数学中，杨表是一种特殊类型的矩阵。 - 通常用于表示对称群的表示理论。 9. **整数划分**： - 指将正整数`n`写成若干正整数之和的方法数。 - 整数划分问题可以通过动态规划的方法高效解决。 10. **错排公式**： - 错排问题是指将`n`个元素重新排列，使得没有元素出现在原来的位置上。 - 解决方法通常是通过递推公式或直接计算得出。 11. **三角形内切圆半径公式**： - 内切圆半径`r = Area/s`，其中`Area`是三角形的面积，`s`是半周长。 - 常用于几何学中的问题。 12. **三角形外接圆半径公式**： - 外接圆半径`R = abc/(4Area)`，其中`a,b,c`是三角形的三边长。 - 也常应用于几何问题中。 13. **圆内接四边形面积公式**： - 圆内接四边形的面积可以通过海伦公式结合特定条件来计算。 14. **基础数论公式**： - 包括各种数论中的基本定理和公式，如欧拉定理、费马小定理等。 #### 二、大数模板，字符读入 - 在处理非常大的数字时，通常需要自己实现大数的操作。 - 字符串读入通常用于快速读取大量数据，提高程序的运行效率。 #### 三、数论算法 1. **最大公约数（GCD）**： - 通过辗转相除法或更相减损法计算两个或多个整数的最大公约数。 - 应用于解决与质数、约数等相关的数学问题。 2. **素数判断**： - 使用试除法或米勒-拉宾素性测试等方法。 - 对于较大数的素性判断尤为重要。 3. **素数筛法**： - 如埃拉托斯特尼筛法，用于找出一定范围内的所有素数。 - 广泛应用于需要快速获取素数列表的场景。 4. **模逆元**： - 求解`a·b ≡ 1 (mod m)`中的`b`，其中`a`和`m`互质。 - 在模运算中非常重要。 5. **扩展欧几里德算法**： - 用于求解线性同余方程或计算最大公约数的同时求出贝祖系数。 - 对于解决模线性方程等问题十分有用。 6. **模线性方程（同余方程）**： - 形式为`ax ≡ b (mod m)`的方程。 - 可以通过扩展欧几里德算法等方法求解。 7. **中国剩余定理**： - 解决一组模同余方程的问题，即使模数不互质也可以求解。 - 在密码学、计算机科学等领域有广泛应用。 8. **欧拉函数**： - 计算小于等于`n`且与`n`互质的正整数的数目。 - 在数论和密码学中有重要作用。 9. **Farey序列**： - Farey序列是有序的分数序列，分子分母互质且分母不超过某个值。 - 通常用于近似分数或处理与分数有关的问题。 10. **Miller-Rabin素性测试**： - 是一种快速检测素性的概率算法。 - 在实际应用中非常高效，特别是在处理大数时。 11. **Pollard's Rho因式分解**： - 是一种基于随机化的因式分解算法。 - 特别适合于寻找较小的因子。 #### 四、图论算法 1. **最小生成树**： - Kruskal算法和Prim算法都是经典的最小生成树算法。 - 适用于解决网络设计、电力布线等问题。 2. **单源最短路径**： - Bellman-Ford算法适用于存在负权边的情况。 - Dijkstra算法则适用于非负权边的情况。 3. **全源最短路径**： - Floyd算法能够求解所有顶点间的最短路径。 - 在网络路由、地图导航等领域有广泛应用。 4. **拓扑排序**： - 用于有向无环图（DAG），表示任务之间的先后顺序。 - 在任务调度、依赖关系管理等方面很有用。 5. **最大流算法**： - 包括Ford-Fulkerson算法、Edmonds-Karp算法等。 - 主要应用于流量网络问题，如运输系统优化等。 6. **最大匹配**： - 如匈牙利算法、Hopcroft-Karp算法等。 - 用于解决二分图的最大匹配问题，广泛应用于配对问题。 7. **带权二分图最优匹配**： - KM算法解决了带权二分图的最优匹配问题。 - 在匹配问题中有着重要的作用。 8. **强连通分量**： - Kosaraju算法和Gabow算法等用于求解有向图中的强连通分量。 - 在分析复杂网络结构时非常有用。 9. **无向图的割边割点和双连通分量**： - 割边和割点是破坏图的连通性的关键元素。 - 双连通分量是无向图中去除割点后仍然保持连通的部分。 - 在网络设计、可靠性分析等方面有重要应用。 10. **最小树形图**： - 求解最小树形图问题通常有两种方法：`O(N^3)`和`O(VE)`。 - 该问题通常出现在通信网络的设计中，如建立最小成本的通信网络。 #### 五、几何算法 1. **几何模板**： - 提供了计算点、线、多边形等基本几何对象的函数。 - 在处理涉及平面几何的问题时非常有用。 2. **球面上两点最短距离**： - 可以通过计算两点的大圆弧长来确定。 - 通常用于地理信息系统等领域。 3. **三点求圆心坐标**： - 通过求解垂直平分线的交点来得到圆心。 - 在计算几何中有广泛应用。 4. **三角形几个重要的点**： - 如重心、垂心、内心和外心等。 - 这些点在几何问题中常常出现。 #### 六、专题讨论 1. **树状数组**： - 也称为二叉索引树，用于快速查询和更新操作。 - 在数据结构领域有重要应用。 2. **字典树**： - 一种高效的多叉树结构，用于存储和检索字符串。 - 广泛应用于文本搜索、词典等场景。 3. **后缀树**： - 用于高效地处理字符串的后缀。 - 在模式匹配、生物信息学等领域有广泛应用。 4. **线段树**： - 用于处理区间查询和更新操作。 - 在解决涉及区间操作的问题时非常有效。 5. **并查集**： - 用于处理动态集合的合并和查找操作。 - 在图论和网络流算法中经常使用。 6. **二叉堆**： - 是一种特殊的完全二叉树，用于维护元素的优先级。 - 堆排序、优先队列等都基于此原理。 7. **逆序数**： - 通过归并排序可以高效地计算。 - 在排序算法分析中有着重要作用。 8. **树状DP**： - 将动态规划应用于树结构中。 - 在解决与树结构相关的问题时非常有效。 9. **欧拉路**： - 求解一条经过每条边恰好一次的路径。 - 在图论中具有重要意义。 10. **八数码**： - 是一种典型的图搜索问题。 - 通常使用A*算法等来求解。 11. **高斯消元法**： - 用于求解线性方程组。 - 在数值计算和线性代数中非常重要。 12. **字符串匹配**： - KMP算法能够高效地在文本中查找模式串。 - 在文本处理和模式识别中有着广泛的应用。 13. **全排列和全组合**： - 通过递归或迭代的方法生成所有可能的排列或组合。 - 在组合数学中有着重要应用。 14. **二维线段树**： - 扩展了一维线段树的功能，用于处理二维空间中的区间查询。 - 在计算机图形学等领域有着广泛应用。 15. **稳定婚姻匹配**： - Gale-Shapley算法可以找到一个稳定的婚姻匹配。 - 在配对问题中有着重要应用。 16. **后缀数组**： - 用于高效地处理字符串的后缀。 - 在文本处理和模式匹配中非常重要。 17. **左偏树**： - 是一种自平衡二叉搜索树，用于高效地进行插入和删除操作。 - 在需要频繁修改数据结构的场景下非常有用。 18. **标准RMQ-ST**： - RMQ问题即Range Minimum Query，即查询区间最小值。 - 通过构建特殊的数据结构来高效解决。 19. **度限制最小生成树**： - 在满足度数限制的情况下，求解最小生成树。 - 在网络设计和优化问题中有着重要应用。 20. **最优比率生成树**： - 0/1分数规划的一种应用。 - 通常用于解决资源分配问题。 21. **最小花费置换**： - 求解最小代价的置换问题。 - 在运输问题和作业调度中有着重要应用。 22. **区间K大数**： - 查询区间内的第`k`大数。 - 通过构建合适的数据结构来解决。 23. **LCA（最近公共祖先）**： - 有两种经典算法：RMQ-ST和Tarjan算法。 - 在处理树结构的问题时非常重要。 24. **指数型母函数**： - 用于处理涉及组合数和多项式的复杂问题。 - 在组合数学中有着重要应用。 25. **AC自动机**： - 结合了字典树和KMP算法的优点。 - 在模式匹配问题中非常高效。 26. **FFT（快速傅里叶变换）**： - 用于快速计算多项式的乘法。 - 在信号处理和编码理论中有着广泛应用。 27. **二分图网络最大流最小割**： - 结合了最大流算法和最小割原理。 - 在网络流问题中有着重要应用。 28. **混合图欧拉回路**： - 处理包含有向边和无向边的混合图。 - 在图论和网络设计中有着重要应用。 29. **无源汇上下界网络流**： - 在某些特定条件下求解最大流问题。 - 在物流和资源分配问题中有着重要应用。 30. **二分图最小点权覆盖**： - 在二分图中寻找最小权重的顶点集，覆盖所有边。 - 在图论和优化问题中有着重要应用。 31. **带约束的轨道计数**： - 使用Burnside引理来处理带有特定约束的计数问题。 - 在计数组合问题中有着重要应用。 32. **三分法求函数波峰**： - 用于在连续函数上查找局部最大值。 - 在优化问题中有着重要应用。 33. **单词计数**： - 使用DFA自动机或Trie树等数据结构来高效计数。 - 在文本处理和自然语言处理中有着重要应用。 34. **字符串和数值hash**： - 通过散列函数将字符串或数值映射到较小的空间。 - 在数据结构和算法设计中有着重要应用。 35. **滚动队列**： - 实现了队列的高效循环操作。 - 在需要频繁插入和删除的场景下非常有用。 36. **最小点基，最小权点基**： - 在图论中用于寻找最小的顶点集。 - 在网络设计和优化问题中有着重要应用。 37. **LCSubsequence O(N^2/logN)**： - 求解最长公共子序列问题。 - 在字符串比较和生物信息学中有着重要应用。 38. **伸展树**： - 一种自平衡二叉搜索树，能够根据访问频率调整节点位置。 - 在需要频繁查找、插入和删除的场景下非常有用。 39. **Treap**： - 结合了二叉搜索树和堆的特点。 - 在数据结构设计中有着重要应用。 40. **0/1分数规划K约束**： - 在0/1分数规划的基础上添加额外的约束条件。 - 在资源分配和优化问题中有着重要应用。 41. **表达式求值**： - 通过解析和计算表达式树来求解。 - 在编译器设计和计算器程序中有着重要应用。 42. **乘除法博弈**： - Wythoff博弈是经典的博弈问题之一。 - 在游戏理论和策略分析中有着重要应用。 43. **状态压缩的积木型DP**： - 通过状态压缩技术减少动态规划的状态空间。 - 在需要节省内存或提高效率的场景下非常有用。 44. **解一般线性方程组**： - 通过消元法等方法求解。 - 在数值计算和线性代数中有着重要应用。 45. **块状链表**： - 将链表分割成多个块，每个块内部使用数组实现。 - 在需要频繁插入和删除的场景下非常有用。 46. **Factor Oracle**： - 用于字符串的周期性分析。 - 在文本处理和模式识别中有着重要应用。 以上内容总结了ACM算法模板集中的主要知识点，涵盖了算法设计与分析的多个方面，对于学习和竞赛准备都非常有价值。