ACM算法模板：数学、字符串、计算几何与数论概览

"这份文档是关于ACM竞赛中常用的算法和函数整理的模板，涵盖了数学问题、字符串处理、计算几何、数论以及图论等多个领域，旨在帮助参赛者快速理解和应用这些基础知识。" 1. 数学问题: - **精度计算**：包括大数阶乘、大数乘法（大数乘小数、大数乘大数）、大数加法、大数减法，这些都是在处理高精度计算时必要的。 - **进制转换**：将任意进制的数转换为其他进制，这是基础算法中的重要部分。 - **最大公约数/最小公倍数**：用于处理整数之间的关系，常见于数论问题。 - **组合序列**：如排列、组合计算，对于解决组合优化问题至关重要。 - **快速傅立叶变换（FFT）**：高效计算复数序列的离散傅立叶变换，常用于信号处理和图像分析等领域。 - **Ronberg算法**：用于数值积分的计算，简化了复杂的积分问题。 - **行列式计算**：在矩阵理论中，行列式可以帮助判断矩阵是否可逆。 - **排列组合数**：计算特定条件下的排列或组合数量，常见于概率论和统计学。 - **求星期几**：根据日期计算星期，涉及日期处理。 - **卡特兰数列**：在计数问题中出现，如括号匹配问题。 - **杨辉三角**：提供了组合数的二维结构，有助于求解组合问题。 - **全排列**：计算所有可能的排列组合。 - **匈牙利算法**：解决最大匹配问题，常用于网络流问题。 2. 字符串处理: - **字符串替换**：在文本中替换特定字符或子串。 - **字符串查找**：查找字符串中是否存在特定子串。 - **字符串截取**：从字符串中提取一部分。 - **LCS（最长公共子序列）**：寻找两个序列中最长的相同子序列。 - **数字转换为字符**：将数字转换为其对应的字符形式。 3. 计算几何: - **叉乘法求面积**：利用向量叉乘计算多边形面积。 - **三角形面积**：通过边长计算三角形面积。 - **两矢量间角度**：计算两个向量之间的夹角。 - **两点距离**：计算2D或3D空间中两点间的距离。 - **点与多边形的关系**：判断点是否在多边形内。 - **线段相关**：判断线段是否相交、点是否在线段上等。 - **直线交点**：求两条直线的交点。 4. 数论: - **二进制操作**：获取数字的二进制长度，以及获取二进制位。 - **模幂运算**：高效地进行模幂计算，如幂取模。 - **模线性方程/方程组**：求解同余方程，涉及中国剩余定理。 - **素数检测**：判断一个数是否为素数，常用在加密算法中。 - **矩阵最大和**：找到矩阵中最大的和。 - **数的位数之和**：计算一个数的所有位数之和。 - **质因数分解**：将一个数分解成质因数的乘积。 - **高斯消元法**：求解线性方程组的基础方法。 5. 图论: - **Prim算法**：用于构建最小生成树，减少图中边的权重总和。 - **Dijkstra算法**：求单源最短路径，适用于带权无环图。 - **Bellman-Ford算法**：可处理负权边的单源最短路径问题。 - **Floyd-Warshall算法**：计算图中所有顶点对之间的最短路径。 - **解欧拉图**：处理具有欧拉路径或欧拉回路的图。 6. 排序/查找： - 此部分未提供具体内容，但通常包括各种排序算法（如快速排序、归并排序、堆排序等）和查找算法（如二分查找、哈希查找等）。 这份文档是ACM竞赛准备者的宝贵参考资料，涵盖了编程竞赛中可能遇到的各种算法和数据结构，对于提升算法能力和解决实际问题具有重要意义。