目录
目录
源码下载
第1章基础数据结构
1.1链表
1.1.1动态链表
1.1.2静态链表
1.1.3STL list
1.2队列
1.2.1STL queue
1.2.2手写循环队列
1.2.3双端队列和单调队列
1.2.4优先队列
1.3栈
1.3.1STL stack
1.3.2手写栈
1.3.3单调栈
1.4二叉树和哈夫曼树
1.4.1二叉树的概念
1.4.2二叉树的遍历
1.4.3哈夫曼树和哈夫曼编码
1.5堆
1.5.1二叉堆的概念
1.5.2二叉堆的操作
1.5.3二叉堆的手写代码
1.5.4堆和priority_queue
小结
第2章基本算法
2.1算法复杂度
2.1.1算法的概念
2.1.2复杂度和大O记号
2.2尺取法
2.2.1尺取法的概念
2.2.2反向扫描
2.2.3同向扫描
2.3二分法
2.3.1二分法的理论背景
2.3.2整数二分
2.3.3实数二分
2.4三分法
2.4.1原理
2.4.2实数三分
2.4.3整数三分
2.5倍增法与ST算法
2.5.1倍增法
2.5.2ST算法
2.6前缀和与差分
2.6.1一维差分
2.6.2二维差分
2.6.3三维差分
2.7离散化
2.7.1离散化的概念
2.7.2离散化手工编码
2.7.3用STL函数实现离散化
2.7.4离散化的应用
2.8排序与排列
2.8.1排序函数
2.8.2排列
2.9分治法
2.9.1汉诺塔和快速幂
2.9.2归并排序
2.9.3快速排序
2.10贪心法与拟阵
2.10.1贪心法
2.10.2拟阵
小结
第3章搜索
3.1BFS和DFS基础
3.1.1搜索简介
3.1.2搜索算法的基本思路
3.1.3BFS的代码实现
3.1.4DFS的常见操作和代码框架
3.1.5BFS和DFS的对比
3.1.6连通性判断
3.2剪枝
3.2.1BFS判重
3.2.2剪枝的应用
3.3洪水填充
3.4BFS与最短路径
3.5双向广搜
3.5.1双向广搜的原理和复杂度分析
3.5.2双向广搜的两种实现
3.5.3双向广搜例题
3.6BFS与优先队列
3.7BFS与双端队列
3.8A*算法
3.8.1贪心最优搜索和Dijkstra算法
3.8.2A*算法的原理和复杂度
3.8.33种算法的对比
3.8.4h函数的设计
3.8.5A*算法例题
3.9IDDFS和IDA*
3.9.1IDDFS
3.9.2IDA*
小结
第4章高级数据结构
4.1并查集
4.1.1并查集的基本操作
4.1.2合并的优化
4.1.3查询的优化(路径压缩)
4.1.4带权并查集
4.2树状数组
4.2.1树状数组的概念和基本编码
4.2.2树状数组的基本应用
4.2.3树状数组的扩展应用
4.3线段树
4.3.1线段树的概念
4.3.2区间查询
4.3.3区间操作与LazyTag
4.3.4线段树的基础应用
4.3.5区间最值和区间历史最值
4.3.6区间合并
4.3.7扫描线
4.3.8二维线段树(树套树)
4.4可持久化线段树
4.4.1可持久化线段树的思想
4.4.2区间第k大/小问题
4.4.3其他经典问题
4.5分块与莫队算法
4.5.1分块
4.5.2基础莫队算法
4.5.3带修改的莫队算法
4.5.4树上莫队
4.6块状链表
4.7简单树上问题
4.7.1树的重心
4.7.2树的直径
4.8LCA
4.8.1倍增法求LCA
4.8.2Tarjan算法求LCA
4.8.3LCA的应用
4.9树上的分治
4.9.1静态点分治
4.9.2动态点分治
4.10树链剖分
4.10.1树链剖分的概念与LCA
4.10.2树链剖分的典型应用
4.11二叉查找树
4.12替罪羊树
4.12.1不平衡率
4.12.2替罪羊树的操作
4.12.3例题
4.13Treap树
4.13.1Treap树的性质
4.13.2基于旋转法的Treap树操作
4.14FHQ Treap树
4.14.1FHQ的基本操作
4.14.2FHQ Treap树的应用
4.15笛卡儿树
4.15.1笛卡儿树的概念
4.15.2用单调栈建笛卡儿树
4.15.3笛卡儿树和RMQ问题
4.16Splay树
4.16.1Splay旋转
4.16.2Splay树的平摊分析
4.16.3Splay树的常用操作和代码
4.17KD树
4.17.1从空间到二叉树的转换
4.17.2KD树的概念和基本操作
4.17.3寻找最近点
4.17.4区间查询
4.18动态树与LCT
4.18.1LCT的思想
4.18.2从原树到辅助树
4.18.3LCT的存储和性质
4.18.4LCT的操作
4.18.5LCT的基本应用
小结
第5章动态规划
5.1DP概念和编程方法
5.1.1DP的概念
5.1.2DP的两种编程方法
5.1.3DP的设计和实现
5.1.4滚动数组
5.2经典线性DP问题
5.3数位统计DP
5.3.1数位统计DP的递推实现
5.3.2数位统计DP的记忆化搜索实现
5.3.3数位统计DP例题
5.4状态压缩DP
5.4.1引子
5.4.2状态压缩DP的原理
5.4.3状态压缩DP例题
5.4.4三进制状态压缩DP
5.5区间DP
5.5.1石子合并问题和两种模板代码
5.5.2区间DP例题
5.5.3二维区间DP
5.6树形DP
5.6.1树形DP的基本操作
5.6.2背包与树形DP
5.7一般优化
5.8单调队列优化
5.8.1单调队列优化的原理
5.8.2单调队列优化例题
5.9斜率优化/凸壳优化
5.9.1把状态转移方程变换为平面的斜率问题
5.9.2求一个dp[i]
5.9.3求所有dp[i]
5.9.4例题
5.10四边形不等式优化
5.10.1应用场合
5.10.2四边形不等式优化操作
5.10.3四边形不等式定义和单调性定义
5.10.4四边形不等式定理
5.10.5例题
小结
源码下载
第6章数论和线性代数
6.1模运算
6.2快速幂
6.3矩阵的应用
6.3.1矩阵的计算
6.3.2矩阵快速幂
6.3.3矩阵快速幂加速递推
6.3.4矩阵乘法与路径问题
6.4高斯消元
6.4.1高斯消元的基本操作
6.4.2高斯约当消元法
6.4.3例题
6.5异或空间线性基
6.5.1异或空间线性基的概念
6.5.2线性基的构造
6.5.3线性基的应用
6.60/1分数规划
6.6.1二分法与0/1分数规划
6.6.2应用场景
6.7GCD和LCM
6.7.1GCD
6.7.2LCM
6.7.3裴蜀定理
6.8线性丢番图方程
6.8.1二元线性丢番图方程
6.8.2扩展欧几里得算法与二元丢番图方程的解
6.8.3多元线性丢番图方程
6.9同余
6.9.1同余概述
6.9.2一元线性同余方程
6.9.3逆
6.9.4同余方程组
6.10素数(质数)
6.10.1小素数的判定
6.10.2大素数的判定
6.10.3素数筛
6.10.4质因数分解
6.11威尔逊定理
6.12积性函数
6.13欧拉函数
6.13.1欧拉函数的定义和性质
6.13.2求欧拉函数的通解公式
6.13.3用线性筛(欧拉筛)求1~n内的所有欧拉函数
6.14整除分块(数论分块)
6.15狄利克雷卷积
6.16莫比乌斯函数和莫比乌斯反演
6.17杜教筛
6.17.1杜教筛的起源
6.17.2杜教筛公式的推导
6.17.3杜教筛算法和复杂度
6.17.4杜教筛模板代码
小结
第7章组合数学
7.1基本概念
7.2鸽巢原理
7.3二项式定理和杨辉三角
7.4卢卡斯定理
7.5容斥原理
7.6Catalan数和Stirling数
7.6.1Catalan数
7.6.2Stirling数
7.7Burnside定理和Plya计数
7.7.1置换群
7.7.2Burnside定理
7.7.3Plya计数
7.8母函数
7.8.1普通型母函数
7.8.2指数型母函数
7.8.3母函数与泰勒级数
7.9公平组合游戏(博弈论)
7.9.1巴什游戏与Pposition、Nposition
7.9.2尼姆游戏
7.9.3图游戏与SpragueGrundy函数
7.9.4威佐夫游戏
小结
第8章计算几何
8.1二维几何
8.1.1点和向量
8.1.2点积和叉积
8.1.3点和线
8.1.4多边形
8.1.5凸包
8.1.6最近点对
8.1.7旋转卡壳
8.1.8半平面交
8.2圆
8.2.1基本的定义和计算
8.2.2最小圆覆盖
8.3三维几何
8.3.1三维点和线
8.3.2三维点积
8.3.3三维叉积
8.3.4最小球覆盖
8.3.5三维凸包
8.3.6三维几何例题
小结
第9章字符串
9.1进制哈希
9.1.1BKDRHash哈希函数
9.1.2进制哈希的应用
9.2Manacher
9.2.1暴力法求最长回文子串
9.2.2Manacher算法
9.2.3模板代码
9.3字典树
9.3.1字典树的构造
9.3.2模板代码
9.4回文树
9.4.1回文树的关键技术
9.4.2模板代码
9.5KMP
9.5.1朴素的模式匹配算法
9.5.2KMP算法
9.5.3模板代码和例题
9.5.4扩展KMP
9.6AC自动机
9.6.1AC自动机算法
9.6.2模板代码
9.7后缀树和后缀数组
9.7.1后缀树和后缀数组的概念
9.7.2倍增法求后缀数组
9.7.3后缀数组的经典应用
9.8后缀自动机
9.8.1后缀自动机的概念
9.8.2endpos和等价类
9.8.3后缀自动机的构造
9.8.4模板代码
9.8.5后缀自动机的应用
小结
第10章图论
10.1图的存储
10.1.1邻接矩阵
10.1.2邻接表
10.1.3链式前向星
10.2拓扑排序
10.2.1拓扑排序的概念
10.2.2基于BFS的拓扑排序
10.2.3基于DFS的拓扑排序
10.2.4输出拓扑排序
10.3欧拉路
10.3.1欧拉路和欧拉回路的存在性判断
10.3.2输出一个欧拉回路
10.4无向图的连通性
10.4.1割点和割边
10.4.2双连通分量
10.5有向图的连通性
10.5.1Kosaraju算法
10.5.2Tarjan算法
10.6基环树
10.72SAT
10.8最短路径
10.8.1FloydWarshall算法
10.8.2传递闭包
10.8.3Dijkstra算法
10.8.4BellmanFord算法
10.8.5SPFA
10.8.6比较BellmanFord算法和Dijkstra算法
10.8.7负环和差分约束系统
10.9最小生成树
10.9.1Kruskal算法
10.9.2Prim算法
10.9.3扩展问题
10.10最大流
10.10.1FordFulkerson方法
10.10.2EdmondsKarp算法
10.10.3Dinic算法
10.10.4ISAP算法
10.10.5混合图的欧拉回路
10.11二分图
10.12最小割
10.13费用流
小结
附录APython在竞赛中的应用
A.1大数计算
A.2构造测试数据和对拍
A.2.1构造随机数据
A.2.2数据去重
A.2.3对拍
A.3输入/输出
索引