### ACM知识点概览
在ACM（Association for Computing Machinery）竞赛中，参赛者需要掌握广泛且深入的计算机科学与编程技巧。以下是从标题、描述、标签以及部分内容中提炼出的关键知识点，这些知识点对于ACM入门者尤其重要：
#### 1. 最大公约数算法 (GCD)
GCD算法是计算两个或多个整数共有约数中最大的一个。其中提到的公式`gcd(a,b)=ax+by`指的是扩展欧几里得算法，它不仅计算出两个数的最大公约数，还能找到一组解(x, y)，满足`ax + by = gcd(a, b)`。
#### 2. Miller-Rabin素性测试
Miller-Rabin是一种高效的素性测试算法，用于判断一个数是否为素数。它基于概率原理，通过随机选取的基数进行模幂运算，来判断一个数是否可能是素数。
#### 3. 快速幂运算
快速幂运算是高效计算`a^b mod n`的一种方法，广泛应用于密码学等领域。它利用了指数的性质，将复杂度从O(b)降低至O(log b)。
#### 4. 线性同余方程求解
线性同余方程`ax ≡ b (mod n)`的求解涉及到模逆元的概念。当a和n互质时，可以找到唯一的解。若不互质，则可能无解或多解。
#### 5. 深度优先搜索（DFS）
DFS是一种图遍历策略，从图的根节点开始，尽可能深地搜索树的分支，直到遇到叶子节点或死胡同再回溯。它是解决许多图形问题的基础算法。
#### 6. 并查集（Disjoint Set）
并查集是一种数据结构，主要用于处理元素的集合合并和查询操作。常用于解决连通性问题，如社交网络中的好友关系分析。
#### 7. 解线性方程组
解线性方程组`Ax = B`涉及矩阵操作和高斯消元等技术，是数值计算和线性代数的基本技能。
#### 8. 贝尔曼-福特算法
贝尔曼-福特算法用于寻找有向图中单源最短路径，即使图中含有负权重边也能正确工作，但不能存在负权重环路。
#### 9. Dijkstra算法
Dijkstra算法同样用于求解单源最短路径问题，但仅适用于非负权重边的情况，效率通常高于贝尔曼-福特算法。
#### 10. 图的拓扑排序
拓扑排序是指对有向无环图(DAG)中的顶点进行排序，使得所有有向边(u, v)都满足u在v之前。
#### 11. Floyd-Warshall算法
Floyd-Warshall算法用于解决任意两点间的最短路径问题，适用于稠密图和含有负权重边的图。
#### 12. 弗洛伊德循环检测算法
该算法用于检测链表中是否存在环，并找出环的起始位置。通过快慢指针技术实现。
#### 13. 最小生成树算法
MST Prim算法和MST Kruskal算法分别使用贪心策略和并查集数据结构，用于在加权无向图中寻找最小生成树。
#### 14. 图像填充算法
如Flood Fill算法，用于二维图像中特定区域的颜色填充，基于深度优先或广度优先搜索。
#### 15. 匈牙利算法
匈牙利算法解决的是二分图最大匹配问题，适用于求解二分图中的完美匹配。
#### 16. Kuhn-Munkres算法（KM算法）
KM算法是解决赋权二分图最大匹配问题的一种高级算法，特别适合于边的权重各不相同的情况。
#### 17. 流网络算法
包括Ford-Fulkerson算法和Push-Relabel算法，用于求解最大流问题，如在有容量限制的网络中寻找最大流量。
#### 18. 最小费用流算法
用于在网络中寻找最小费用的最大流，适用于物流、资源分配等问题。
#### 19. 数论基础
包括模运算、中国剩余定理、欧拉函数等，是ACM竞赛中解决数学问题的重要工具。
#### 20. 几何算法
如凸包、最近点对、三角剖分等，涉及点、线、面的处理，用于解决空间中的几何问题。
#### 21. 动态规划
动态规划是一种通过分解问题为子问题，存储子问题的解避免重复计算的算法策略，广泛应用于优化问题中。
#### 22. 字符串匹配算法
如KMP算法，用于在文本中高效查找模式串的位置，是文本处理中的重要工具。
#### 23. 编码理论
包括Huffman编码、格雷码等，涉及信息压缩、错误检测和纠正等领域。
#### 24. 数据结构
包括树、堆、栈、队列、哈希表等，是实现算法和解决实际问题的基础。
#### 25. 高级算法概念
如NP完整性、图着色、图同构、平面图、Voronoi图等，涉及更复杂的图形和计算理论问题。
以上只是ACM竞赛中众多知识点的一部分，掌握它们需要深入学习和大量实践。ACM竞赛不仅考验选手的编程能力，还考验其算法设计、数学思维、问题抽象和解决的能力。
