浙江大学ACM竞赛模板库

"ACM模板（浙大）是浙江大学ICPC团队使用的竞赛模板库，由WishingBone于2002年创建，并在2004年由Riveria更新。这个模板库包含了丰富的算法和数据结构，涵盖了从几何、组合数学、结构、数论到数值计算、图论等多个领域，旨在帮助参赛者快速解决各类问题。" 1. 几何： - 注意事项：处理几何问题时需要考虑精度问题和特殊情况。 - 几何公式：包括点、线、面之间的关系，以及距离、角度等计算。 - 多边形：涉及多边形的定义、性质和操作，如判断点在多边形内/外，多边形的面积等。 - 多边形切割：用于处理多边形分割成多个部分的问题。 - 浮点函数：处理浮点数运算时的误差控制。 - 面积：计算平面图形和立体的面积、体积。 - 球面：处理球面上的计算，如球面坐标与直角坐标的转换。 - 三角形：涉及三角形的性质，如边长、角度、周长、面积的计算。 - 三维几何：处理三维空间中的几何问题，如点、线、面的关系。 - 凸包：找到一组点的最小凸多边形包围。 2. 组合： - 组合公式：提供组合计数的基本公式和计算方法。 - 排列组合生成：生成所有可能的排列或组合序列。 - Gray码：生成具有相邻位差异仅为一位的二进制码。 - Polya计数：用于计算有限群作用下的对象数量。 - 字典序全排列和组合：按照字典序生成所有排列和组合。 3. 结构： - 并查集：用于处理不相交集合的合并与查询。 - 堆：包括最大堆和最小堆，常用于优先队列和排序。 - 线段树：支持区间查询和修改操作，如求区间和、查找最值等。 - 子段和与子阵和：处理数组或矩阵的连续子序列和。 4. 数论： - 阶乘最后非0位：计算阶乘结果末尾的非零数字个数。 - 模线性方程组：解同余方程组，应用于数论问题。 - 素数：检测和生成素数，如Sieve of Eratosthenes算法。 - 欧拉函数：计算小于等于给定数的正整数中与该数互质的数的数量。 5. 数值计算： - 定积分计算（Romberg方法）：数值积分的一种高效方法。 - 多项式求根（牛顿法）：迭代求解多项式的根。 - 周期性方程（追赶法）：寻找周期函数的解。 6. 图论—NP搜索： - 最大团：寻找图中最大完全子图。 - 最大团(n<64)(faster)：对于小规模问题的优化算法。 7. 图论—连通性： - 无向图关键点：确定图的连通性，使用DFS遍历邻接矩阵。 - 无向图关键边：找出影响图连通性的边。 - 无向图的块：通过BFS或DFS划分图的连通分量。 - 无向图连通分支：找到所有的连通分支。 - 有向图强连通分支：确定有向图中强连通分量。 - 有向图最小点基（邻接阵）：用于有向图的最小生成树。 8. 图论—匹配： - 二分图最大匹配（匈牙利算法，邻接表/邻接阵）：寻找二分图中最大匹配。 这个模板库是ACM竞赛准备的重要资源，它提供了各种常见问题的标准解决方案，有助于参赛者快速理解和实现算法，提高解题效率。