ACM竞赛代码整理：基础算法与数据结构

"这是一份ACM竞赛代码整理的PDF文档，版本0.6，由Tiaotiao编撰。文档包含基础算法、数据结构、图论和计算几何等多个章节，旨在帮助参赛者准备ACM编程竞赛。" 文档中详细列举了各种常用的算法和数据结构模板，对于学习和理解ACM竞赛中的核心知识非常有帮助。 ### 第一章 基础算法 1. **常用宏定义**：提供了如`clr()`用于数组清零，`cpy()`用于数组复制，以及数学运算和比较的宏定义，便于快速编写代码。 2. **欧几里德算法**：用于计算两个整数的最大公约数(GCD)。 3. **快速排序**：经典的排序算法，采用分治策略，效率高但不稳定。 4. **快速排序（通用版）**：在基本快速排序的基础上进行了改进，可能包含了对原快速排序的优化，如三数取中、随机化选取枢轴等。 5. **第K小元素**：寻找数组中的第K小元素，可以利用快速选择或优先队列实现。 6. **LIS（最长上升子序列）O(NLOGN)**：求解一个序列中最长的上升子序列，通常使用动态规划解决。 7. **RMQ（区间最值询问）**：在线性时间预处理后，可以快速查询区间内的最大值或最小值。 8. **KMP模式匹配**：字符串匹配算法，避免了不必要的回溯，提高了效率。 9. **字符串最小表示**：可能涉及到最小字典序的子串查找或压缩。 ### 第二章 数据结构 1. **并查集**：用于处理不相交集合的合并与查询，常用于解决联通性问题。 2. **HEAP（最小堆）**：一种特殊的完全二叉树，满足堆性质，常用于优先队列和求最小值。 3. **树状数组**（线段树）：用于高效地进行区间更新和查询操作。 4. **二维树状数组**：扩展了树状数组，支持二维区间操作。 5. **TRIE（字典树）**：用于存储字符串，便于进行前缀匹配和插入查找操作。 6. **后缀数组**：用于处理字符串，可以快速找到所有后缀的排序。 7. **LCP（最长公共前缀）**：求解字符串数组中每对相邻字符串的最长公共前缀。 ### 第三章 图论 1. **BELLMAN-FORD**：求解图中的负权边最短路径问题，能检测负权环。 2. **BELLMAN-FORD（队列优化）**：对原算法的优化，可能通过队列加速。 3. **Dijkstra+HEAP（最短路径）**：使用贪心策略的Dijkstra算法配合最小堆求解单源最短路径。 4. **二分图最大匹配**：采用匈牙利算法或增广路算法解决二分图的最大匹配问题。 5. **带权二分图最大匹配**：在考虑边权重的情况下求解最大匹配。 6. **最小路径覆盖**：找到图中覆盖所有顶点的最小路径集合。 7. **稳定婚姻问题**：Gale-Shapley算法解决稳定匹配问题。 8. **拓扑排序**：对有向无环图(DAG)的顶点进行线性排序。 9. **LCA（最近公共祖先）**：找到树中两个节点的最近公共祖先，这里使用了Tarjan算法。 10. **最大流**：网络流问题，求解在一个有向图中从源点到汇点的最大流量。 11. **最小费用最大流**：在求最大流的同时考虑边的费用，寻找最小总费用的流。 12. **求割点和桥**：识别图中删除某个节点或边会导致连通性改变的关键元素。 13. **无向图的块**：无向图的连通分量划分。 14. **极大双连通分量**：图中最大的双连通子图。 15. **极大强连通分量**：图中最大的强连通子图。 16. **极大强连通分量缩点**：将极大强连通分量合并成一个节点，简化图的结构。 17. **2-SAT判定**：2-SAT问题是一个布尔逻辑满足性问题，可以判断是否存在一组分配使得所有子句都为真。 ### 第五章 计算几何 1. **三维凸包**：在三维空间中找到一组点的最小凸多面体，通常使用格雷码或其他高效算法。 这份文档详细地涵盖了ACM竞赛中常见的算法和数据结构，对于准备参赛的学生或者想要深入学习算法的开发者来说，是一份宝贵的参考资料。