0x00 基本算法 位运算补码表示法, 理解 C++ 无符号 有符号整数在计算机中的存储方式各种按位运算, 包括取位 置位 移位等, 以及一些常见技巧快速幂,64 位整数乘法二进制状态压缩, 使用二进制数对状态进行压缩 提取的方法枚举 模拟 递推能想象问题 状态空间, 理解各种基本算法其实是对状态空间的遍历与映射常见的枚举形式, 无法设计有效算法时能够通过枚举的方式直接遍历状态空间通过模拟, 主要侧重代码实现能力的训练递推边界 目标 递推公式的发现与设计一维 二维前缀和的递推与应用递归理解递归思想 子问题 递归边界 回溯时还原现场递归实现常见规模的状态空间的遍历分治思想, 对问题进行划分 递归 再合并分形, 主要练习对子问题的划分 提取 抽象递归的机器实现, 转化成非递归的通用方法二分整数集合二分法 实数域二分法单峰函数的三分法二分答案, 把求解转化为判定排序各种排序算法, 插入 / 选择 / 冒泡 / 堆 / 归并 / 快速 / 计数 / 基数 / 桶排序离散化中位数相关问题, 包括货仓选址 环形均分纸牌 动态维护中位数等求第 k 大数的 O(N) 算法逆序对相关问题, 使用归并排序求逆序对
倍增序列上的倍增算法及其应用 RMQ-ST 算法贪心贪心思想及其证明手段, 主要通过较多题目开拓视野 归纳总结 0x10 基本数据结构 栈栈的基本实现, 使用数组和栈顶位置变量模拟一个栈栈的灵活应用, 例如使用辅助栈保存额外信息 对顶栈等表达式计算, 后缀表达式 中缀转后缀 中缀表达式递归求值单调栈队列一般队列 双端队列 循环队列的基本实现单调队列, 理解使用单调性处理问题的思想链表与邻接表双向链表的实现与操作, 以及数组模拟链表邻接表结构, 图和树的邻接表存储与遍历 Hash Hash 表, 使用邻接表结构实现开散列法字符串 Hash, 前缀与区间 Hash 值 二分法的结合 字符串 KMP 模式匹配算法,next 数组的灵活运用最小表示法, 循环同构问题 Trie
Trie 的插入 检索等基本操作 Trie 与 xor 问题二叉堆二叉堆的基本操作及其实现,Insert GetTop Extract Remove 等二叉堆的灵活应用, 与贪心算法相结合, 数据结构间 建立映射 的思想 k 叉 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 筛法与线性筛法快速递推欧拉函数同余同余 同余类 剩余系的定义费马小定理, 欧拉定理及其推论 Be zout 定理, 扩展欧几里得算法乘法逆元的计算与应用线性同余方程 方程组的求解, 中国剩余定理高次同余方程中指数的求解,Baby Step, Giant Step 算法矩阵乘法矩阵乘法运算与基本性质矩阵乘法加速递推, 状态矩阵 转移矩阵的构造方法
高斯消元与线性空间系数矩阵 增广矩阵 主元 自由元 初等行变换等概念高斯消元的实现, 方程组唯一解 多解 无解的判断线性空间的相关概念, 高斯消元求线性空间的基线性空间的推广, 异或空间的性质与应用, 去重与不去重异或空间的形态组合计数加法原理, 乘法原理, 排列数, 组合数及其性质组合数的递推求法 逆元求法 分解质因数约分求法二项式定理,Lucas 定理多重集的排列数和组合数 Catalan 数列的定义和应用容斥原理与 Möbius 函数容斥原理的理解与应用多重集组合数的完整解析 Mo bius 函数的定义 计算与应用概率与数学期望随机变量 概率 数学期望等相关定义数学期望的线性性质, 数学期望的递推计算, 数学期望与动态规划的结合 0/1 分数规划 0/1 分数规划模型与二分法求解博弈论之 SG 函数 NIM 游戏等简单博弈模型 SG 函数的计算与应用 0x40 数据结构进阶 并查集 并查集的基本实现与应用, 路径压缩
并查集对传递性关系的维护, 扩展域并查集, 边带权并查集树状数组支持单点增加 区间和查询的树状数组支持区间增加 单点查询的树状数组支持区间增加 区间和查询的树状数组树状数组的应用, 求逆序对 实时维护 01 序列中的第 k 个 1 线段树支持单点修改 区间查询的线段树线段树延迟标记, 支持区间修改 区间查询扫描线思想, 线段树维护扫描线分块分块的 大段维护 局部朴素 思想两种常见的分块形式, 在线求区间众数离线对询问进行分块的算法点分治点分治框架, 以树的重心为根防止退化两种常见的子树统计方法 : 树上直接统计 指针扫描数组二叉查找树与平衡树初步 BST 的实现与基本操作平衡树初步 : 单旋转的概念,Treap 的实现与基本操作,*Splay 0x50 动态规划 线性 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 增广路算法及其应用