杭电ACM算法大全：数论、图论与几何模板

"杭电ACM算法模板是一个集合了多种常用算法和数学公式的编程模板库，由Huang Wei创建，旨在支持软件工程和程序设计竞赛。该模板库由杭州电子科技大学计算机与软件学院的ACM团队维护，适用于ACM（国际大学生程序设计竞赛）和其他算法竞赛。" 在ACM竞赛中，掌握高效的算法和数据结构是关键。这份模板涵盖了以下几个主要领域： 1. **常用函数与STL**：包括对标准模板库(STL)的熟练运用，如容器、迭代器、算法等，这些都是解决复杂问题的基础工具。 2. **重要公式与定理**： - **Fibonacci Number**：斐波那契数列及其在动态规划中的应用。 - **Lucas Number**：卢卡斯数列，与斐波那契数列有紧密联系，可用于解决特定类型的数学问题。 - **Catalan Number**：卡特兰数，常用于计数问题，如括号匹配、格子路径等。 - **Stirling Number (Second Kind)**：斯特林数第二类，用于描述集合的划分。 - **Bell Number**：贝尔数，表示集合的分割数目。 - **Stirling's Approximation**：斯特林近似公式，用于估算大数阶乘。 - **Sum of Reciprocal Approximation**：倒数和的近似，常见于积分的近似计算。 - **Young Tableau**：杨表，与排列组合和群论相关。 - **整数划分**：整数的不同加法组合，与组合数学紧密相关。 - **错排公式**：错排问题，计算一个排列中所有元素都不在原位的排列数量。 - **三角形内切圆半径公式** 和 **外接圆半径公式**：几何学中的重要计算。 - **圆內接四边形面积公式**：计算特定几何图形的面积。 - **基础数论公式**：如欧几里得算法、最大公约数、最小公倍数等。 3. **大数模板，字符读入**：处理大整数的操作，如大数乘法、除法，以及从输入流中读取整数的方法。 4. **数论算法**： - **Greatest Common Divisor (GCD)**：最大公约数的计算。 - **Prime素数判断**：快速判断一个数是否为素数。 - **Sieve Prime素数筛法**：如埃拉托斯特尼筛法，用于找出一定范围内的所有素数。 - **Module Inverse模逆元**：在模运算下求解一个数的逆元。 - **Extended Euclid扩展欧几里德算法**：求解两个整数的最大公约数及它们的贝祖等式解。 - **Modular Linear Equation模线性方程(同余方程)**：解决模线性方程组的问题。 - **Chinese Remainder Theorem中国余数定理**：解决多个同余方程组成的系统。 - **Euler Function欧拉函数**：欧拉 φ 函数，计算小于等于给定整数的正整数中与之互质的数量。 - **Farey总数** 和 **Farey序列构造**：费雷序列在数论和几何中有广泛应用。 - **Miller-Rabin素数测试** 和 **Pollard_rho因式分解**：用于素数检测和大整数因子分解。 5. **图论算法**： - **最小生成树(Kruscal算法和Prim算法)**：寻找加权无向图的最小生成树。 - **单源最短路径(Bellman-ford算法, Dijkstra算法)**：计算图中从单一节点到其他所有节点的最短路径。 - **全源最短路径(Floyd算法)**：计算图中任意两节点间的最短路径。 - **拓扑排序**：在有向无环图(DAG)中对节点进行排序。 - **网络预流和最大流**：在网络流问题中找到最大的流量。 - **网络最小费用最大流**：在考虑费用的情况下求解最大流。 - **网络最大流(高度标号预流推进)**：一种求解网络最大流的高效方法。 - **最大团**：在无向图中找寻最大的完全子图。 - **二分图最大匹配(匈牙利算法)**：在二分图中寻找最大匹配。 - **带权二分图最优匹配(KM算法)**：求解带权二分图的最大匹配问题。 - **强连通分量(Kosaraju算法和Gabow算法)**：识别有向图中的强连通分量。 6. **几何算法**： - **几何模板**：提供基础的几何操作。 - **球面上两点最短距离**：计算球面上两点之间的最短路径。 - **三点求圆心坐标**：根据三个点的坐标确定圆心。 这些模板提供了ACM竞赛中常见的问题解决方案，帮助参赛者快速解决复杂问题，提升编程效率。通过学习和掌握这些模板，程序员可以在算法竞赛中取得更好的成绩。