浙江大学ACM模板

### 浙江大学ACM模板知识点详解 #### 一、几何 ##### 1.1 注意事项 - **舍入方式**：在处理浮点运算时，需特别注意0.5的舍入方向，以避免误差累积。 - **数据测试**：几何题目中，建议多测试不对称的数据来确保算法的鲁棒性和准确性。 - **整数几何**：对于整数类型的几何计算，需关注`xmult`（坐标放大倍数）和`dmult`（距离放大倍数）是否会导致溢出。 - **浮点数精度**：在处理浮点数时，需合理设置`eps`值，以确保比较操作的准确性和稳定性。 - **斜率使用**：尽量避免使用斜率进行计算，以防除数为零的情况发生。 - **公式简化**：在应用公式之前，应先对其进行适当简化，以减少计算复杂度并提高计算效率。 ##### 1.2 几何公式 - **基本公式**：包括点到直线的距离公式、两点间距离公式等。 - **高级公式**：涉及复杂的几何结构，如圆与直线的关系、多边形的面积计算等。 ##### 1.3 多边形 - **多边形定义**：由若干条不交叉的线段首尾相连形成的闭合图形。 - **多边形特性**：多边形的顶点数量、边的数量及其之间的关系等。 - **多边形操作**：如多边形的旋转、缩放等变换操作。 ##### 1.4 多边形切割 - **切割方法**：通过直线或平面将多边形分割成多个部分的技术。 - **应用场景**：在图形学、计算机辅助设计等领域中有广泛的应用。 ##### 1.5 浮点函数 - **精度控制**：如何在处理浮点数运算时保持足够的精度。 - **特殊值处理**：如何处理无穷大、无穷小以及NaN等特殊值。 - **误差分析**：分析算法中的误差来源及控制策略。 ##### 1.6 面积 - **基本形状**：计算常见几何形状（如圆形、矩形、三角形等）的面积。 - **复杂形状**：针对多边形、不规则形状等复杂情况下的面积计算。 ##### 1.7 球面 - **球面属性**：如球面的半径、直径等基本参数。 - **球面计算**：计算球面上的点与点之间的距离、球面的面积等。 ##### 1.8 三角形 - **性质**：三角形的内角和等于180度、勾股定理等基本性质。 - **类型**：锐角三角形、钝角三角形、直角三角形等不同类型的三角形。 - **计算**：涉及三角形面积、周长等计算方法。 ##### 1.9 三维几何 - **三维空间**：三维空间中的点、线、面等基本元素。 - **三维对象**：立方体、球体等典型三维对象的定义和性质。 - **操作**：三维对象的平移、旋转、缩放等操作。 ##### 1.10 凸包 - **概念**：凸包是指一组点所构成的最小凸多边形。 - **构建方法**：Graham扫描算法、Jarvis步进算法等常见构建凸包的方法。 - **应用领域**：计算机图形学、模式识别等领域。 ##### 1.11 网格 - **网格定义**：用于描述二维或三维空间中离散化的网格结构。 - **网格生成**：基于不同的需求生成特定类型的网格。 - **网格操作**：如网格的变形、细分等操作。 ##### 1.12 圆 - **圆的基本属性**：半径、直径等。 - **圆的方程**：标准方程、参数方程等形式。 - **圆的相关计算**：涉及圆的切线、圆与直线的关系等。 ##### 1.13 整数函数 - **定义**：在整数域上的函数。 - **应用**：如质数检测、阶乘等常用整数函数的应用场景。 #### 二、组合 - **组合公式**：排列组合的基本公式及其推导过程。 - **排列组合生成**：如何生成所有可能的排列或组合。 - **生成Gray码**：一种特殊的编码方式，相邻两个代码之间仅有一位不同。 - **置换(Polya)**：一种计数组合方法，用于解决计数问题。 - **字典序全排列**：按照字典序排列所有可能的全排列结果。 - **字典序组合**：同样按照字典序排列所有可能的组合结果。 #### 三、数据结构 - **并查集**：一种高效的数据结构，用于管理一组元素的集合，支持合并操作和查询元素所在集合的操作。 - **堆**：一种特殊的完全二叉树结构，常用于实现优先队列。 - **线段树**：一种可以快速查询区间信息的数据结构，如区间求和、区间最小/大值等。 - **子段和**：计算数组中某一段连续子数组的和。 - **子阵和**：计算二维数组中某个矩形区域内的元素之和。 #### 四、数论 - **阶乘最后非0位**：求一个数的阶乘结果中最后一个非0数字。 - **模线性方程组**：求解形如\(ax \equiv b\ (mod\ m)\)的方程组。 - **素数**：素数的定义、检测方法及其相关性质。 - **欧拉函数**：欧拉函数的定义、计算方法及其应用。 #### 五、数值计算 - **定积分计算(Romberg)**：Romberg方法是一种高效的数值积分方法，用于近似计算定积分。 - **多项式求根(牛顿法)**：利用牛顿迭代法求解多项式的根。 - **周期性方程(追赶法)**：适用于求解具有周期性的方程。 #### 六、图论—NP搜索 - **最大团**：在图中寻找最大的完全子图，即团。 - **最大团(n<64)(faster)**：针对规模较小的情况，提供更高效的求解方法。 #### 七、图论—连通性 - **无向图关键点(dfs邻接阵)**：利用深度优先搜索算法查找无向图中的关键点。 - **无向图关键边(dfs邻接阵)**：查找无向图中的关键边。 - **无向图的块(bfs邻接阵)**：使用广度优先搜索算法找出无向图中的块。 - **无向图连通分支(dfs/bfs邻接阵)**：查找无向图的所有连通分支。 - **有向图强连通分支(dfs/bfs邻接阵)**：查找有向图的强连通分支。 - **有向图最小点基(邻接阵)**：找出有向图中的最小点基数。 #### 八、图论—匹配 - **二分图最大匹配(hungary邻接表)**：匈牙利算法是求解二分图最大匹配的经典算法之一。 - **二分图最佳匹配(kuhn_munkras邻接阵)**：Kuhn-Munkras算法用于求解二分图的最佳匹配问题。 #### 九、图论—网络流 - **最大流(邻接阵)**：基于Ford-Fulkerson算法计算最大流。 - **上下界最大流(邻接阵)**：考虑边的容量上下界限制下的最大流问题。 - **最小费用最大流(邻接阵)**：在网络流中同时考虑流的最大值和最小成本。 #### 十、图论—应用 - **欧拉回路(邻接阵)**：在图中寻找一条经过每条边恰好一次的回路。 - **树的优化算法**：针对树形结构的优化算法，如动态规划等。 - **拓扑排序(邻接阵)**：对有向无环图进行拓扑排序。 - **最佳边割集**：在图中找到一个割集，使得割集的权值之和最小。 - **最佳点割集**：同样求最小割集，但关注的是顶点而非边。 - **最小路径覆盖**：在有向图中找到一个路径集合，使得每个顶点至少被一个路径覆盖。 #### 十一、图论—支撑树 - **最小生成树(kruskal邻接表)**：Kruskal算法用于求解加权无向图的最小生成树。 - **最小生成树(prim+mapped_heap邻接表)**：Prim算法结合映射堆用于求解最小生成树问题。 - **最小生成树(prim邻接阵)**：另一种实现Prim算法的方式。 #### 十二、图论—最短路径 - **最短路径(单源dijkstra+binary_heap邻接表)**：Dijkstra算法结合二叉堆用于求解单源最短路径问题。 - **最短路径(多源floyd_warshall邻接阵)**：Floyd-Warshall算法用于求解所有顶点间的最短路径问题。 #### 十三、应用 - **Joseph问题**：经典的约瑟夫环问题。 - **N皇后构造解**：在棋盘上放置N个皇后，使得任意两个皇后不会互相攻击。 - **模式匹配(kmp)**：KMP算法用于字符串匹配。 - **最长公共单调子序列**：寻找两个序列中最长的单调递增或递减的公共子序列。 #### 十四、其它 - **大数(只能处理正数)**：用于处理超出普通整数范围的大数运算。 - **分数**：分数类的设计及其运算。 - **矩阵**：矩阵的定义、基本运算等。 - **线性方程组**：求解线性方程组的各种方法。 - **线性相关**：向量组线性相关的定义及其判定方法。 - **日期**：日期相关算法，如计算两个日期之间的天数差等。 以上是对浙江大学ACM模板中的知识点进行了详细的总结和解释，这些内容覆盖了算法竞赛中的许多核心概念和技术，对于提高算法理解和编程能力非常有帮助。