常见算法模板整理汇总

ACM模板整理 ACM 模板整理是指在 ACM 竞赛中常用的算法和数据结构的总结和整理，本文档对 ACM 模板进行了分类和整理，总共分为六个部分：数学问题、字符串处理、计算几何、数论、图论和排序/查找。 **数学问题** 数学问题是 ACM 竞赛中的基本问题，包括精度计算、任意进制转换、最大公约数、最小公倍数、组合序列、快速傅立叶变换（FFT）、Ronberg 算法计算积分、行列式计算、求排列组合数、求某一天星期几、卡特兰（Catalan）数列原理、杨辉三角、全排列、匈牙利算法----最大匹配问题、最佳匹配 KM 算法等。 1. 精度计算：大数阶乘、乘法（大数乘小数）、乘法（大数乘大数）、加法、减法等。 2. 任意进制转换：将十进制数转换为其他进制数。 3. 最大公约数和最小公倍数：计算两个数的最大公约数和最小公倍数。 4. 组合序列：计算组合数的公式和应用。 5. 快速傅立叶变换（FFT）：快速傅立叶变换的原理和应用。 6. Ronberg 算法计算积分：使用 Ronberg 算法计算定积分。 7. 行列式计算：计算行列式的值和应用。 8. 求排列组合数：计算排列组合数的公式和应用。 9. 求某一天星期几：计算某一天是星期几。 10. 卡特兰（Catalan）数列原理：卡特兰数列的定义和应用。 11. 杨辉三角：杨辉三角的定义和应用。 12. 全排列：计算全排列的公式和应用。 13. 匈牙利算法----最大匹配问题：使用匈牙利算法解决最大匹配问题。 14. 最佳匹配 KM 算法：使用 KM 算法解决最佳匹配问题。 **字符串处理** 字符串处理是 ACM 竞赛中的重要问题，包括字符串替换、字符串查找、字符串截取、LCS-最大公共子串长度、数字转换为字符等。 1. 字符串替换：将字符串中的某些字符替换为其他字符。 2. 字符串查找：在字符串中查找某些字符或子串。 3. 字符串截取：截取字符串中的某些字符或子串。 4. LCS-最大公共子串长度：计算两个字符串的最大公共子串长度。 5. 数字转换为字符：将数字转换为字符。 **计算几何** 计算几何是 ACM 竞赛中的重要问题，包括叉乘法求任意多边形面积、求三角形面积、两矢量间角度、两点距离（2D、3D）、射向法判断点是否在多边形内部、判断点是否在线段上、判断两线段是否相交、判断线段与直线是否相交、点到线段最短距离、求两直线的交点等。 1. 叉乘法求任意多边形面积：使用叉乘法计算任意多边形的面积。 2. 求三角形面积：计算三角形的面积。 3. 两矢量间角度：计算两矢量之间的角度。 4. 两点距离（2D、3D）：计算两点之间的距离。 5. 射向法判断点是否在多边形内部：使用射向法判断点是否在多边形内部。 6. 判断点是否在线段上：判断点是否在线段上。 7. 判断两线段是否相交：判断两线段是否相交。 8. 判断线段与直线是否相交：判断线段与直线是否相交。 9. 点到线段最短距离：计算点到线段的最短距离。 10. 求两直线的交点：计算两直线的交点。 **数论** 数论是 ACM 竞赛中的重要问题，包括 x 的二进制长度、返回 x 的二进制表示中从低到高的第 i 位、模取幂运算、求解模线性方程、筛法素数产生器、判断一个数是否素数、求距阵最大和、求一个数每一位相加之和、质因数分解、高斯消元法解线性方程组等。 1. x 的二进制长度：计算 x 的二进制长度。 2. 返回 x 的二进制表示中从低到高的第 i 位：返回 x 的二进制表示中从低到高的第 i 位。 3. 模取幂运算：计算模取幂运算的结果。 4. 求解模线性方程：求解模线性方程的解。 5. 筛法素数产生器：使用筛法产生素数。 6. 判断一个数是否素数：判断一个数是否素数。 7. 求距阵最大和：计算距阵的最大和。 8. 求一个数每一位相加之和：计算一个数每一位相加之和。 9. 质因数分解：将一个数分解为质因数。 10. 高斯消元法解线性方程组：使用高斯消元法解线性方程组。 **图论** 图论是 ACM 竞赛中的重要问题，包括 Prim 算法求最小生成树、Dijkstra 算法求单源最短路径、Bellman-ford 算法求单源最短路径、Floyd-Warshall 算法求每对节点间最短路径、解欧拉图等。 1. Prim 算法求最小生成树：使用 Prim 算法求最小生成树。 2. Dijkstra 算法求单源最短路径：使用 Dijkstra 算法求单源最短路径。 3. Bellman-ford 算法求单源最短路径：使用 Bellman-ford 算法求单源最短路径。 4. Floyd-Warshall 算法求每对节点间最短路径：使用 Floyd-Warshall 算法求每对节点间最短路径。 5. 解欧拉图：解欧拉图的定义和应用。 **排序/查找** 排序/查找是 ACM 竞赛中的重要问题，包括快速排序、归并排序、堆排序、插入排序、查找算法等。 本文档对 ACM 模板进行了分类和整理，对 ACM 竞赛中的常用算法和数据结构进行了总结和整理，为 ACM 竞赛的选手提供了一个系统的参考资料。