浙江大学ACM比赛常用代码模板集合

"ACM模板（浙江大学）" 这个资源是浙江大学ACM竞赛团队的常用模板库，包含了各种算法和数据结构的实现，适用于解决算法竞赛中的常见问题。模板库由WishingBone于2002年创建，并在2004年由Riveria进行了更新。 1. 几何部分： - 注意事项：这部分可能涵盖了解决几何问题时的一些基本策略和注意事项。 - 几何公式：提供了常用的几何计算公式，如距离、角度、面积等。 - 多边形：包括多边形的定义、性质和处理方法。 - 多边形切割：涉及如何将多边形分割成更小的部分。 - 浮点函数：处理浮点数的运算，可能包括精度控制和误差分析。 - 面积计算：对不同形状的面积进行精确计算。 - 球面几何：处理球面上的问题，如大圆路径等。 - 三角形：涉及到三角形的各种性质和计算。 - 三维几何：处理三维空间中的几何问题。 - 凸包：快速找到一组点的凸包，通常使用Graham扫描或Jarvis步进法。 - 网格：与格点相关的算法，如格点覆盖、格点路径等。 - 圆：圆的相关计算，如点与圆的关系、圆与圆的交点等。 - 整数函数：处理整数特性的函数，可能包括整数除法和取模。 2. 组合数学： - 组合公式：包括组合、排列的基本计算公式。 - 排列组合生成：提供生成所有可能排列或组合的算法。 - Gray码生成：生成二进制Gray码的算法。 - Polya计数（置换）：处理排列的计数问题。 - 字典序全排列：按字典序生成所有排列。 - 字典序组合：按字典序生成所有组合。 3. 数据结构： - 并查集：用于处理不相交集合的操作，如合并和查询。 - 堆：实现优先队列，支持插入、删除最大/最小元素。 - 线段树：处理区间查询和更新的问题。 - 子段和：快速计算数组子区间的和。 - 子阵和：处理矩阵子区域的和。 4. 数论： - 阶乘最后非0位：找出阶乘最后的非零数字的位置。 - 模线性方程组：解模线性方程组的算法，如扩展欧几里得算法。 - 素数：检测素数的算法，如埃拉托斯特尼筛法。 - 欧拉函数：计算欧拉函数φ(n)，表示小于n且与n互质的正整数的数量。 5. 数值计算： - 定积分计算：使用Romberg方法计算函数的定积分。 - 多项式求根：利用牛顿法求解多项式的实根。 - 周期性方程：通过追赶法解决周期性方程。 6. 图论 - NP搜索： - 最大团：寻找图中最大的完全子图。 - n<64的最大团：对于规模较小的图，有更快的求解方法。 7. 图论 - 连通性： - 无向图关键点和关键边：确定图的强连通组件。 - 无向图的块：通过bfs或dfs找到图的连通分量。 - 有向图强连通分支：找出图的所有强连通分量。 - 有向图最小点基：寻找图的最小点基，用于优化某些问题。 8. 图论 - 匹配： - 二分图最大匹配：使用匈牙利算法求解二分图的最大匹配。 - Kuhn-Munkres算法：求解二分图的最佳匹配。 这些模板旨在提高ACM竞赛中解决问题的效率，涵盖了广泛的算法和数据结构，为参赛者提供了强大的工具箱。