浙大ACM竞赛模板：算法与解题思路

"浙江大学ACM模板提供了丰富的算法代码和解题思路，主要涵盖了几何、组合、结构、数论、数值计算、图论等多个方面的内容，旨在帮助参赛者解决ACM（国际大学生程序设计竞赛）中的问题。 1. 几何： - 注意事项：这部分可能包含了解题时对几何问题的特殊考虑和注意事项。 - 几何公式：包括了基本的几何计算公式，如面积、周长等。 - 多边形：涉及多边形的基本操作，如计算面积、周长等。 - 多边形切割：介绍了如何对多边形进行分割或裁剪的算法。 - 浮点函数：可能包括了处理浮点数误差和精度问题的方法。 - 面积：提供计算各种几何形状面积的算法。 - 球面：关于球体的几何运算，例如球面距离等。 - 三角形：处理与三角形相关的计算，如海伦公式、余弦定理等。 - 三维几何：涵盖三维空间中的几何问题，如点、线、面的相互关系。 2. 组合： - 组合公式：给出组合数C(n, k)的计算方法。 - 排列组合生成：算法实现生成所有可能的排列和组合。 - gray码：提供了生成格雷码的算法。 - 置换：Polya计数理论在排列中的应用。 - 字典序全排列和组合：按字典序生成所有排列和组合。 3. 结构： - 并查集：数据结构用于处理集合合并和查询是否属于同一集合的问题。 - 堆：实现优先队列的堆数据结构，包括大顶堆和小顶堆。 - 线段树：用于区间查询和修改的数据结构。 - 子段和：快速计算一段连续序列之和的算法。 - 子阵和：处理矩阵子区域和的算法。 4. 数论： - 阶乘最后非0位：计算阶乘结果末尾非零数字的数量。 - 模线性方程组：解模线性方程组的方法，如扩展欧几里得算法。 - 素数：检测素数的算法，如埃拉托斯特尼筛法。 - 欧拉函数：计算欧拉函数φ(n)的值。 5. 数值计算： - 定积分计算(Romberg)：数值积分的一种方法，通过高斯型插值逼近。 - 多项式求根(牛顿法)：使用牛顿迭代法求解多项式方程的根。 - 周期性方程(追赶法)：寻找周期性方程的解。 6. 图论—NP搜索： - 最大团：求解图的最大独立集问题。 - 最大团(n<64)(faster)：对于节点数量小于64的情况，更快的最大团算法。 7. 图论—连通性： - 无向图关键点(dfs邻接阵)：确定无向图的关键节点，使用深度优先搜索。 - 无向图关键边(dfs邻接阵)：找到无向图的关键边，同样使用深度优先搜索。 - 无向图的块(bfs邻接阵)：利用广度优先搜索划分无向图的连通块。 - 无向图连通分支(dfs/bfs邻接阵)：找出无向图的所有连通分支。 - 有向图强连通分支(dfs/bfs邻接阵)：检测有向图的强连通分量。 - 有向图最小点基(邻接阵)：在有向图中找到最小点基。 8. 图论—匹配： - 二分图最大匹配：Kuhn-Munkres算法或匈牙利算法解决二分图的最大匹配问题。 - 一般图匹配：处理非二分图的匹配问题，采用不同的算法策略。 这个模板是浙江大学ACM竞赛团队的经验结晶，它不仅包含了基础算法，还有各种优化技巧和实践经验，对于提升算法能力、解决实际问题非常有帮助。"