中山大学ACM竞赛模板：高精度算法与计算几何

"中山大学的ACM模板，包含高精度计算、计算几何、图论算法、数据结构、数论算法、字符串处理、模拟算法、特殊问题解决以及排序算法等多个方面的内容，适用于ACM竞赛和算法学习。" 中山大学的ACM模板是一份详尽的算法集，涵盖了多个计算机科学的重要领域，旨在帮助参赛者和学习者准备ACM国际大学生程序设计竞赛。这份模板特别强调了算法的实用性和效率，采用A5排版，方便打印和携带。 1. **高精度计算** - 高精函数：模板提供了基础的大数运算，如高精度加法、高精度乘法等，支持大数与单精度数的混合运算。 - 高精开方：实现了高精度下的开方算法，对于需要精确计算平方根的题目非常有用。 - 高精类：定义了一个完整的高精度数类，包含各种操作方法，方便进行大数操作。 2. **计算几何** - 凸包：包含了计算几何中的凸包算法，如Graham扫描或Jarvis步进法，用于找出一组点的最小外接多边形。 - 最远点对和最近点对：分别用于寻找点集中距离最远和最近的点对。 - 简单多边形的重心：计算多边形的质心或重心。 - 直线问题：处理直线与点、直线与直线之间的关系。 - 计算多边形面积：包括凹凸多边形的面积计算方法。 3. **图论算法** - 生成树问题：涵盖Prim、Kruskal等构造最小生成树的方法。 - 最短路问题：Dijkstra、Floyd-Warshall等算法解决单源最短路径问题。 - 网络流问题：包括最大流算法，如Ford-Fulkerson的标号法和前向推进法，以及最小费用最大流问题。 - 二分图问题：最大基数匹配和最大权匹配的实现。 - Euler回路和连通性问题：识别图中的Euler回路和割顶、桥等连通性概念。 4. **数据结构** - 堆：提供优先队列操作，如插入、删除、调整等。 - 线段树：用于区间查询和修改操作。 - 树状数组：快速更新和查询区间和。 - 哈希表：快速查找和插入元素。 - 左偏树：一种自平衡二叉搜索树，用于高效地处理插入和删除操作。 5. **数论算法** - 简单的数论算法：包括最大公约数、中国剩余定理、Euler函数等。 - 随机素数测试与大数分解：用于素性检验和大整数分解。 6. **字符串处理** - KMP算法：解决字符串匹配问题，避免冗余比较。 - 后缀数组：用于构建和操作后缀数组，用于字符串的复杂查询。 - LIS（最长递增子序列）和最小串表示法：优化字符串操作。 - 最大公共上升子列：在数组中找到最长的公共上升子序列。 7. **模拟算法** - 表达式求值：模拟计算表达式的结果。 8. **特殊问题** - LCA（最近公共祖先）+ RMQ（范围最值查询）：处理树上和数组上的查询问题。 - FFT（快速傅里叶变换）：用于多项式乘法和其他信号处理任务。 9. **排序算法** - 快速排序：寻找第n大数的版本，适用于部分排序需求。 - 归并排序：计算逆序数，常用于统计数组的逆序对数量。 - 希尔排序：改进的插入排序，适合处理大规模数据。 - 基数排序：按位进行排序，适用于整数排序。 - STL的sort函数：C++标准库提供的排序工具，可灵活应用于多种场景。 这份模板全面且实用，是学习和参与ACM竞赛的重要参考资料。通过深入理解和实践这些算法，可以显著提升编程能力和问题解决能力。