ACM模板-浙大模板浙大模板

### ACM模板——浙大模板概览 本篇文档主要介绍了浙江大学计算机编程竞赛团队（ICPC）常用的一些算法和数据结构实现方法。这份资料由WishingBone于2002年12月创建，并由Riveri在2004年11月进行了更新。下面将根据文档的大纲对各个部分进行详细的知识点总结。 #### 1. 几何 - **1.1 注意** - 舍入方式：确保在进行浮点数运算时正确处理0.5的舍入方向。 - 不对称数据测试：对于几何题目来说，应该多测试一些不对称的数据来确保算法的鲁棒性。 - 整数几何边界：如果涉及到整数几何运算，则需要注意`xmult`和`dmult`是否会导致溢出。 - 浮点数精度：在处理浮点数时，需要合理设置`eps`值以避免精度问题。 - **1.2 几何公式** - 包括但不限于距离公式、角度公式等基本的几何计算方法。 - **1.3 多边形** - 主要介绍如何处理多边形的问题，包括多边形的表示、面积计算等。 - **1.4 多边形切割** - 如何将一个多边形切割成多个较小的多边形，这在地图分割等领域有广泛应用。 - **1.5 浮点函数** - 针对浮点数运算中可能出现的各种问题提供解决方案，如舍入误差、精度控制等。 - **1.6 面积** - 提供多种计算平面图形面积的方法。 - **1.7 球面** - 涉及球面上的几何问题，如计算球面距离等。 - **1.8 三角形** - 介绍与三角形相关的各种计算方法，例如三角形的面积、周长以及判断三角形类型等。 - **1.9 三维几何** - 对于三维空间中的几何问题提供解决方案，包括体积计算、三维空间中的距离计算等。 - **1.10 凸包** - 介绍凸包的定义及其计算方法，常用于图形学和计算机视觉领域。 - **1.11 网格** - 关于网格数据结构的应用和操作，如构建、查询等。 - **1.12 圆** - 圆的相关计算方法，包括圆的面积、周长计算以及与圆相关的几何问题。 - **1.13 整数函数** - 专门针对整数的运算提供算法，如整数除法的余数计算等。 #### 2. 组合 - **2.1 组合公式** - 包含了基本的组合数学公式，如组合数的计算公式等。 - **2.2 排列组合生成** - 如何生成所有可能的排列和组合。 - **2.3 生成gray码** - Gray码是一种特殊的二进制编码形式，相邻两个数字只有一位不同，这里介绍了生成Gray码的方法。 - **2.4 置换(polya)** - polya置换是组合数学中的一个重要概念，这里提供了相关算法。 - **2.5 字典序全排列** - 如何按字典序输出所有可能的全排列。 - **2.6 字典序组合** - 如何按字典序输出所有可能的组合。 #### 3. 结构 - **3.1 并查集** - 介绍并查集的基本原理和实现方法。 - **3.2 堆** - 堆数据结构的操作和应用。 - **3.3 线段树** - 线段树的构建和查询操作。 - **3.4 子段和** - 计算数组中特定子段的和。 - **3.5 子阵和** - 类似于子段和，但适用于多维数组。 #### 4. 数论 - **4.1 阶乘最后非0位** - 如何快速计算阶乘结果的末尾第一个非零数字。 - **4.2 模线性方程组** - 解决模线性方程组的方法。 - **4.3 素数** - 素数检测和生成方法。 - **4.4 欧拉函数** - 欧拉函数的计算方法。 #### 5. 数值计算 - **5.1 定积分计算(Romberg)** - 使用Romberg算法进行定积分计算。 - **5.2 多项式求根(牛顿法)** - 使用牛顿迭代法求多项式的根。 - **5.3 周期性方程(追赶法)** - 追赶法解决周期性方程问题。 #### 6. 图论—NP搜索 - **6.1 最大团** - 寻找图中最大的团（完全子图）。 - **6.2 最大团(n<64)(faster)** - 当节点数量小于64时的更快的最大团寻找方法。 #### 7. 图论—连通性 - **7.1 无向图关键点(dfs邻接阵)** - 使用深度优先搜索确定无向图的关键点。 - **7.2 无向图关键边(dfs邻接阵)** - 同样使用深度优先搜索确定无向图的关键边。 - **7.3 无向图的块(bfs邻接阵)** - 使用广度优先搜索确定无向图中的块。 - **7.4 无向图连通分支(dfs/bfs邻接阵)** - 确定无向图中的连通分支。 - **7.5 有向图强连通分支(dfs/bfs邻接阵)** - 确定有向图中的强连通分支。 - **7.6 有向图最小点基(邻接阵)** - 找出有向图中的最小点基。 #### 8. 图论—匹配 - **8.1 二分图最大匹配(hungary邻接表)** - 使用匈牙利算法求解二分图的最大匹配问题。 - **8.2 二分图最大匹配(hungary邻接阵)** - 使用匈牙利算法求解二分图的最大匹配问题，但采用邻接矩阵存储图。 - **8.3 二分图最大匹配(hungary正向表)** - 使用匈牙利算法求解二分图的最大匹配问题，采用正向表存储图。 - **8.4 二分图最佳匹配(kuhn_munkras邻接阵)** - 使用Kuhn-Munkras算法求解二分图的最佳匹配问题。 - **8.5 一般图匹配(邻接表)** - 求解一般图的匹配问题。 - **8.6 一般图匹配(邻接阵)** - 同上，但使用邻接矩阵存储图。 - **8.7 一般图匹配(正向表)** - 同上，但使用正向表存储图。 #### 9. 图论—网络流 - **9.1 最大流(邻接阵)** - 求解最大流问题。 - **9.2 上下界最大流(邻接阵)** - 在给定上下界的约束条件下求最大流。 - **9.3 上下界最小流(邻接阵)** - 在给定上下界的约束条件下求最小流。 - **9.4 最大流无流量(邻接阵)** - 在特殊情况下求解最大流问题。 - **9.5 最小费用最大流(邻接阵)** - 求解最小费用最大流问题。 #### 10. 图论—应用 - **10.1 欧拉回路(邻接阵)** - 查找是否存在欧拉回路。 - **10.2 树的前序表转化** - 将树的前序遍历结果转化为其他形式。 - **10.3 树的优化算法** - 对树的一些常见操作进行优化。 - **10.4 拓扑排序(邻接阵)** - 对有向无环图进行拓扑排序。 - **10.5 最佳边割集** - 找到最佳的边割集。 - **10.6 最佳点割集** - 找到最佳的点割集。 - **10.7 最小边割集** - 找到最小的边割集。 - **10.8 最小点割集** - 找到最小的点割集。 - **10.9 最小路径覆盖** - 对图进行最小路径覆盖。 #### 11. 图论—支撑树 - **11.1 最小生成树(kruskal邻接表)** - 使用Kruskal算法求解最小生成树问题。 - **11.2 最小生成树(kruskal正向表)** - 同上，但使用正向表存储图。 - **11.3 最小生成树(prim+binary_heap邻接表)** - 使用Prim算法结合二叉堆求解最小生成树问题。 - **11.4 最小生成树(prim+mapped_heap邻接表)** - 使用Prim算法结合映射堆求解最小生成树问题。 - **11.5 最小生成树(prim邻接阵)** - 使用Prim算法求解最小生成树问题，采用邻接矩阵存储图。 - **11.6 最小树形图(邻接阵)** - 求解最小树形图问题。 #### 12. 图论—最短路径 - **12.1 最短路径(单源bellman_ford邻接阵)** - 使用Bellman-Ford算法求解单源最短路径问题。 - **12.2 最短路径(单源dijkstra+bfs邻接表)** - 使用Dijkstra算法结合广度优先搜索求解单源最短路径问题。 - **12.3 最短路径(单源dijkstra+bfs正向表)** - 同上，但使用正向表存储图。 - **12.4 最短路径(单源dijkstra+binary_heap邻接表)** - 使用Dijkstra算法结合二叉堆求解单源最短路径问题。 - **12.5 最短路径(单源dijkstra+binary_heap正向表)** - 同上，但使用正向表存储图。 - **12.6 最短路径(单源dijkstra+mapped_heap邻接表)** - 使用Dijkstra算法结合映射堆求解单源最短路径问题。 - **12.7 最短路径(单源dijkstra+mapped_heap正向表)** - 同上，但使用正向表存储图。 - **12.8 最短路径(单源dijkstra邻接阵)** - 使用Dijkstra算法求解单源最短路径问题，采用邻接矩阵存储图。 - **12.9 最短路径(多源floyd_warshall邻接阵)** - 使用Floyd-Warshall算法求解多源最短路径问题。 #### 13. 应用 - **13.1 Joseph问题** - Joseph环问题的解决方案。 - **13.2 N皇后构造解** - 构造N皇后问题的一个解。 - **13.3 布尔母函数** - 布尔母函数的相关应用。 - **13.4 第k元素** - 找到数组中的第k个元素。 - **13.5 幻方构造** - 构造幻方。 - **13.6 模式匹配(kmp)** - KMP算法在模式匹配中的应用。 - **13.7 逆序对数** - 计算数组中逆序对的数量。 - **13.8 字符串最小表示** - 求解字符串的最小表示形式。 - **13.9 最长公共单调子序列** - 寻找两个序列中最长的公共单调子序列。 - **13.10 最长子序列** - 寻找序列中最长的子序列。 - **13.11 最大子串匹配** - 寻找字符串中最大的匹配子串。 - **13.12 最大子段和** - 寻找序列中最大子段的和。 - **13.13 最大子阵和** - 寻找二维数组中最大子阵的和。 #### 14. 其它 - **14.1 大数(只能处理正数)** - 提供处理大数的方法，但仅限于正数。 - **14.2 分数** - 分数的表示和运算方法。 - **14.3 矩阵** - 矩阵的表示和运算方法。 - **14.4 线性方程组** - 解决线性方程组的方法。 - **14.5 线性相关** - 线性相关的判断方法。 - **14.6 日期** - 日期相关的计算方法。 以上内容是对浙大ACM模板的一个概述，涵盖了从基础的几何计算到高级的图论问题，为参赛者提供了全面而实用的参考指南。