浙江大学ACM竞赛几何与组合数学算法库

"浙江大学ACM模板" 这是一个专门为参加ACM（国际大学生程序设计竞赛）而编写的模板库，由浙江大学ICPC团队开发维护。这个模板涵盖了众多算法和数据结构，旨在帮助参赛者快速解决各种竞赛中的问题。以下是模板库中包含的主要内容： 1. 几何： - 注意事项：讲解在处理几何问题时需要注意的关键点。 - 几何公式：提供常见的几何计算公式，如距离、角度等。 - 多边形：包括多边形的定义、性质和操作，如判断点是否在多边形内。 - 多边形切割：描述如何分割多边形。 - 浮点函数：处理浮点数的精度问题。 - 面积：计算不同几何形状的面积。 - 球面：处理与球面几何相关的问题。 - 三角形：涉及三角形的性质和计算，如重心、垂心等。 - 三维几何：扩展到三维空间的几何问题。 - 凸包：计算点集的凸包，用于优化问题。 - 网格：在网格结构上的操作。 - 圆：处理圆的性质和相关计算。 - 整数函数：与整数相关的操作，如整除、取模等。 2. 组合： - 组合公式：介绍组合计算的基本公式。 - 排列组合生成：生成所有可能的排列或组合。 - Gray码：生成Gray码序列，一种二进制码，相邻两个码字之间仅有一位不同。 - 置换（Polya）：进行置换操作，如循环置换、对称置换等。 - 字典序全排列：按字典序生成所有排列。 - 字典序组合：按字典序生成所有组合。 3. 结构： - 并查集：用于处理不相交集合的合并与查询。 - 堆：实现大顶堆和小顶堆，常用于优先队列。 - 线段树：支持区间查询和修改操作的数据结构。 - 子段和：快速计算区间和。 - 子阵和：二维数组的区间和计算。 4. 数论： - 阶乘最后非0位：确定阶乘结果最后的非零位数。 - 模线性方程组：解模线性方程组，常用于数论问题。 - 素数：素数检测和素数生成。 - 欧拉函数：计算一个数的欧拉函数值，与同余群有关。 5. 数值计算： - 定积分计算（Romberg法）：数值积分的方法。 - 多项式求根（牛顿法）：用牛顿迭代法求解多项式的实根。 - 周期性方程（追赶法）：处理周期性方程的求解。 6. 图论—NP搜索： - 最大团：寻找图中最大的完全子图。 7. 图论—连通性： - 无向图关键点：找到保持图连通性的关键节点。 - 无向图关键边：找出关键边，即移除后会导致图不连通的边。 - 无向图的块：划分图的连通部分。 - 无向图连通分支：列出图的所有连通分支。 - 有向图强连通分支：找到有向图中的强连通分量。 - 有向图最小点基：寻找最小点基，与图的拓扑排序相关。 8. 图论—匹配： - 二分图最大匹配：匈牙利算法实现，用于寻找最大匹配。 - 二分图最佳匹配：Kuhn-Munkres算法，求解最佳匹配。 9. 图论—网络流： - 最大流：寻找网络的最大流。 - 上下界最大流/最小流：处理带有上下界限制的网络流问题。 - 最大流无流量：在无流量情况下求最大流。 - 最小费用最大流：同时考虑流量和费用。 10. 图论—应用： - 欧拉回路：判断图是否存在欧拉回路，并生成。 - 树的前序表转化：将前序遍历的结果转化为二叉树。 - 树的优化算法：优化树结构的算法。 - 拓扑排序：对有向无环图进行排序。 - 最佳边割集：找到图的最佳边割。 - 最佳点割集：找出图的最佳点割。 这个模板库全面覆盖了ACM竞赛中可能遇到的多种算法和数据结构，对于参赛者来说是一份宝贵的参考资料。通过理解和掌握这些内容，可以提高解决问题的效率和精度。