中山大学ACM算法模板：高精度、计算几何、图论与数据结构

"中山大学ACM模板 经典模板，由中山大学ACM精英团队创建，包含各种算法和数据结构的实现，适用于编程竞赛和算法学习。" 这篇资源提供了丰富的算法和数据结构模板，适用于参与ACM算法竞赛或进行算法学习的人员。以下是各个部分的详细说明： 1. **高精度计算** - 高精函数：提供了大数加法、高精加单精和高精乘单精等基本操作。 - 高精开方：实现了大数的平方根计算。 - 高精类：可能包括完整的高精度数类，包含了大数的基本运算方法。 2. **计算几何** - 凸包：用于寻找一组点构成的凸包算法。 - 最远点对：计算给定点集中最远的两点距离。 - 最近点对：找出点集中的最近点对。 - 简单多边形的重心：计算多边形的质心。 - 直线问题：处理与直线相关的计算。 - 计算多边形面积：计算凹凸多边形的面积。 - 判断点线在多边形内：检测点是否在多边形内部或线上。 3. **图论算法** - 生成树问题：如Prim、Kruskal等最小生成树算法。 - 最短路问题：Dijkstra、Floyd等算法。 - 网络流问题：包括最大流的标号法和前向推进法，以及最小费用最大流算法。 - 二分图问题：最大基数匹配和最大权匹配。 - Euler回路：寻找图中的Euler回路。 - 连通性问题：检测图的割顶和桥，以及极大强连通分支。 4. **数据结构** - 堆：包括最大堆和最小堆的实现。 - 线段树：支持区间查询和修改的操作。 - 树状数组：快速处理区间和单点更新的问题。 - 哈希表：提供快速查找和插入操作。 - 左偏树：一种自平衡二叉搜索树。 5. **数论算法** - 简单数论：最大公约数计算、欧几里得算法、中国剩余定理等。 - 随机素数测试与大数分解：用于素性检验和大整数的因数分解。 6. **字符串处理** - KMP算法：快速处理模式匹配问题。 - 后缀数组：构建后缀数组用于字符串操作。 - LIS（最长递增子序列）：在线性时间内找到序列中最长的递增子序列。 - 最小串表示法：用最少的字符表示原字符串。 - 最大公共上升子列：寻找两个序列的最大公共上升子序列。 7. **模拟算法** - 表达式求值：处理数学表达式的求值问题。 8. **特殊问题** - LCA（最近公共祖先）+ RMQ（区间最值查询）：在树结构上进行高效查询。 - FFT（快速傅里叶变换）：用于多项式乘法和其他信号处理任务。 9. **排序算法** - 快速排序（找第n大数）：在排序过程中找到第n大的元素。 - 归并排序（逆序数）：计算排序过程中的逆序对数量。 - 希尔排序：基于插入排序的改进版本。 - 基数排序：按位进行的排序算法。 - STL的sort函数：C++标准库提供的排序函数。 这个模板集合了ACM竞赛中常见的算法和数据结构，是学习和准备竞赛的宝贵资源。通过深入理解和实践这些模板，可以提升算法解决能力和编程技巧。