ACM算法大全：从基础到高级，一网打尽

"本文档是博主精心整理的ICPC（国际大学生程序设计竞赛）算法集合，涵盖了ACM竞赛中常见的算法和数据结构，旨在帮助参赛者系统学习和复习。" 这篇整理包括了多个算法和数据结构的模板，例如： 1. **最大公约数 (GCD)**：提供了计算两个整数最大公约数的基本实现，通过递归的欧几里得算法实现。 2. **扩展欧几里得算法 (ex-GCD)**：用于求解线性同余方程，同时返回x和y的值，使得gcd(a, b) = ax + by。 3. **最短路径算法**：提到了Dijkstra算法的堆优化版本，以及邻接矩阵的表示方法。 4. **最小生成树算法**：包括Prim和Kruskal算法，用于寻找加权无向图中的最小生成树。 5. **动态规划 (DP)**：涵盖了多种类型的DP问题，如一维、二维DP，以及背包问题（完全背包、多重背包）等。 6. **图的遍历与搜索**：如深度优先搜索(DFS)和广度优先搜索(BFS)，以及它们在最短路径问题中的应用。 7. **数据结构**：如二叉树的遍历和重建，ST表（部分sum查询），并查集，以及堆（优先队列）的应用。 8. **图论**：介绍了染色法判断二分图、匈牙利算法（Kuhn-Munkres算法）解决匹配问题。 9. **数学模板**：涉及素数判定和筛法（试除法、朴素筛法、线性筛法），欧几里得算法，快速幂，矩阵快速幂，扩展欧几里得算法，以及博弈论中的巴什博奕、威佐夫博奕和尼姆博奕。 10. **STL函数库**：标准模板库中的函数和工具的使用。 11. **快速数论变换**：如FFT/IFFT在快速计算多项式乘法中的应用。 12. **位运算**、**双指针**和**离散化**技术在算法中的应用。 13. **前缀和**和**差分**：用于高效处理序列的累加和问题。 14. **树状数组**：用于支持区间查询和修改操作。 15. **区间合并**和**数位DP**模板：处理区间操作的问题。 16. **其他**：如判断几何形状、线段相交，求无向图中的三元环数量，大组合数求模，线性求逆元，除法分块，线段树的升级功能，求解不定方程，求极值，最小费用最大流，左偏树和可并堆，马拉车算法（求最长回文子串），手动开平方根，中国剩余定理等。 这个集合不仅包含了基础算法，还有高级算法和特定问题的解决方案，对于准备参加ICPC或ACM竞赛的学生来说是一份宝贵的资源。通过深入理解和熟练运用这些模板，可以提升解决问题的能力，提高编程竞赛的成绩。