全面的ACM算法模板：图论、数论到数据结构

这份资源主要涵盖了ACM竞赛中常见的算法和数据结构知识点，包括图论、数论、数据结构、计算几何、问题解决等多个方面。以下是这些领域的详细解释： 1. 图论： - 术语：涉及到图的基本概念，如顶点、边、邻接矩阵、邻接表等。 - 独立集、覆盖集、支配集：独立集是图中互不相邻的顶点集合；覆盖集是图中至少包含每个顶点的边的集合；支配集是能覆盖所有顶点的最小顶点集合。 - DFS（深度优先搜索）：遍历图的一种方法，用于发现边连接的顶点。 - 割顶、桥：割顶是指移除后导致图分成分离的顶点；桥是移除后使两个连通分量分离的边。 - 强连通分量：图中任意两个顶点都互相可达的子图。 - 最小点基：在图的点覆盖问题中，找到覆盖最少顶点的集合。 - 拓扑排序：有向无环图(DAG)的顶点排序，使得对于每条有向边(u, v)，u都在v之前。 - 欧拉路与哈密顿路：欧拉路是经过图中所有边一次且仅一次的路径；哈密顿路是经过图中所有顶点一次且仅一次的路径。 - Bellman-Ford算法：用于求解带有负权边的最短路径问题。 - 差分约束系统：通过Bellman-Ford算法求解满足一定条件的路径。 - DAG最短路径：处理有向无环图中的最短路径问题。 - 二分图匹配：寻找二分图中最大数量的配对，匈牙利算法和KM算法是求解方法。 2. 数论： - 最大公约数(GCD)和最小公倍数(LCM)：计算两个或多个整数的最大公约数和最小公倍数。 - 快速幂取模：高效地计算模意义下的幂运算。 - Fermat小定理：在素数p下，如果a不是p的倍数，则a^(p-1) ≡ 1 (mod p)。 - Rabin-Miller伪素数测试：一种测试素数的有效方法。 - Pollard-rho算法：寻找大素数因子的算法。 - 扩展欧几里得算法：求解线性同余方程ax ≡ b (mod n) 的解。 - 欧拉定理：如果a与m互质，则a^φ(m) ≡ 1 (mod m)，其中φ(m)是欧拉函数。 - 中国剩余定理：解决多个线性同余方程组的问题。 - Discrete Logging：解决BL ≡ N (mod P)这类问题。 - N!最后一个不为0的数字：研究阶乘数尾部零的个数。 - 2^14以内的素数：列出一定范围内的素数。 3. 数据结构： - 堆（最小堆）：一种完全二叉树，父节点的值不大于其子节点。用于实现优先队列。 - 并查集：处理集合合并与查询的离散数据结构。 - 树状数组：用于高效地进行区间更新和查询的数组结构。 - 低字位1（LOWBIT）：在二进制表示中找到最低位的1。 - 线段树：用于处理区间查询和修改的树形数据结构。 - 字符串：处理文本数据，如字符串哈希和KMP算法用于模式匹配。 4. 计算几何： - 直线交点：计算两条直线的交点。 - 线段相交：检测两条线段是否相交。 - 三点外接圆圆心：找到三个点构成的圆的圆心。 - 点在多边形内的判断：确定点是否位于多边形内部。 - 两圆交面积：计算两个圆相交部分的面积。 - 最小包围圆：找到包含一组点的最小圆。 - 经纬度坐标：处理地理坐标系中的计算。 - 凸包：找到点集的最小凸多边形覆盖。 5. 问题解决（Problem）： - RMQ-LCA（Range Minimum Query & Lowest Common Ancestor）：结合区间最小值查询和最近公共祖先问题的解决方法。 这份模板是ACM竞赛准备的宝贵资料，涵盖了广泛的算法和数据结构，适合参赛者复习和提高。