ACM算法模板集：STL、数论与计算几何

"ACM模板-Anoyer.pdf" 是一份针对ACM竞赛编程的算法和数据结构模板，包含了广泛的编程知识点，适用于解决各种算法问题。 ### STL（Standard Template Library，标准模板库） STL是C++中的一个核心部分，提供了一系列高效且泛用的数据结构和算法。模板文件中详细介绍了以下STL容器及其用法： 1. `<Vector>`：动态数组，支持随机访问和高效插入/删除操作。 2. `<List>`：双向链表，适合频繁插入和删除。 3. `<deque>`：双端队列，可以在两端进行插入和删除。 4. `<map>`：关联容器，以键值对形式存储数据，键唯一。 5. `<multimap>`：与`<map>`类似，但键可以重复。 6. `<unordered_map>`：哈希表实现的关联容器，提供快速查找。 7. `<set>`：集合，键唯一且自动排序。 8. `<multiset>`：与`<set>`类似，但元素可以重复。 9. `<String>`：用于处理字符串。 10. `<bitset>`：位集，用于高效存储和操作二进制位。 11. `<queue>`：先进先出（FIFO）队列。 12. `<stack>`：后进先出（LIFO）栈。 13. `<priority_queue>`：优先队列，元素按优先级排序。 14. `<algorithm>`：包含多种通用算法，如排序、查找、变换等。 ### 字符串处理 1. `Kmp`：Knuth-Morris-Pratt算法，用于字符串匹配。 2. 马拉车算法：用于字符串匹配，比KMP更高效。 3. 拓展KMP：KMP的改进版。 4. 编辑距离：计算两个字符串之间转换成对方所需的最少操作次数。 5. Karp-Rabin算法：快速字符串搜索算法。 6. AC自动机+Trie树：用于高效处理多个模式串的搜索问题。 7. 查找母串中各单词出现次数：统计子串在主串中出现的次数。 8. 最短公共祖先：找到树中两个节点的最近公共祖先。 9. 字符串Hash：用于快速比较两个字符串是否相同。 10. Sunday算法：字符串搜索算法。 11. 后缀数组DA和DC3：构建后缀数组的方法。 12. 后缀自动机：处理字符串查询的高效数据结构。 ### 数论 1. Miller-Rabin素性测试：用于判断大整数是否为素数。 2. 杜教筛：高效生成素数的算法。 3. log(n)复杂度分解素因子：快速分解整数的素因子。 4. 基数排序MSD：非比较型整数排序算法。 5. 矩阵快速幂：高效计算幂次的算法。 6. 莫比乌斯函数：在数论中有广泛应用。 7. 逆元模板：用于模逆运算。 8. 欧拉函数：计算小于等于n的正整数中与n互质的数的数量。 9. 素数筛：用于生成一定范围内的素数列表。 10. 拓展欧几里得：求解线性同余方程。 11. 拓展欧几里得求整数解个数：求解线性同余方程组的整数解数量。 12. 整除分块：在处理整数数组时的一种优化策略。 13. 组合数：计算组合数C(n, k)。 14. 最长循环节：找出一个数字的循环节长度。 15. 高精度模拟乘法：处理大整数乘法。 16. N的大数次方：高效计算大整数的幂。 17. 博弈论：解决零和游戏问题。 18. 线性基：处理整数集合的线性组合问题。 19. 容斥原理：计算有限集合的大小。 20. 高斯消元：解线性方程组的方法。 21. 线性筛：用于生成最小质因子序列。 ### 数据结构 1. 线段树：处理区间查询和修改的问题。 2. 并查集：用于维护不相交集合的结构。 3. 树状数组：快速查询和更新数组区间之和。 4. 一维差分数组：处理一维序列的增删改查问题。 5. 二维差分数组：处理二维数组的区间查询和修改。 ### 图论 1. Dijkstra算法：寻找图中单源最短路径。 2. Kruskal算法：构造图的最小生成树。 3. 分考场-图染色：解决图染色问题。 ### 计算几何 1. 球与球之间的相交体积与面积：计算几何问题。 2. 线段判相交及点与线的关系：判断线段间或点与线的位置关系。 3. 线与圆交点：计算直线与圆的交点。 4. kuangbin计算几何2维和3维：提供了二维和三维计算几何的实现。 5. 最大空凸包：求解空间中的最大无点区域。 这份模板全面覆盖了ACM竞赛中常见的算法和数据结构，对于参赛者来说是非常有价值的参考资料。