Acmer必备算法指南

"算法 for Acmer" 是一本面向 ACM 竞赛选手的算法指南，涵盖了众多算法和数据结构，旨在帮助读者掌握解决竞赛问题所需的技能。书中的目录详细列举了各个主题，从基础的数论到高级的图论和网络流，还包括字符串处理和计算几何等多个方面。 首先，数论部分介绍了常用的数学函数，如 GCD（最大公约数）函数，包括处理整数和小数的版本。此外，还有康拓展开，用于计算一个数字在所有排列中的位置，这对于解决某些搜索和计数问题非常有用。 接着是快速幂算法，这是一种高效的计算幂次的技巧，常用于求解模幂运算。排列组合部分讲解了组合和排列的基本概念，以及如何高效地计算它们。扩展欧几里得定理和中国剩余定理是数论中的重要工具，分别用于求解最大公约数和一组同余方程组。 在离散数学中，鸽巢原理和容斥原理是基础的计数原理，而素数相关的知识，如欧拉函数和莫比乌斯反演，则对于理解数论性质和计算有重要作用。置换和Burnside、Polya定理则涉及组合恒等式和群论。 在数据结构部分，介绍了并查集、字典树（Trie）、单调队列和栈、线段树、树状数组、RMQ（Range Minimum Query）、Treap、划分树、树链剖分、Splay树、DLX（ Dancing Links ）等。这些数据结构在解决动态查询和更新问题时非常有效。 动态规划（DP）是算法设计的关键技术，书中涵盖了背包问题、区间DP、树形DP、数位DP和状压DP等多种变体。搜索算法包括DFS（深度优先搜索）和BFS（广度优先搜索），在图论中，生成树、最短路、差分约束、Tarjan算法、LCA（最近公共祖先）和2-SAT问题的解决方法都有所涉及。 字符串处理部分，如KMP算法用于模式匹配，AC自动机处理字符串查询，Manacher算法则用于找到字符串中的最长回文子串。计算几何部分讲解了基本的几何公式、点、向量、线和圆的运算，以及半平面交、最近点对问题和多边形格点问题。 最后，书中还提到了高精度计算，包括朴素实现和完全高精度算法，以及一些通用的模板和函数，如STL的使用，以及Java编程的基础和文件定向。 这本书全面覆盖了ACMer所需的各种算法和数据结构，是学习和准备ACM竞赛的宝贵资源。