中山大学ACM算法模板集合

"中山大学ACM模板包含了C++编写的多种经典算法模板，适用于ACM算法竞赛，包括高精度计算、计算几何、图论算法、数据结构、数论算法、字符串处理、模拟算法以及特殊问题的解决方案等。" 这篇资源详细列举了多个领域的算法模板，以下是对这些算法的详细说明： 1. **高精度算法**： - **高精函数**：提供了大数的加法、高精与单精度数的加法、高精与单精度数的乘法等基本操作。 - **高精开方**：实现了大数的平方根计算。 - **高精类**：包含完整的高精度运算，如减法、除法等，便于处理大整数的计算。 2. **计算几何**： - **凸包**：用于计算给定点集的最小外接多边形。 - **最远点对**：找出点集中距离最远的两点。 - **最近点对**：寻找点集中距离最近的两点。 - **简单多边形的重心**：计算多边形的几何中心。 - **直线问题**：处理直线相关的几何问题。 - **计算多边形面积**：计算凹凸多边形的面积。 - **判断点线在多边形内**：确定点是否位于多边形内部或边界上。 3. **图论算法**： - **生成树问题**：如Prim算法或Kruskal算法，用于找到图的最小生成树。 - **最短路问题**：包括Dijkstra算法和Floyd-Warshall算法等，解决图中两点间的最短路径。 - **网络流问题**：包括最大流问题的标号法和前向推进法，以及最小费用最大流问题的求解。 - **二分图问题**：解决最大基数匹配和最大权匹配问题。 - **Euler回路**：寻找图中的Euler路径或回路。 - **连通性问题**：检测图的割顶、桥和极大强连通分支。 4. **数据结构**： - **堆**：支持优先队列操作，如插入、删除、调整等。 - **线段树**：用于区间查询和修改，例如求和、最大值等。 - **树状数组**：快速实现区间更新和查询，常用于求和问题。 - **哈希表**：提供高效的数据查找、插入和删除操作。 - **左偏树**：一种自平衡二叉查找树，适用于频繁的插入和删除操作。 5. **数论算法**： - **简单的数论算法**：包括最大公约数、扩展欧几里得算法、中国剩余定理和Euler函数。 - **随机素数测试与大数分解**：用于素性检验和大整数的质因数分解。 6. **字符串处理**： - **KMP算法**：高效的模式匹配算法。 - **后缀数组**：用于字符串的排序和查找子串。 - **LIS(nlogn)**：最长递增子序列的线性时间复杂度算法。 - **最小串表示法**：用最少字符表示一个字符串。 - **最大公共上升子列**：寻找两个序列的最大公共上升子序列。 7. **模拟算法**： - **表达式求值**：实现表达式的计算，例如四则运算。 8. **特殊问题**： - **LCA+RMQ**：最近公共祖先和区间最值查询。 - **FFT**：快速傅里叶变换，用于多项式乘法等。 - **最大团**：求解图的最大团问题。 9. **排序**： - **快速排序(找第n大数)**：快速排序算法，并扩展为找出第n大的元素。 - **归并排序(逆序数)**：利用归并排序计算逆序对数量。 - **希尔排序**：基于插入排序的快速排序改进版。 - **基数排序**：按位进行排序，适合于处理非负整数。 - **STL的sort函数**：C++标准库提供的通用排序算法。 以上就是中山大学ACM模板中涵盖的主要算法和数据结构，这些模板为ACM竞赛和实际问题的解决提供了强大的工具。