浙江大学ACM竞赛模板库

"这是一份源自浙江大学ACM竞赛团队的经典算法模板库，包含了丰富的几何、组合、数据结构、数论、数值计算以及图论相关的算法和技巧，旨在为ACM/ICPC竞赛提供强有力的支持。" 1. **几何**： - 注意事项：在处理几何问题时，需要注意精度问题，通常采用浮点数运算，但需谨慎处理可能的浮点误差。 - 几何公式：涵盖各类几何计算公式，如距离、面积、体积等。 - 多边形：包括多边形的定义、性质和处理方法。 - 多边形切割：涉及如何将一个多边形分割成多个部分。 - 浮点函数：处理浮点数的运算，确保结果的准确性。 - 面积：计算各种形状的面积，如矩形、圆形、三角形等。 - 球面：处理与球面几何相关的问题。 - 三角形：三角形的性质和应用，如海伦公式。 - 三维几何：扩展到三维空间中的几何问题。 - 凸包：计算点集的凸包，例如Graham扫描法。 - 网格：处理基于网格的几何问题。 - 圆：圆的性质及与圆相关的算法。 2. **组合**： - 组合公式：包括组合计数的基本公式，如组合数C(n, k)。 - 排列组合生成：生成所有可能的排列或组合。 - Gray码：生成二进制Gray码序列。 - Polya计数：置换群的计数问题。 - 字典序全排列：按字典序生成所有可能的排列。 - 字典序组合：按字典序生成所有可能的组合。 3. **数据结构**： - 并查集：用于维护不相交集合的高效数据结构。 - 堆：优先队列的实现，包括大顶堆和小顶堆。 - 线段树：支持区间查询和修改的操作，如求区间和。 - 子段和：处理连续子数组的求和问题。 - 子阵和：二维数组的子矩阵和计算。 4. **数论**： - 阶乘最后非0位：找出n!的最后非0位数。 - 模线性方程组：解模线性方程组的方法，如扩展欧几里得算法。 - 素数：素数检测和生成。 - 欧拉函数：计算欧拉函数φ(n)，用于计算同余类的数量。 5. **数值计算**： - 定积分计算：Romberg积分法，用于数值积分。 - 多项式求根：使用牛顿法求解多项式的实根。 - 周期性方程：通过追赶法解决周期性方程。 6. **图论—NP搜索**： - 最大团：寻找图中最大完全子图，即最大团问题。 - 最大团(n<64)(faster)：对于规模较小的问题，有更快的算法。 7. **图论—连通性**： - 无向图关键点：利用DFS查找无向图的关键点，确保两点间的连通性。 - 无向图关键边：确定保持图连通性的关键边。 - 无向图的块：通过bfs找到图的连通块。 - 无向图连通分支：DFS/BFS方法获取所有连通分支。 - 有向图强连通分支：识别有向图中的强连通分量。 - 有向图最小点基：寻找图的最小点基，有助于简化问题。 8. **图论—匹配**： - 二分图最大匹配：匈牙利算法用于求解二分图的最大匹配问题，采用邻接表或邻接矩阵表示图。 这份模板库是ACM竞赛者的重要参考资料，它不仅包含基本算法，还提供了各种优化和问题解决策略，对于提升算法能力，解决复杂问题具有很高的实用价值。