ACM竞赛算法模板集合

"这是一份来自Zhejiang University ACM竞赛团队的Routine Library，由WishingBone在2002年创建，并在2004年由Riveria更新。这份模板库包含了丰富的算法和数据结构，主要涵盖了几何、组合数学、结构、数论、数值计算以及图论等多个领域，对于ACM竞赛或者算法学习极具参考价值。" 详细说明: 1. 几何部分（1.1-1.13）: - 注意事项：提供了在处理几何问题时需要注意的细节。 - 几何公式：总结了基础的几何计算公式。 - 多边形：包括多边形的基本操作和性质。 - 多边形切割：讨论如何分割多边形。 - 浮点函数：涉及浮点数的运算和处理。 - 面积计算：提供了计算不同形状面积的方法。 - 球面：介绍了与球面相关的几何概念。 - 三角形：讨论三角形的性质和计算。 - 三维几何：处理三维空间中的几何问题。 - 凸包：介绍如何快速找到点集的凸包。 - 网格：涉及网格结构及其应用。 - 圆：处理圆形和圆周上的问题。 - 整数函数：针对整数操作的函数。 2. 组合数学部分（2.1-2.6）: - 组合公式：包括组合计数的基本公式。 - 排列组合生成：如何生成排列和组合序列。 - Gray码：介绍如何生成Gray码序列。 - Polya计数：处理置换问题的Polya理论。 - 字典序全排列：生成全排列的字典序序列。 - 字典序组合：生成组合的字典序序列。 3. 结构部分（3.1-3.5）: - 并查集：快速处理集合合并与查询的数据结构。 - 堆：包括优先队列和堆排序等。 - 线段树：用于区间查询和更新的高效数据结构。 - 子段和：处理数组子区间的和。 - 子阵和：扩展到二维矩阵的子区域和问题。 4. 数论部分（4.1-4.4）: - 阶乘最后非0位：计算阶乘末尾零的数量。 - 模线性方程组：解决同余方程组的问题。 - 素数：素数检测和相关的数论函数。 - 欧拉函数：计算小于等于指定数的正整数中与该数互质的数的数量。 5. 数值计算部分（5.1-5.3）: - 定积分计算（Romberg方法）：数值积分的高效算法。 - 多项式求根（牛顿法）：用牛顿迭代法求解多项式的根。 - 周期性方程（追赶法）：处理周期性方程的数值解。 6. 图论—NP搜索（6.1-6.2）: - 最大团：寻找图中最大的完全子图。 - n<64的最大团（更快）：优化算法以快速解决小规模问题。 7. 图论—连通性（7.1-7.6）: - 无向图关键点：确定图的连通性的关键节点。 - 无向图关键边：找出维持连通性的关键边。 - 无向图的块：分析图的连通分量。 - 无向图连通分支：使用DFS或BFS找到所有连通分支。 - 有向图强连通分支：确定有向图中的强连通分量。 - 有向图最小点基：找到图的最小点基，即最小的点集使得所有边被覆盖。 8. 图论—匹配（8.1-8.2）: - 二分图最大匹配（匈牙利算法，邻接表）：通过Kuhn-Munkres算法找到最大匹配。 - 二分图最大匹配（匈牙利算法，邻接阵）：相同目标，但使用邻接矩阵实现。 这份资源是ACM竞赛准备者的宝贵工具，包含了大量的经典算法和实用技巧，适合进行算法训练和竞赛准备。