ACM竞赛入门与核心知识点总结

"ACM必备知识" ACM竞赛（国际大学生程序设计竞赛）涉及的知识面广泛，主要包括图论、组合数学、计算几何/解析几何以及数论等方面。以下是对这些领域的详细阐述： 一、图论 1. 最短路径问题：BFS用于非负边权最短路径，Dijkstra算法适用于非负权重，而Bellman-Ford可以处理负权重。Bellman-Ford的Yen氏优化用于寻找多条最短路径，差分约束系统和Floyd算法则解决更复杂的路径问题。 2. 生成树问题：最小生成树如Prim或Kruskal算法，第k小生成树，最优比率生成树和0/1分数规划，以及度限制生成树等。 3. 连通性问题：DFS用于判断图的连通性，割点、割边、二连通分支、强连通分支以及2-SAT等概念。 4. 有向无环图（DAG）：拓扑排序及其与动态规划的关联。 5. 匹配问题：最大匹配、最小路径覆盖、0/1矩阵的最小覆盖、完备匹配和最优匹配。 6. 网络流问题：理解网络流模型与线性规划的关系，最大流最小割定理，最大流问题的Ford-Fulkerson算法等，以及有上下界的最大流和最小费用最大流。 二、组合数学 1. 思路：逼近方法（如二分、三分、N分），递推和动态规划。 2. 概率问题：如Polya定理的应用。 三、计算几何/解析几何 1. 叉积和面积是计算几何的基础，复数在解析几何中起到关键作用。 2. 基本几何对象：点、直线、线段和多边形。 3. 凸多边形/凸包：Graham扫描法用于构建凸包，水平序处理共线点，完美凸包算法解决判定问题，如两直线、线段相交以及点在多边形内的判定。 4. 经典问题：最小外接圆的计算，点集直径，旋转卡壳和对踵点，以及多边形的三角剖分。 四、数论 1. 最大公约数：Euclid算法和扩展的Euclid算法，同余方程/不定方程的解法。 2. 线性方程组：高斯消元法处理线性方程组，mod2域上的解法，整系数方程组的精确解。 3. 矩阵：行列式计算和矩阵乘法在递推关系中的应用。 4. 分数：分数树和连分数逼近。 5. 数论计算：求约数个数、欧拉函数φ(N)、约数和，以及快速数论变换。 6. 素数问题：概率判素算法，如Miller-Rabin测试，以及素数的其他性质。 这些知识点构成了ACM竞赛的基础，掌握它们能帮助参赛者更好地解决复杂算法问题。在学习过程中，建议先广后精，系统性地掌握各种算法和理论，并通过实际编程练习来提升能力。