"这是一份来自天津大学的ACM学习笔记,包含了丰富的算法和数据结构模板,主要使用C++编程语言,并辅以少量Java代码。笔记涵盖了图论、计算几何、数学、数据结构等多个核心领域,是学习和准备ACM竞赛的宝贵资料。"
在图论部分,笔记详细介绍了各种概念和算法,如割点和割边的定义,Kruskal算法用于构建最小生成树,以及树的分治策略。同时,还讲解了第K短路的计算、一般图的匹配问题,如 Dinic 最大流算法、Sap 最大流算法和EK最大流算法。此外,还包括混合图的欧拉回路、最大权闭合图、最大密度子图、最小边割集、二分图最小权覆盖集、最优比例生成树、最小限度生成树、次小生成树、生成树计数、图的十字匹配、树中删除最少边形成n连通集、最短路及其次短路的计算,以及树的最小点覆盖等问题。
计算几何领域,笔记涵盖了基础公式和常用计算几何库的使用,例如处理三角形的各种操作,如计算面积和找到最大面积的三角形。还有凸包的构造,包括两凸包的最短距离、凸包的直径、最大内切圆、三维凸包、半平面交、平面最远点对、网格问题、圆的运算、两圆交的面积、最小圆覆盖、单位圆覆盖最多点、最小球覆盖、圆和多边形的交、直线的反射、扇形的重心、矩形交面积、点在三角形内部的数量、Pick公式求面积、共线最多的点的个数、线段围成的区域储水量、最多正方形个数的计算、最多确定互不平行直线的方法、三角形全等的判断、多边形核的求解以及点的旋转等。
数学部分涉及多种理论和算法,如定理与定义、公式与序列、排列与组合的计算,线性筛法用于高效地找到素数,定积分的计算,凸函数的极值问题,表达式求值,多项式乘法使用傅里叶变换,多项式求根采用牛顿迭代法,模线性方程组的解决,计算特定数字在数列中出现的次数,Rabin-Miller伪素数测试,快速幂取模,Lucas-组合数取模,快速组合数取模,菲波拉契数列的模运算,整数的质因数分解,递归求等比数列之和,置换群的最小交换代价,最优子区间,高精度计算,第K个与m互质的数,行列式的计算,排列P(n, m)的最后非零位,法雷级数,取石子游戏的策略,Nim游戏的必胜方法数,以及数列的最优划分问题。
这份笔记详尽地梳理了ACM竞赛中常见的算法和问题,对于提升算法思维和编程能力有着极大的帮助,是学习ACM竞赛和算法设计的宝贵参考资料。