【亲测免费】 ACM巨全模板资料集

这是一份ACM竞赛中常用的模板资料集合，包含了大量的算法模板和数学公式，是 ACM 竞赛选手和算法爱好者的宝贵学习资源。资料以PDF格式呈现，内容详尽，结构清晰，覆盖了竞赛中常见的数据结构、动态规划、竞争策略、数论、计算几何以及图论等多个领域。

内容目录

数据结构

• RMQ (区间最值区间出现最大次数求区间gcd)
• 二维RMQ求区间最大值 (二维区间极值)
• 线段树模板 (区间加法、染色、区间最小值)
• 线性基 (求异或第k大)
• 静态区间查询树 (静态求区间第k小)
• 权值线段树 (求逆序对)
• 动态区间查询树 (区间第k大带修改)
• 树上启发式合并 (查询子树的优化)
• 树状数组模板 (区间异或和、求逆序对)
• 区间不重复数字的和 (树状数组)
• KD树 (求k维空间中离所给点最近的m个点)
• LCA (两个节点的公共父节点)

动态规划

• LIS (最长上升子序列)
• 有依赖的背包
• 最长公共子序列 (LCS)
• 树形DP
• 状压DP-斯坦纳树
• 背包
• multset

竞争策略

• NIM竞争
• 威佐夫竞争
• 约瑟夫环
• 斐波那契竞争
• sg函数

数论

• 素数检验
• 拉格朗日乘子法
• 裂项
• 扩展欧几里得
• 勾股数
• 斯特林公式
• 牛顿迭代法
• 同余定理
• 中国剩余定理
• 二次剩余
• 十进制矩阵快速幂
• 欧拉函数
• 费马小定理
• 高斯消元
• 矩阵快速幂
• 分解质因数
• 线性递推式BM(杜教)
• 线性一次方程组解的情况
• 行列式的逆矩阵

计算几何

• 三角形 (求面积)
• 多边形
• 三点求圆心和半径
• 扫描线 (矩形覆盖求面积、周长)
• 凸包
• 多边形的直径
• 多边形的宽度
• 最小面积外接矩形

图论

• 最短路 (优先队列dijkstra、spfa、Floyd)
• 判断环 (tarjan算法)
• 最小生成树 (Kruskal、Prim)
• Dicnic最大流 (最小割)
• 无向图最小环
• 图中两点间的最长距离
• 第k短路
• 回文树模板
• 拓扑排序
• 次小生成树
• 最小树形图
• 并查集
• 最近公共祖先
• 限制顶点度数的MST
• 多源最短路
• 最短路 (输出字典序最小)
• 最长路

字符串

• 字典树
• KMP
• EXKMP
• 马拉车
• 最长前后缀
• hash
• 后缀数组
• 前缀循环节
• AC自动机
• 后缀自动机

小技巧

• 数据类型转换
• 输入输出优化
• 精度处理
• 组合数学公式
• 坐标离散化
• 向下取整处理
• STL数据结构
• Devc++使用
• 一维离散化封装
• Ubuntu对拍程序
• Codeblocks使用

本模板集合汇聚了众多算法竞赛中的经典问题和解决方案，适合作为学习和复习资料，帮助竞赛选手系统性地掌握算法竞赛所需的知识点和技巧。