清华大学ACM算法模板：几何、组合、结构与图论

"ACM模板-清华大学.pdf" 是一份由清华大学编写的 ACM（国际大学生程序设计竞赛）算法模板，包含了丰富的代码示例和易于理解的解释。这份模板涵盖了多个计算机科学竞赛中常见的算法和数据结构。 1. 几何： - 注意事项：在处理几何问题时需要特别注意精度问题和几何公式的正确使用。 - 几何公式：包含了一系列几何计算的基本公式，如面积、周长等。 - 多边形：涉及多边形的定义、性质和操作，如判断是否共线、是否交叉等。 - 多边形切割：讨论如何对多边形进行分割或合并。 - 浮点函数：处理浮点数时的运算和精度控制。 - 面积计算：包括平面图形和立体图形的面积计算方法。 - 球面：涉及球面上的坐标系统和计算。 - 三角形：三角形的各种性质，如勾股定理、余弦定理等。 - 三维几何：扩展到三维空间的几何问题，如体积、表面积的计算。 - 凸包：计算点集的凸包，常用于优化问题。 - 网格：处理二维或三维网格上的问题。 - 圆：圆形相关问题，如圆周率、圆心角等。 - 整数函数：在几何计算中，有时需要将浮点数转换为整数进行处理。 2. 组合： - 组合公式：提供了组合计数的数学公式，如组合C(n, k)。 - 排列组合生成：算法实现生成所有可能的排列和组合。 - Gray码：生成Gray码序列，一种二进制编码方式，相邻两个码字之间仅有一位不同。 - 置换(Polya)：排列的计数和生成。 - 字典序全排列：按照字典序生成所有排列。 - 字典序组合：类似地，按字典序生成所有组合。 3. 结构： - 并查集：快速查找和合并集合的高效数据结构。 - 堆：包括大顶堆和小顶堆，常用于优先队列和最大/最小元素的查找。 - 线段树：用于区间查询和修改的数据结构，可以快速处理子段和的问题。 - 子段和：在线段树的基础上处理区间加减等操作。 - 子阵和：扩展到二维矩阵的区间查询和修改。 4. 数论： - 阶乘最后非0位：计算阶乘末尾非零数字的数量。 - 模线性方程组：解模意义下的线性方程组，常用在数论和密码学问题中。 - 素数：素数检测算法，如埃拉托斯特尼筛法。 - 欧拉函数：计算小于等于给定数的正整数中与该数互质的数的数量。 5. 数值计算： - 定积分计算(Romberg)：数值积分的一种方法，通过逐步提高精度得到近似结果。 - 多项式求根(牛顿法)：用牛顿迭代法求解多项式方程的根。 - 周期性方程(追赶法)：解决周期性方程，如寻找周期函数的周期。 6. 图论—NP搜索： - 最大团：找到图中最大大小的完全子图。 7. 图论—连通性： - 无向图关键点：确定图的连通性，找出关键节点。 - 无向图关键边：确定哪些边是维持图连通性的关键。 - 无向图的块：划分图的连通分量。 - 无向图连通分支：列出所有的连通分支。 - 有向图强连通分支：在有向图中找寻强连通分量。 - 有向图最小点基：找出有向图的最小点集，使得任意两点间都有路径。 8. 图论—匹配： - 二分图最大匹配：匈牙利算法实现，找到二分图中最大的匹配数。 - 二分图最佳匹配：Kuhn-Munkres算法，用于找到二分图的最佳匹配。 - 一般图匹配：处理非二分图的匹配问题。 9. 图论—网络流： - 最大流：寻找网络中的最大流量，通常使用Ford-Fulkerson或Edmonds-Karp算法。 - 上下界最大流：处理有上下界限制的网络流问题。 - 上下界最小流：在保持流的上下界条件下，寻找最小费用的流。 - 最大流无流量：在网络流问题中，当没有增加流的空间时如何处理。 - 最小费用最大流：在满足最大流的同时，考虑边的费用，找到总费用最小的流。 这些内容为参加ACM竞赛或进行算法学习提供了丰富的参考资料，涵盖了许多基础和高级算法，有助于提升解决问题的能力。