中山大学ACM竞赛程序模板：高精度、计算几何与图论算法

"中山大学ACM竞赛程序模板(c/c++)" 这篇资源主要涵盖了中山大学用于ACM竞赛的C/C++程序模板，包含了多种算法和数据结构的实现，旨在帮助参赛者快速解决各种算法问题。以下是详细的知识点： 1. 高精度算法： - 提供了高精度加法、乘法等基础操作的函数，如`add`用于大数加法，`by`用于高精度乘法。 - 高精度开方：实现了计算高精度数的平方根的功能。 - 高精度类：可能包含了一组完整的高精度运算方法，如减法、除法、比较等。 2. 计算几何： - 凸包算法：用于找到一组点中的最小凸包。 - 最远点对：计算给定点集中最远的两点组合。 - 最近点对：寻找点集中的最近点对。 - 简单多边形的重心：计算多边形的几何中心。 - 直线问题：可能包括直线与点的关系判断，直线相交等。 - 计算多边形面积：无论是凹多边形还是凸多边形，都能计算其面积。 - 点线在多边形内的判断：确定点是否位于多边形内部，以及线段是否穿过多边形。 3. 图论算法： - 生成树问题：可能包括Prim算法或Kruskal算法，用于找到图的最小生成树。 - 最短路问题：Dijkstra算法或Floyd-Warshall算法，用于计算图中两点间的最短路径。 - 网络流问题：最大流算法，如Ford-Fulkerson算法的两种变体：标号法和前向推进法，以及最小费用最大流问题的解决方案。 - 二分图问题：最大基数匹配和最大权匹配的算法实现。 - Euler回路：寻找图中的Euler回路，即从一个顶点出发，经过所有边且不重复的路径。 - 连通性问题：包括割顶和桥的检测，以及极大强连通分支的查找。 4. 数据结构： - 堆：提供了堆排序或优先队列的实现。 - 线段树：用于区间查询和修改操作的数据结构。 - 树状数组：快速处理区间和问题的数据结构。 - 哈希表：用于快速查找和插入元素。 - 左偏树：一种自平衡的二叉搜索树。 5. 数论算法： - 基本的数论操作：包括最大公约数、扩展欧几里得算法、中国剩余定理。 - 随机素数测试和大数分解：用于素性检验和大整数的质因数分解。 6. 字符串处理： - KMP算法：快速进行模式匹配。 - 后缀数组：用于处理字符串的后缀，常用于最长公共前后缀的查找。 - LIS（最长递增子序列）：在线性时间复杂度内找到序列的最长递增子序列。 - 最小串表示法：找到表示所有子串的最短串。 - 最大公共上升子列：找到两个序列的最长公共上升子序列。 7. 模拟算法： - 表达式求值：实现对数学表达式的求值。 8. 特殊问题： - LCA（最近公共祖先）和RMQ（Range Minimum Query）：在树上快速查找最近公共祖先，以及查询区间内的最小值。 - FFT（快速傅里叶变换）：用于高效地进行复数或实数序列的离散傅里叶变换。 - 最大团：寻找图中最大大小的完全子图。 9. 排序算法： - 快速排序：用于整体排序，同时提供找第n大数的优化。 - 归并排序：稳定排序，可以计算逆序数。 - 希尔排序：改进的插入排序，效率高于普通插入排序。 - 基数排序：按位进行的排序，适合于整数排序。 - STL的`sort`函数：C++标准库提供的排序功能。 这些模板覆盖了ACM竞赛中常见的问题类型，可以帮助参赛者快速编写出高效且正确的代码。