ACM算法模板总结：大数、搜索、最短路等

"常见算法代码（全）.docx" 这篇文档是一个针对ACM竞赛的算法模板集合，包含了多种常用算法的C/C++实现。它旨在帮助初学者理解和记忆常见问题的解决策略，并提供可复用的代码模板。文档涵盖的算法范围广泛，包括大数操作、二分查找、枚举排列、子集生成、回溯法（如n皇后问题）、并查集、树状数组、字符串匹配算法（KMP、Sunday、BM）、动态规划问题（如01背包和完全背包）、最长上升/下降子序列、最长公共子序列、拓扑排序、欧拉路径和回路、图的最小生成树和最短路径算法、最大公约数（GCD）和最小公倍数（LCM）、埃拉托斯特尼筛法、唯一分解定理、扩展欧几里得算法、欧拉函数、快速幂以及矩阵快速幂。 1. 大数：大数运算通常用于处理超过标准整型变量范围的数字。文档提供了加法和乘法的模板，以处理字符串形式表示的大数。例如，通过将每一位相加并处理进位来实现加法，通过逐位相乘然后累加结果来实现乘法。 2. 二分查找：二分查找是一种在有序数组中查找特定元素的高效方法，其时间复杂度为O(log n)。文档中可能包含了如何在适当的数据结构上实现二分查找的代码。 3. 枚举排列与子集生成：这些算法常用于找出所有可能的组合，如全排列和子集。它们通常涉及递归或回溯技术。 4. n皇后回溯：这是一个经典的回溯问题，目标是在n×n棋盘上放置n个皇后，使得没有两个皇后在同一行、同一列或同一对角线上。 5. 并查集：用于维护一组不相交集合的动态联合/查找操作，常用于解决连通性问题。 6. 树状数组：也称为线段树，是一种数据结构，可以高效地支持区间查询和修改操作。 7. KMP、Sunday、BM字符串匹配算法：这些是改进的字符串搜索算法，比朴素的线性搜索更高效。 8. 动态规划：01背包和完全背包问题属于动态规划的经典实例，通过状态转移方程求解背包问题的最优解。 9. 拓扑排序：在无环有向图中，拓扑排序可以给出顶点的无序序列，使得对于每条有向边 (u, v)，u 都在 v 之前。 10. 最小生成树和最短路径：如Prim's算法和Dijkstra算法，用于找到图中的最小生成树和节点间的最短路径。 11. GCD和LCM：最大公约数和最小公倍数是数论中的基本概念，可用于简化数值计算。 12. 埃拉托斯特尼筛法：用于找出小于给定数的所有质数。 13. 唯一分解定理和扩展欧几里得：与整数的因子分解和线性同余方程的求解有关。 14. 欧拉函数：欧拉函数φ(n)表示小于n且与n互质的正整数的个数。 15. 快速幂和矩阵快速幂：快速幂用于高效地计算幂次，而矩阵快速幂则应用于高维矩阵的快速幂运算。 这个文档是ACM竞赛选手或对算法感兴趣的程序员的宝贵资源，提供了各种常见问题的解决方案和代码模板，有助于提升编程和算法设计能力。虽然作者自称是ACM小白，但提供的代码和思路对于初学者来说是非常实用的。