吉林大学ACM竞赛代码模板集合

"吉林大学ACM代码模板是一个用于ACM竞赛的编程模板集，包含了多种算法和数据结构的实现，旨在帮助参赛者高效地解决竞赛中的问题。" 本模板覆盖了多个关键领域的算法和数据结构，包括高精度计算、计算几何、图论、数据结构、数论以及字符串处理等。下面将详细介绍这些领域的知识点： 1. 高精度计算： - 高精函数：提供大数的加法、加单精度数和乘单精度数的功能。 - 高精开方：实现了大数的平方根计算。 - 高精类：封装了高精度运算的一系列方法。 2. 计算几何： - 凸包：用于找到一组点的最小外接多边形。 - 最远点对：找出给定点集中距离最远的两个点。 - 最近点对：寻找点集中距离最近的两个点。 - 简单多边形的重心：计算多边形的质心。 - 直线问题：处理与直线相关的几何问题。 - 计算多边形面积：计算凹凸多边形的面积。 - 判断点线在多边形内：检测点是否位于多边形内部或线上。 3. 图论算法： - 生成树问题：解决最小生成树和最大生成树的问题。 - 最短路问题：包括Dijkstra算法和Floyd-Warshall算法等，用于求解图中两点间的最短路径。 - 网络流问题：包括最大流和最小费用最大流的算法，如Ford-Fulkerson和Edmonds-Karp算法。 - 二分图问题：涉及最大基数匹配和最大权匹配的计算。 - Euler回路：寻找图中的Euler路径或回路。 - 连通性问题：包括割顶和桥的检测，以及极大强连通分支的查找。 4. 数据结构： - 堆：支持优先队列操作，如插入、删除和调整。 - 线段树：用于区间查询和更新操作。 - 树状数组：一种高效的数据结构，用于区间查询和单点修改。 - 哈希表：实现快速的查找、插入和删除操作。 - 左偏树：一种自平衡的二叉查找树。 5. 数论算法： - 基本的数论运算：如最大公约数（GCD）、扩展欧几里得算法和Euler函数。 - 随机素数测试：验证一个数是否为素数。 - 大数分解：将大数分解为其因子。 6. 字符串处理： - KMP算法：高效的字符串匹配算法，避免冗余比较。 - 后缀数组：用于处理字符串的各种操作，如最长公共前后缀。 - LIS（最长递增子序列）：在O(n log n)的时间复杂度内找到最长递增子序列。 - 最小串表示法：用最短的字符串表示原字符串。 - 最大公共上升子列：寻找两个序列的最大公共上升子序列。 7. 模拟算法： - 表达式求值：解析并计算数学表达式的值。 8. 特殊问题： - LCA+RMQ：最近公共祖先（Lowest Common Ancestor）与区间最值查询。 - FFT（快速傅里叶变换）：用于多项式乘法和其他数值计算。 9. 排序算法： - 快速排序：快速找到数组中第n大的元素。 - 归并排序：稳定排序，可用于计算逆序数。 - 希尔排序：改进的插入排序，时间复杂度为O(n^1.3)。 - 基数排序：非比较型排序，基于数字的位数进行排序。 - STL的sort函数：C++标准库提供的通用排序函数。 这些代码模板为ACM竞赛提供了全面的工具集，涵盖了竞赛中可能遇到的大多数问题，有助于参赛者快速编写高效解决方案。