“浙江大学ACM模板(经典代码).pdf”是一个包含浙江大学ICPCTeam(国际大学生程序设计竞赛团队)日常训练使用的代码库,由WishingBone在2002年创建,并由Riveria在2004年进行了最后一次更新。这个模板涵盖了多个计算机科学领域的算法和数据结构,包括几何、组合数学、数据结构、数论、数值计算、图论问题等。
1. 几何:
- 注意事项:这部分可能包含了解决几何问题时需要注意的关键点。
- 几何公式:介绍了用于几何计算的基本公式。
- 多边形:处理多边形的算法,如检测点在多边形内、外或边界上。
- 多边形切割:如何分割一个多边形成多个部分。
- 浮点函数:处理浮点数精度问题的函数。
- 面积:计算几何形状面积的方法。
- 球面:与球体相关的计算,如球面坐标转换。
- 三角形:三角形的性质和计算,如面积、周长、中点等。
- 三维几何:处理三维空间中的几何问题,如点、线、面的关系。
- 凸包:计算几何对象的凸包,例如快速计算点集的最小外接多边形。
- 网格:与网格相关的算法,可能涉及到像素操作或网格上的搜索。
- 圆:圆的属性和与圆相关的计算。
- 整数函数:处理整数操作的函数,可能包括整数除法、取模等。
2. 组合:
- 组合公式:提供组合计算的数学公式。
- 排列组合生成:生成所有可能的排列和组合。
- gray码:生成 Gray码,一种二进制码,相邻两个码字之间仅有一位不同。
- 置换(polya):实现置换操作,常用于组合优化问题。
- 字典序全排列和字典序组合:按字典序生成所有排列和组合。
3. 结构:
- 并查集:高效处理集合合并和查询的数据结构。
- 堆:实现优先队列功能,如最小堆和最大堆。
- 线段树:用于区间查询和修改的数据结构。
- 子段和:快速计算数组一段连续子区间的和。
- 子阵和:扩展到二维数组,处理矩阵的子区域求和。
4. 数论:
- 阶乘最后非0位:确定阶乘结果最后一位非零数字的位置。
- 模线性方程组:求解模意义下的线性方程组。
- 素数:检测素数的算法,如埃拉托斯特尼筛法。
- 欧拉函数:计算欧拉函数φ(n),表示小于等于n且与n互质的正整数个数。
5. 数值计算:
- 定积分计算(Romberg方法):数值积分的一种高效算法。
- 多项式求根(牛顿法):通过迭代逼近求解多项式方程的根。
- 周期性方程(追赶法):解决具有周期性的方程。
6. 图论 - NP搜索:
- 最大团:寻找图中最大的完全子图。
- 最大团(n<64)(faster):针对节点数较少的情况,提供了更快的解决方案。
7. 图论 - 连通性:
- 无向图关键点(dfs邻接阵):识别图中关键的连接点。
- 无向图关键边(dfs邻接阵):找出保持图连通性的关键边。
- 无向图的块(bfs邻接阵):检测图的连通分量。
- 无向图连通分支(dfs/bfs邻接阵):找出所有的连通分支。
- 有向图强连通分支(dfs/bfs邻接阵):查找有向图的强连通分量。
- 有向图最小点基(邻接阵):找到图中最小的点集,使得每条有向边指向该集合内的一个点。
8. 图论 - 匹配:
- 二分图最大匹配(hungary邻接表/邻接阵/正向表):应用Kuhn-Munkres算法求解二分图的最大匹配。
- 一般图匹配(邻接表/邻接阵/正向表):解决非二分图的匹配问题。
这个模板为参加ACM竞赛的学生提供了丰富的代码示例和算法实现,有助于他们在竞赛中快速解决问题。