浙江大学ACM模板(经典代码）.pdf

### 浙江大学ACM模板知识点详解 #### 一、概述 《浙江大学ACM模板（经典代码）》是一份由浙江大学ICPC团队整理的经典ACM编程资料，最初由Wishing Bone在2002年创建，并于2004年由Riveria进行了更新。这份文档系统地介绍了ACM编程中的各种常见问题及其解决方案，覆盖了多个领域，如几何、组合数学、数据结构、数值计算、图论等。以下是对文档中提及的主要知识点进行的详细介绍。 #### 二、几何 ##### 1.1 注意事项 - **浮点运算误差**：在处理几何问题时，由于计算机内部使用的是有限精度的浮点数表示实数，因此可能会引入误差。在比较两个浮点数是否相等时，应采用一个足够小的误差范围来判断。 - **坐标系选择**：根据问题的具体需求选择合适的坐标系（例如笛卡尔坐标系或极坐标系），以便更有效地解决问题。 ##### 1.2 几何公式 - **距离公式**：两点之间的距离可通过距离公式 \( d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} \) 计算。 - **角度计算**：通过向量内积可以计算两个向量之间的夹角。 ##### 1.3 多边形 - **多边形面积计算**：可以使用叉积的方法来计算不规则多边形的面积。 - **凸多边形的检测**：利用所有顶点构成的向量内积为正或负的特性，可以判断一个多边形是否为凸多边形。 ##### 1.4 多边形切割 - **多边形切割问题**：涉及到将一个或多个多边形分割成更小的部分，常见的应用场景包括地图分割、图形设计等。 ##### 1.5 浮点函数 - **浮点数运算**：针对浮点数的特殊处理方法，如四舍五入、取整等。 ##### 1.6 面积 - **不同形状的面积计算**：包括圆形、椭圆形、三角形等多种基本图形的面积计算方法。 ##### 1.7 球面 - **球面上的点**：如何在球面上定义和操作点。 - **球体体积和表面积计算**：球体的基本性质及其相关计算。 ##### 1.8 三角形 - **海伦公式**：用于计算任意三角形面积的一种方法。 - **余弦定律和正弦定律**：用于解决三角形问题的重要工具。 ##### 1.9 三维几何 - **三维空间中的点、线、面**：三维空间中点、线、面的关系及计算。 - **三维图形的表面积和体积计算**：如立方体、球体等的体积和表面积计算方法。 ##### 1.10 凸包 - **凸包算法**：用于找出一组点构成的最小凸多边形的算法，常见的有Graham扫描算法、Jarvis步进法等。 ##### 1.11 网格 - **网格划分**：将平面区域划分为规则或不规则的网格单元，用于模拟和分析。 ##### 1.12 圆 - **圆的方程**：标准方程和一般方程。 - **圆与直线的关系**：相交、相切、相离等判断条件。 ##### 1.13 整数函数 - **整数运算**：涉及到整数的加减乘除以及取模等基本运算。 #### 三、组合数学 ##### 2.1 组合公式 - **组合数计算**：如 \(C(n, k)\) 的计算方法。 - **排列组合的基本原理**：了解排列和组合的基本概念及计算方法。 ##### 2.2 排列组合生成 - **全排列生成**：给出一个集合的所有可能排列。 - **组合生成**：生成给定大小的子集。 ##### 2.3 生成 Gray 码 - **Gray 码定义**：一种相邻两个编码只有一位不同的编码方式。 - **递归生成方法**：通过递归的方式生成 Gray 码序列。 ##### 2.4 置换(Polya) - **Polya 定理**：用于解决具有对称性的计数问题，尤其是涉及颜色分配的问题。 ##### 2.5 字典序全排列 - **字典序排列**：按照字典顺序列出所有可能的排列。 ##### 2.6 字典序组合 - **字典序组合**：按照字典顺序列出所有可能的组合。 #### 四、数据结构 ##### 3.1 并查集 - **并查集的基本操作**：包括查找、合并等基本操作，常用于处理不相交集的问题。 - **优化技巧**：如路径压缩、按秩合并等技术。 ##### 3.2 堆 - **堆的定义**：完全二叉树的一种存储形式，分为大顶堆和小顶堆。 - **堆的应用**：如优先队列、堆排序等。 ##### 3.3 线段树 - **线段树的构建**：用于高效查询区间内的特定信息，如区间和、区间最大值等。 - **线段树的更新操作**：如何在线段树中插入或删除元素。 ##### 3.4 子段和 - **子段和问题**：如何快速计算数组中任意子段的和。 ##### 3.5 子阵和 - **子阵和问题**：与子段和类似，但考虑的是二维数组。 #### 五、数论 ##### 4.1 阶乘最后非0位 - **阶乘计算**：如何求解阶乘的最后一位非零数字。 ##### 4.2 模线性方程组 - **中国剩余定理**：解决模线性方程组的有效方法之一。 ##### 4.3 素数 - **素数判断**：常用的素数判断方法，如埃拉托斯特尼筛法。 - **素数相关性质**：如质因数分解、素数个数估计等。 ##### 4.4 欧拉函数 - **欧拉函数定义**：\( \phi(n) \) 表示小于等于 \( n \) 的正整数中与 \( n \) 互质的数的个数。 - **欧拉函数的性质**：如乘法性等。 #### 六、数值计算 ##### 5.1 定积分计算(Romberg) - **Romberg 积分**：一种高效的数值积分方法，基于复合梯形法则。 ##### 5.2 多项式求根(牛顿法) - **牛顿迭代法**：用于求解多项式的近似根。 ##### 5.3 周期性方程(追赶法) - **追赶法**：适用于求解周期性方程，特别适用于三对角矩阵的情况。 #### 七、图论 ##### 6.1 最大团 - **最大团问题**：找到图中最大的完全子图。 ##### 6.2 最大团(n<64)(faster) - **快速求解**：当图的规模较小时，可以使用更快的算法求解最大团问题。 ##### 7.1 无向图关键点(dfs邻接阵) - **关键点识别**：通过深度优先搜索来识别无向图中的关键点。 ##### 7.2 无向图关键边(dfs邻接阵) - **关键边识别**：识别无向图中的关键边。 ##### 7.3 无向图的块(bfs邻接阵) - **图的块**：识别无向图中的最大连通子图。 ##### 7.4 无向图连通分支(dfs/bfs邻接阵) - **连通分支识别**：识别无向图中的连通分支。 ##### 7.5 有向图强连通分支(dfs/bfs邻接阵) - **强连通分支**：识别有向图中的强连通分支。 ##### 7.6 有向图最小点基(邻接阵) - **最小点基**：识别有向图中的最小点集，该点集包含所有的强连通分支。 ##### 8.1 二分图最大匹配(Hungary邻接表) - **匈牙利算法**：用于求解二分图的最大匹配问题。 ##### 8.2 二分图最大匹配(Hungary邻接阵) - **邻接矩阵实现**：使用邻接矩阵实现匈牙利算法。 ##### 8.3 二分图最大匹配(Hungary正向表) - **正向表实现**：使用正向表实现匈牙利算法。 ##### 8.4 二分图最佳匹配(Kuhn_Munkras邻接阵) - **Kuhn-Munkras算法**：用于求解二分图的最佳匹配问题。 ##### 8.5 一般图匹配(邻接表) - **一般图匹配问题**：不限制图是否为二分图的一般匹配问题。 ##### 8.6 一般图匹配(邻接阵) - **邻接矩阵实现**：使用邻接矩阵实现一般图匹配问题。 ##### 8.7 一般图匹配(正向表) - **正向表实现**：使用正向表实现一般图匹配问题。 ##### 9.1 最大流(邻接阵) - **Ford-Fulkerson算法**：用于求解最大流问题的一种基本算法。 ##### 9.2 上下界最大流(邻接阵) - **上下界限制**：考虑流量限制下的最大流问题。 ##### 9.3 上下界最小流(邻接阵) - **最小流问题**：考虑流量限制下的最小流问题。 ##### 9.4 最大流无流量(邻接阵) - **无流量情况**：求解最大流时考虑初始状态没有流量的情况。 ##### 9.5 最小费用最大流(邻接阵) - **最小费用最大流**：同时考虑最大流和最小费用的最优解。 #### 八、图论应用 ##### 10.1 欧拉回路(邻接阵) - **欧拉回路**：寻找图中经过每条边恰好一次的回路。 ##### 10.2 树的前序表转化 - **树的遍历**：如何从前序遍历转换到其他类型的遍历。 ##### 10.3 树的优化算法 - **树的优化**：针对特定问题对树进行优化处理的方法。 ##### 10.4 拓扑排序(邻接阵) - **拓扑排序**：对于有向无环图，按照某种顺序输出所有顶点的过程。 ##### 10.5 最佳边割集 - **边割集**：寻找最小的边集合，移除这些边后图不再连通。 ##### 10.6 最佳点割集 - **点割集**：寻找最小的点集合，移除这些点后图不再连通。 ##### 10.7 最小边割集 - **最小边割集**：寻找使得图分裂所需的最少边数。 ##### 10.8 最小点割集 - **最小点割集**：寻找使得图分裂所需的最少点数。 ##### 10.9 最小路径覆盖 - **路径覆盖**：寻找覆盖图中所有顶点的最少路径数量。 ##### 11.1 最小生成树(Kruskal邻接表) - **Kruskal算法**：一种贪心算法，用于求解最小生成树问题。 ##### 11.2 最小生成树(Kruskal正向表) - **正向表实现**：使用正向表实现Kruskal算法。 ##### 11.3 最小生成树(Prim+binary_heap邻接表) - **Prim算法**：使用二叉堆优化的Prim算法。 ##### 11.4 最小生成树(Prim+binary_heap正向表) - **正向表实现**：使用正向表实现Prim算法。 ##### 11.5 最小生成树(Prim+mapped_heap邻接表) - **映射堆实现**：使用映射堆优化的Prim算法。 ##### 11.6 最小生成树(Prim+mapped_heap正向表) - **正向表实现**：使用正向表实现Prim算法。 ##### 11.7 最小生成树(Prim邻接阵) - **邻接矩阵实现**：使用邻接矩阵实现Prim算法。 ##### 11.8 最小树形图(邻接阵) - **最小树形图**：最小生成树的特殊情况，仅应用于树形图。 #### 九、最短路径 ##### 12.1 最短路径(单源Bellman_Ford邻接阵) - **Bellman-Ford算法**：适用于含有负权边的图。 ##### 12.2 最短路径(单源Dijkstra+bfs邻接表) - **Dijkstra算法**：适用于无负权边的图。 ##### 12.3 最短路径(单源Dijkstra+bfs正向表) - **正向表实现**：使用正向表实现Dijkstra算法。 ##### 12.4 最短路径(单源Dijkstra+binary_heap邻接表) - **二叉堆优化**：使用二叉堆优化的Dijkstra算法。 ##### 12.5 最短路径(单源Dijkstra+binary_heap正向表) - **正向表实现**：使用正向表实现Dijkstra算法。 ##### 12.6 最短路径(单源Dijkstra+mapped_heap邻接表) - **映射堆优化**：使用映射堆优化的Dijkstra算法。 ##### 12.7 最短路径(单源Dijkstra+mapped_heap正向表) - **正向表实现**：使用正向表实现Dijkstra算法。 ##### 12.8 最短路径(单源Dijkstra邻接阵) - **邻接矩阵实现**：使用邻接矩阵实现Dijkstra算法。 ##### 12.9 最短路径(多源Floyd_Warshall邻接阵) - **Floyd-Warshall算法**：适用于求解所有顶点之间的最短路径问题。 #### 十、应用案例 ##### 13.1 Joseph问题 - **约瑟夫环**：经典的循环问题，涉及循环队列的应用。 ##### 13.2 N皇后构造解 - **N皇后问题**：寻找放置N个皇后在N×N的棋盘上，使得任意两个皇后之间不能相互攻击的方案。 ##### 13.3 布尔母函数 - **母函数应用**：利用母函数解决组合数学问题。 ##### 13.4 第k元素 - **选择问题**：在数组中找到第k个最大的元素。 ##### 13.5 幻方构造 - **幻方**：每个行、列以及两条对角线上的数字之和相等的特殊矩阵。 ##### 13.6 模式匹配(KMP) - **KMP算法**：快速字符串匹配算法，避免重复比较。 #### 结语 《浙江大学ACM模板（经典代码）》涵盖了ACM竞赛中几乎所有重要的算法和技术，是学习和准备ACM竞赛不可或缺的宝贵资源。通过深入学习这些知识点，可以大大提高解决复杂问题的能力，对于参加ACM竞赛的学生来说非常有价值。