ACM竞赛两年算法精华：从最短路到欧拉函数

本文档详细总结了两年ACM竞赛中涉及的主要算法，包括但不限于最短路径、最小生成树、动态规划、字符串处理、博弈论、大数运算、哈希算法、排序算法以及图论问题等。以下是每个部分的详细知识点： 1. **最短路**：文档提到了Floyd算法和Dijkstra算法，其中Floyd算法的时间复杂度为O(n^3)，适用于有负权边的情况。Floyd算法示例展示了如何在一个带权重的图中找到任意两点之间的最短路径，例如69个节点间的路径。 2. **最小生成树**：Kruskal算法和Prim算法是构建最小生成树的经典方法。Kruskal通过边的增序合并，Prim则从一个顶点开始逐步扩张。 3. **动态规划**：涉及01背包、完全背包和多重背包问题，以及最长公共子序列和单调递增子序列等，如使用二分查找优化单调递增子序列的求解。 4. **字符串匹配**：KMP算法是一种高效的字符串匹配算法，字典树（Trie）和AC自动机用于高效处理字符串查找和匹配问题。 5. **博弈论**：文档介绍了三种常见的博弈类型：巴什博奕、威佐夫博弈和尼姆博弈，这些都是经典的游戏理论概念。 6. **大数运算**：涵盖了浮点大数加法、大数乘法、大数开方等操作，对于精度要求高的计算场景非常关键。 7. **Hash算法**：使用除留余数法和链地址法实现哈希函数，用于数据的快速查找和存储。 8. **排序算法**：堆排序（最小堆）、拓扑排序和归并排序，展示了不同应用场景下的高效排序策略。 9. **图论与搜索**：二分匹配、并查集用于解决图的连接性和查询问题，最大流算法用于网络流问题。 10. **数论与组合数学**：欧拉函数、扩展欧几里得算法、费马小定理和莫比乌斯函数，这些是数论中的核心概念。 11. **数值计算**：矩阵快速幂用于高效计算幂运算，表达式求值涉及解析和计算表达式的值。 12. **高级主题**：后缀自动机（SAM）用于字符串处理，计算n的阶乘位数和判断/求解多边形问题，如凹凸多边形判定、面积计算，以及暴力生成素数数组和特定求和公式。 文档提供的算法覆盖了基础到进阶的计算机科学领域，对参与ACM竞赛的学生和工程师来说是一份宝贵的参考资料。