算法竞赛进阶指南

0x00基本算法本章知识点位运算补码表示法，理解C++无符号、有符号整数在计算机中的存储方式各种按位运算，包括取位、置位、移位等，以及一些常见技巧快速幂，64位整数乘法二进制状态压缩，使用二进制数对状态进行压缩、提取的方法枚举、模拟、递推能想象问题“状态空间”，理解各种基本算法其实是对状态空间的遍历与映射常见的枚举形式，无法设计有效算法时能够通过枚举的方式直接遍历状态空间通过模拟，主要侧重代码实现能力的训练递推边界、目标、递推公式的发现与设计一维、二维前缀和的递推与应用递归理解递归思想、子问题、递归边界、回溯时还原现场递归实现常见规模的状态空间的遍历分治思想，对问题进行划分、递归、再合并分形，主要练习对子问题的划分、提取、抽象递归的机器实现，转化成非递归的通用方法二分整数集合二分法、实数域二分法单峰函数的三分法二分答案，把求解转化为判定排序各种排序算法，插入/选择/冒泡/堆/归并/快速/计数/基数/桶排序离散化中位数相关问题，包括货仓选址、环形均分纸牌、动态维护中位数等求第𝑘大数的O(𝑁)算法逆序对相关问题，使用归并排序求逆序对倍增序列上的倍增算法及其应用RMQ-ST算法贪心贪心思想及其证明手段，主要通过较多题目开拓视野、归纳总结0x10基本数据结构本章知识点栈栈的基本实现，使用数组和栈顶位置变量模拟一个栈栈的灵活应用，例如使用辅助栈保存额外信息、对顶栈等表达式计算，后缀表达式、中缀转后缀、中缀表达式递归求值单调栈队列一般队列、双端队列、循环队列的基本实现单调队列，理解使用单调性处理问题的思想链表与邻接表双向链表的实现与操作，以及数组模拟链表邻接表结构，图和树的邻接表存储与遍历HashHash表，使用邻接表结构实现开散列法字符串Hash，前缀与区间Hash值、二分法的结合字符串KMP模式匹配算法，𝑛𝑒𝑥𝑡数组的灵活运用最小表示法，循环同构问题TrieTrie的插入、检索等基本操作Trie与xor问题二叉堆二叉堆的基本操作及其实现，Insert、GetTop、Extract、Remove等二叉堆的灵活应用，与贪心算法相结合，数据结构间“建立映射”的思想𝑘叉Huffman树与Huffman编码0x20搜索本章知识点树与图的遍历树与图的深度优先遍历，树的DFS序、深度、重心，图的连通块划分树与图的广度优先遍历，拓扑排序，bitset优化的可达性统计深度优先搜索深搜的三种基本递归形式，经典的子集和、全排列、N皇后问题等深搜框架的设计与实现，搜索树理论剪枝剪枝的设计思想与实现优化搜索顺序、排除等效冗余、可行性与最优性剪枝、记忆化等常见剪枝手法迭代加深迭代加深思想，迭代加深DFS（ID-DFS）双向搜索思想，双向DFS广度优先搜索广搜框架的设计与实现，熟练使用记录数组判重、方向常数数组等广搜的常见问题类型，如走地图、多起点BFS、双重BFS等广搜变形双端队列BFS，双向BFS优先队列BFS，理解并能根据每次扩展代价的实际情况选择正确的BFS形式A*估价函数的设计准则，估值f(state)≤未来实际代价g(state)A*算法的实现，A*=优先队列BFS+估价函数IDA*IDA*算法的实现，IDA*=迭代加深DFS+估价函数0x30数学知识本章知识点质数质数的判定，试除法质数的筛选，Eratosthenes筛法、线性筛法算术基本定理，试除法分解质因数约数算术基本定理的约数个数推论、约数和推论试除法求约数，倍数法求1~N每个数的约数集合最大公约数，最小公倍数，更相减损术，欧几里得算法欧拉函数的定义与基本性质，积性函数的定义与基本性质试除法计算欧拉函数，Eratosthenes筛法与线性筛法快速递推欧拉函数同余同余、同余类、剩余系的定义费马小定理，欧拉定理及其推论Bezout定理，扩展欧几里得算法乘法逆元的计算与应用线性同余方程、方程组的求解，中国剩余定理高次同余方程中指数的求解，BabyStep,GiantStep算法矩阵乘法矩阵乘法运算与基本性质矩阵乘法加速递推，状态矩阵、转移矩阵的构造方法高斯消元与线性空间系数矩阵、增广矩阵、主元、自由元、初等行变换等概念高斯消元的实现，方程组唯一解、多解、无解的判断线性空间的相关概念，高斯消元求线性空间的基线性空间的推广，异或空间的性质与应用，去重与不去重异或空间的形态组合计数加法原理，乘法原理，排列数，组合数及其性质组合数的递推求法、逆元求法、分解质因数约分求法二项式定理，Lucas定理多重集的排列数和组合数Catalan数列的定义和应用容斥原理与Möbius函数容斥原理的理解与应用多重集组合数的完整解析Mobius函数的定义、计算与应用概率与数学期望随机变量、概率、数学期望等相关定义数学期望的线性性质，数学期望的递推计算，数学期望与动态规划的结合0/1分数规划0/1分数规划模型与二分法求解博弈论之SG函数NIM游戏等简单博弈模型SG函数的计算与应用0x40数据结构进阶本章知识点并查集并查集的基本实现与应用，路径压缩并查集对传递性关系的维护，扩展域并查集，边带权并查集树状数组支持单点增加、区间和查询的树状数组支持区间增加、单点查询的树状数组支持区间增加、区间和查询的树状数组树状数组的应用，求逆序对、实时维护01序列中的第𝑘个1线段树支持单点修改、区间查询的线段树线段树延迟标记，支持区间修改、区间查询扫描线思想，线段树维护扫描线分块分块的“大段维护、局部朴素”思想两种常见的分块形式，在线求区间众数离线对询问进行分块的算法点分治点分治框架，以树的重心为根防止退化两种常见的子树统计方法：树上直接统计、指针扫描数组二叉查找树与平衡树初步BST的实现与基本操作平衡树初步：单旋转的概念，Treap的实现与基本操作，*Splay0x50动态规划本章知识点线性DP理解动态规划的“阶段”“状态”“决策”三要素应用动态规划的三个条件：“子问题重叠性”“最优子结构”“无后效性”能抽象出题目关键点作为状态，并选择覆盖整个状态空间的最小维度集合简单状态转移方程的设计与实现通过记录转移来源、递归输出的方法，求出动态规划算法的具体方案DP的初步优化：离散化、贪心、变量维护决策集合、前缀和预处理等方法背包了解0/1背包、完全背包、多重背包、分组背包模型在传统线性DP基础上省略“阶段”维度，控制循环顺序进行背包DP的手段多重背包的二进制拆分优化区间DP区间DP的状态设计区间DP的一般转移方式：枚举划分点DP的两种等价实现方式：递推（循环）与递归（记忆化搜索）线性DP中“区间”与树形结构中“子树”的联系树形DP树形DP的状态设计树形DP的实现方式：深度优先遍历背包类树形DP的实现方式：分组背包转移不定根的树形DP：二次扫描与换根法环形与后效性处理环形DP两种手段，两次DP（一次断开、一次强制连接）、环拆成链复制一倍高斯消元求解有后效性的状态转移方程状态压缩DP状态压缩DP的状态表示：集合型状态压缩为整数状态的方法，相关的位运算状态压缩DP的状态转移：一般转移、DFS转移、合法性判定倍增优化DP倍增优化DP的状态表示与转移方程设计倍增优化DP的实现：先用动态规划预处理，再用二进制拆分思想进行拼接数据结构优化DP用线段树、树状数组、二叉堆等，维护决策候选集合，优化DP的转移单调队列优化DP能够确定决策的取值范围并挖掘其单调性状态转移方程的变形，分开“只含状态变量”和“只含决策变量”的部分单调队列优化DP的程序实现框架单调队列的三种通用操作：检查队头合法性、取最优、队尾插入并维护单调性多重背包的单调队列优化算法斜率优化斜率优化与线性规划的联系，建立坐标系，使用斜率和截距分析凸壳形状单调队列维护凸壳的三种通用操作插入的坐标或待查询的斜率不具有单调性时的解决方法：二分、平衡树费用提前计算思想四边形不等式四边形不等式的定义和相关定理一维线性DP、二维区间DP的四边形不等式优化决策单调性证明、维护与实现计数类DP计数类DP“不重不漏”的基本原则，加法原理与乘法原理子问题互斥性，寻找“基准点”的思想，围绕基准点构造一个不可划分的整体数位统计DP数位统计问题的常见模型与求解方法：动态规划预处理、试填法0x60图论本章知识点最短路图的基本概念，图的邻接矩阵与邻接表存储单源最短路径问题，Dijkstra算法及堆优化，Bellman-Ford，SPFA算法单源最短路径各算法的适用范围，单源最短路径问题的变形与扩展任意两点间最短路径问题，Floyd算法的本质及应用传递闭包，无向图最小环问题最小生成树最小生成树的定义与基本性质，Kruskal算法，Prim算法最小生成树问题的变形与扩展树的直径与最近公共祖先树的直径的定义与计算：动态规划或两次BFS树的直径的性质与应用，尤其是直径的“最长性”LCA的定义与计算，向上标记法，树上倍增法，LCA的Tarjan算法LCA的扩展与应用：“树上差分算法”等树上倍增法的应用：“次小生成树”等基环树基环树、外向树、内向树的定义，基环树的处理方法负环与差分约束最短路中负环的判定方法差分约束系统的求解，差分约束到最短路的转化Tarjan算法与无向图连通性无向图的搜索树、时间戳与追溯值，割点与割边判定法则Tarjan算法求割点、割边、点双连通分量、边双连通分量双连通分量的性质与应用，缩点欧拉图的判定，欧拉路的计算Tarjan算法与有向图连通性有向图的搜索树、边的分类，Tarjan算法求强连通分量强连通分量的性质与应用，缩点有向无环图的必经点与必经边，路径条数取模法2-SAT问题的判定，自底向上拓扑排序构造方案二分图的匹配二分图的判定：染色法判断是否存在奇环二分图最大匹配：匈牙利（增广路）算法二分图匹配的模型构建方法，“0要素”与“1要素”，二分图多重匹配二分图带权最大匹配：KM算法二分图的覆盖与独立集二分图最小点覆盖，模型构建的“2要素”二分图最大独立集，“团”与独立集的对应关系，补图转化思想有向无环图的最小路径点覆盖、最小路径可重复点覆盖网络流初步网络流的定义，“容量限制”“斜对称”“流量守恒”三条基本定律最大流的Edmonds-Karp增广路算法与Dinic算法网络流求解二分图匹配的方法，二分图最大匹配的必须边、可行边判定最小割的定义，最大流最小割定理，“点边转化”技巧费用流的Edmonds-Karp增广路算法及其应用