NOIP2017模板复习手册：核心算法概览

本资源是一份针对NOIP2017比赛的模板复习手册，名为"Kvar_ispw171"，主要涵盖数学、算法、图论、数据结构和动态规划等多个核心知识点。以下是各部分的主要内容概述： 1. **数学**： - **O(1)最大公约数**: 学习了基本的计算最大公约数的方法，包括使用C++代码实现。 - **拓展欧几里得算法**: 提供了一种高效的算法来求解两个数的最大公约数，并可能用于扩展到模运算中的逆元计算。 - **长整型快速乘**：涉及快速幂运算，提高大整数乘法的效率。 - **欧拉筛**：一种用于找出一定范围内的所有质数的高效筛选算法。 - **BSGS算法**：可能是Baillie-PSW素性测试的一种变体，用于判断大整数是否为素数。 - **中国剩余定理**：解决同余方程组的重要理论，用于模数下的求解。 - **O(n)求逆元**：讨论了如何在有限域上快速计算一个数的逆元。 - **高精度整数**：介绍了处理大整数的特殊数据结构和运算方法。 - **快速傅里叶变换（FFT）**：用于处理离散傅里叶变换，是信号处理和数字信号分析中的重要工具。 2. **图论**： - **树链剖分**：用于对树进行分解，便于处理树相关的查询问题。 - **Floyd传递闭包**：可能是指Floyd-Warshall算法，用于求解所有节点对之间的最短路径。 - **点/边双连通分量**：分析图中不可达区域，理解图的连通性和完整性。 - **最近公共祖先（LCA）**：查找具有共同祖先的节点，在树形结构中有广泛应用。 - **差分约束系统（DCS）**：可能涉及图上的动态优化问题。 - **虚树**：简化图论中的复杂度，用于理解和分析实际问题。 - **Dinic网络流**：经典的数据结构和算法，用于求解网络流问题。 - **SPFA最小费用流**：另一种求解网络流问题的算法，适用于带有权值的成本。 - **匈牙利算法**：用于解决分配问题，如任务分配或图匹配问题。 - **2-SAT**：二进制逻辑表示形式，用于解决某些组合优化问题。 - **判定与输出方案**：2-SAT的具体应用，可能涉及到问题求解的步骤。 - **拓扑排序**：对有向无环图的排序算法，用于确定节点的执行顺序。 - **树的直径**：衡量树中任意两节点间的最长路径。 - **树分块**：将树分割成多个子树，便于管理和操作。 - **静态点分治**：可能是一种递归算法策略，用于特定问题的解决方案。 3. **数据结构**： - **二维树状数组**：用于高效查询区间和更新操作的数组结构。 - **二维线段树**：处理二维区间查询的问题，类似于一维线段树的扩展。 - **堆**：包括基本的堆数据结构及其应用，如优先队列。 - **左偏树/平衡树**：用于快速查找和插入操作的自平衡搜索树。 - **pbds可并堆**：一种高效的数据结构，支持并查集操作。 - **伸展树/pbds伸展树**：用于高效处理动态维护的树形结构。 - **bitset**：位集合数据结构，适合存储和操作二进制信息。 - **可持久化线段树**：允许在不破坏已有数据的情况下进行多次更新和查询。 4. **动态规划**： - **斜率优化**：一种优化动态规划的方法，通过减少状态转移矩阵的计算。 - **有依赖的背包问题**：处理物品选择时考虑前后关系的背包问题。 - **最长公共上升子序列**：经典的动态规划问题，应用于序列分析。 5. **其他**： - **带修改的莫队算法**：一种可以处理插入和删除操作的特殊队列。 这份复习手册对于参加NOIP2017比赛的学生来说，提供了全面且深入的数学和算法基础，有助于理解和解决竞赛中遇到的相关问题。