ACM竞赛算法攻略：数论、图论与树的精髓

"本文主要介绍了ACM竞赛中的关键算法和数据结构，包括数论、图论和树的相关知识，这些都是ACM修炼过程中必备的基础。" 一、数论 数论在ACM竞赛中扮演着重要角色，其中包括： 1. 筛选法：用于快速找出一个范围内的素数，如埃拉托斯特尼筛法。 2. 欧拉函数：计算小于或等于n的正整数中与n互质的数的数量。 3. 快速幂取余和快乘取余：高效计算大数乘法和模幂运算。 4. 扩展欧几里得算法：求解最大公约数和线性同余方程的解。 5. 中国剩余定理：解决一组同余方程的问题，当模数两两互质时，存在唯一解。 6. 逆元：找到a关于模n的乘法逆元，即满足a*x ≡ 1 (mod n)的x。 7. 费马小定理：在质数p下，如果a与p互质，a^(p-1) ≡ 1 (mod p)，可用于快速求逆元。 二、图 图论算法在ACM中广泛应用于解决最短路径、最大匹配等问题： 1. 链式前向星：图的存储结构，用于实现Dijkstra、Bellman-Ford等算法。 2. 最短路： - Dijkstra算法：处理非负权单源最短路，时间复杂度为O(V^2)。 - Bellman-Ford算法：可以处理负权边，时间复杂度为O(VE)。 - SPFA算法：亦可处理负权边，最坏情况下时间复杂度为O(VE)。 - Floyd算法：处理多源最短路，时间复杂度为O(V^3)。 3. 二分图的最大匹配： - 最小顶点覆盖、最大独立集与最大匹配的关系：最小顶点覆盖数等于最大匹配数，最大独立集数等于节点数减去最大匹配数。 4. 拓扑排序：对有向无环图进行排序，时间复杂度为O(V+E)。 三、树 树相关问题通常涉及最小生成树和最近公共祖先等： 1. 最小生成树： - Prim算法：贪心算法，时间复杂度为O(V^2)。 - Kruskal算法：基于并查集，时间复杂度为O(ElogE)。 2. 最小树形图：也称朱刘算法，用于解决树形图的构造问题。 3. LCA（最近公共祖先）： - Tarjan算法：求解给定两个节点的最近公共祖先，是解决树上动态查询的关键。 这些只是ACM修炼之路的基础部分，随着技能的提升，还需要深入学习高级算法和技巧，如强连通分量、网络流、字符串处理、位操作等，以及如何优化算法以适应实际比赛的时限要求。通过不断练习和学习，可以逐步成为一名优秀的ACM竞赛选手。