吉林大学ACM算法竞赛例程：标准代码库

"ACM例程 tenshi例程是吉林大学为ACM算法竞赛者提供的一个标准代码库，由上海交通大学计算机科学与工程系的HaoYuan在2003年10月23日编撰。这个库涵盖了算法和数据结构等多个方面的内容，对参赛者提升算法设计和实现能力非常有帮助。" 该资源主要包含以下知识点： 1. **高精度计算**：提供了C语言和C++实现的高精度计算方法，支持大整数运算，这对于处理需要精确计算的问题至关重要。 2. **浮点数高精度**：除了整数，还包括了高精度浮点数的处理，这对于需要精确浮点运算的算法非常关键。 3. **分数类(FractionClass)**：实现了分数的运算，包括加减乘除等，是处理分数计算问题的基础。 4. **二项堆(BinaryHeap)**：二项堆是一种特殊的完全二叉树，常用于优先队列，如Dijkstra算法或Prim算法中。 5. **胜者树(WinnerTree)**：胜者树用于快速查询和更新最小元素，是某些数据结构和算法中的高效工具。 6. **数字树(DigitalTree)**：数字树常用于字符串搜索和排序，如后缀数组(SuffixArray)的构建。 7. **区间树(SegmentTree)**：区间树能高效地进行区间查询和修改操作，适用于动态维护区间信息的问题。 8. **IOI 2001中的区间树(SegmentTree in IOI’2001)**：这是特定竞赛中使用的区间树变体，可能具有特定的优化或应用。 9. **并查集(Union-Find Set)**：并查集用于处理集合的合并和查找问题，常用于解决连通性问题。 10. **快速排序(QuickSort)**：快速排序是一种高效的排序算法，时间复杂度为O(n log n)。 11. **归并排序(MergeSort)**：归并排序也是稳定的排序算法，适用于大数据量的排序。 12. **基数排序(RadixSort)**：基数排序基于数字的位来进行排序，尤其适合处理整数数组。 13. **选择第k小元素(SelectKthSmallestElement)**：这是一个寻找数组中第k小元素的算法，对在线性时间复杂度内解决问题很有用。 14. **KMP模式匹配(KMP)**：KMP算法用于字符串搜索，避免了不必要的回溯，提高了效率。 15. **后缀排序(SuffixSort)**：后缀排序用于对字符串的所有后缀进行排序，是构建后缀数组的基础。 16. **图论和网络算法**： - 单源最短路径： - Dijkstra算法配合二项堆实现 - Bellman-Ford算法配合队列实现 - 最小生成树： - Kruskal算法 - 最小有向生成树 - 二分图的最大匹配 - 二分图的最大费用完美匹配 - 一般图的最大匹配 - 最大流： - Ford-Fulkson算法在矩阵形式的实现 - Ford-Fulkson算法在链式前向星结构的实现 - 最小费用最大流： - 在矩阵和链式前向星结构中的实现 - 鉴别正则有向图(ChordalGraph识别) 这些算法和数据结构是ACM竞赛中常见的问题类型，通过学习和理解这些例程，参赛者可以提高自己的编程和问题解决能力。