浙大ACM算法库：几何、数论、数值计算与图论

"浙江大学ACM标程库是一个包含ACM竞赛常用算法的综合库，主要涉及几何、组合数学、数据结构、数论、数值计算以及图论等多个领域，旨在为参赛者提供解决问题的基础代码和理论知识。" 这篇文档详细介绍了浙江大学ACM团队的标准库，覆盖了ACM竞赛中常见的问题和算法。以下是各部分的关键知识点： 1. **几何**： - **几何公式**：包含了基础的几何计算公式。 - **多边形**：包括多边形的处理方法，如点在多边形内的判断。 - **凸包**：介绍了计算二维平面上点集的凸包算法。 - **网格**：讨论了在网格上的几何操作。 - **圆**：提供了圆形相关的算法，如点与圆的关系判断。 2. **组合数学**： - **组合公式**：涵盖了组合计数的基本公式。 - **生成gray码**：介绍了如何生成 Gray 码序列。 - **置换(Polya)**：涉及到排列和置换的计算方法。 - **字典序全排列**和**字典序组合**：提供了生成特定顺序排列和组合的方法。 3. **数据结构**： - **并查集**：用于处理不相交集合的合并与查询。 - **堆**：包括了最小堆和最大堆的实现。 - **线段树**：用于高效地处理区间查询和更新。 - **子段和**和**子阵和**：支持对数组或矩阵的连续子区间进行操作。 4. **数论**： - **阶乘最后非0位**：计算阶乘最后非零数字的位置。 - **模线性方程组**：解决同余线性方程组的问题。 - **素数**：素数检测和相关的数论操作。 - **欧拉函数**：计算欧拉函数的值，与同余运算和模反元素相关。 5. **数值计算**： - **定积分计算(Romberg)**：使用Romberg方法进行数值积分。 - **多项式求根(牛顿法)**：利用牛顿迭代法求解多项式的根。 - **周期性方程(追赶法)**：处理周期性方程的算法。 6. **图论**： - **最大团**：寻找图中的最大团问题。 - **连通性**：包括无向图和有向图的连通性判断和划分。 - **匹配**：二分图和一般图的最大匹配算法，如匈牙利算法。 - **网络流**：最大流、上下界最大流、最小费用最大流等问题的求解。 这些知识点都是ACM竞赛中经常遇到的，掌握它们对于提升算法能力、解决实际问题至关重要。这个库不仅包含了算法的实现，还可能包括了对算法原理的解释和实例，是学习和准备ACM竞赛的重要参考资料。