ACM算法模板：图论、字符串处理与数学策略

"kuangbin的ACM模板.pdf" 是一份关于ACM竞赛的算法模板集合，涵盖了图论、字符串处理、数学等多个方面的重要算法，旨在帮助参赛者快速解决各类问题。 1. 图论 - 网络流 - 最大流：包括算法模板，如Ford-Fulkerson或Edmonds-Karp算法，用于找出图中从源点到汇点的最大流量。此外，还涉及二分图匹配、上下界可行流、多源汇最大流、关键边的识别、最大流判定、拆点策略以及建图实战。 - 最小割：包含算法模板，常用于网络优化问题，比如直接应用、最大权闭合图、最大密度子图、最小点权覆盖集、最大点权独立集等，也有建图实战的讲解。 - 费用流：考虑了边的代价，寻找具有最小总费用的最大流量。 2. 字符串处理 - KMP算法：一种高效的模式匹配算法，避免了不必要的回溯。 - e-KMP：KMP算法的改进版，增加了错误位置的信息。 - Manacher算法：处理回文字符串的高效算法，避免了重复计算。 - AC自动机：Aho-Corasick自动机，用于在文本中同时查找多个模式串。 - 后缀数组：用于字符串排序和字符串查询，包括DA(Dynamic Array)和DC3算法。 - 后缀自动机：快速查找字符串后缀的工具，包含基本函数及应用例题。 - 字符串hash：用于快速比较两个字符串是否相等，减少了全比较的时间复杂度。 3. 数学 - 素数：包括素数筛选算法，如Sieve of Eratosthenes，用于判断或筛选素数。 - 扩展欧几里得算法：求解最大公约数的同时，还可找到逆元。 - 模线性方程组：解同余方程组的方法。 - 随机素数测试和大数分解：处理大整数的运算。 - 欧拉函数：计算一个数的欧拉函数值，与素数筛选和合数分解相关。 - 高斯消元：用于解决线性方程组，包括浮点数的处理。 - FFT（快速傅里叶变换）：用于快速计算多项式乘法。 - 斐波那契数列取模循环节：研究斐波那契数列模一定数后的周期性。 - 原根：在模意义下，原根是满足特定性质的数。 - 快速数论变换：如在HDU4656问题中的卷积取模应用。 这些模板是ACM竞赛中解决问题的基础，提供了详细的算法模板和实践示例，帮助参赛者快速理解并实现各种复杂问题的解决方案。对于参加ACM竞赛或希望提升算法能力的程序员来说，这份资源是非常宝贵的。