SOWHAT ACM/ICPC 竞赛模板集

"acm各类模板" 本书是一部针对ACM（国际大学生程序设计竞赛）的电子书，主要涵盖了ACM比赛常用的代码模板和算法，旨在帮助参赛者提升编程技能和解决问题的能力。书中详细讲解了各种数学、图论、数据结构等领域的基础理论和实现方法。 在数学部分，书中介绍了基本的公式和算法，包括欧几里得算法（用于计算最大公约数）、快速欧几里得算法（提升效率的版本）、扩展欧几里得算法（求解线性同余方程）、中国剩余定理（解决多个同余方程组的问题）、快速幂模（高效计算幂运算模）、欧拉函数（求解小于等于给定数的正整数中与该数互质的数的数量）、质因子分解（分解一个数为质因数的乘积）、素数线性筛法（快速找出一定范围内的素数）以及millerrabin素数测试（概率性检测素数的方法）。 图论部分涉及了最短路径和最小生成树的算法。最短路径中，包括了Dijkstra算法（单源最短路径）、SPFA（Shortest Path Faster Algorithm，一种改进的Bellman-Ford算法）、Floyd算法（多源最短路径）以及Bellman-Ford算法（处理负权边的最短路径）。最小生成树部分则讲解了Prim算法和Kruskal算法。 在二分图匹配方面，书中提到了匈牙利算法和KM算法，这两种方法常用于解决分配问题。接着是网络流问题，包括最大流算法（如Edmonds-Karp算法和Dinic算法以及SAP算法）和最小费用最大流算法。此外，还讨论了有上下界的最大流问题以及混合图的欧拉回路。 图论中的连通性问题，如强连通分量（Kosaraju算法和Tarjan算法）和双连通分量（Tarjan算法），也得到了详细的阐述。数据结构部分涵盖了Hash函数、堆、二叉查找树、AC自动机（用于字符串匹配）和Trie树（字典树）、树状数组以及线段树（用于区间查询和更新）。 线段树的讲解中，不仅介绍了线段树的基本概念，还提供了线段树节点的定义、扫描线定义、一般模板以及如何处理矩形面积的交集和并集问题。 这本书是ACM竞赛选手的重要参考资料，通过学习这些模板和算法，可以有效提高选手在竞赛中的表现和解决问题的速度。