跳到主要内容

2024/04/程序设计竞赛_进阶篇

· 阅读需 26 分钟

第一章 常见优化技巧​

1.1 双指针法​

1.2 空间换时间​

1.3 单调栈​

1.4 单调队列​

1.5 额外加练​

第二章 前缀和、差分与离散化​

2.1 前缀和与二维前缀和​

2.2 差分​

2.3 离散化​

2.4 额外加练​

第三章 分治与倍增​

3.1 归并排序与快速幂​

3.2 其它序列上的分治​

3.3 倍增与ST表​

3.4 额外练习​

第四章 进阶搜索​

4.1 状态剪枝​

4.2 迭代加深与双向搜索​

4.3 启发式搜索​

4.4 额外加练​

第五章 二叉堆​

5.1 二叉堆的实现​

5.2 优先队列​

5.3 额外练习​

第六章 线段树​

6.1 线段树的建立与操作​

6.2 线段树的应用​

6.3 权值线段树​

6.4 额外加练​

第七章 树状数组与字典树​

7.1 树状数组​

7.2 字典树​

7.3 额外加练​

第八章 线段树的进阶用法​

8.1 可持久化线段树​

8.2 树状数组套权值线段树​

8.3 额外加练​

第九章 树​

9.1 树的性质与遍历​

9.2 树的直径与重心​

9.3 最近公共祖先​

9.4 额外加练​

第十章 最短路​

10.1 单源最短路径​

10.2 负环与差分约束​

10.3 次短路​

10.4 多源最短路径与传递背包​

10.5 额外加练​

第十一章 最小生成树​

11.1 最小生成树及其应用​

11.2 次小生成树​

11.3 额外加练​

第十二章 连通性问题​

12.1 无向图的边双连通性​

12.2 无向图的点双连通性​

12.3 有向图的强连通性​

12.4 额外加练​

第十三章 动态规划的引入​

13.1 什么是动态规划​

13.2 状态、转移与有向无环图​

13.3 拓扑序与记忆化搜索​

13.4 动态规划的解法​

13.5 额外加练​

第十四章 线性状态动态规划​

14.1 单序列问题​

14.2 多序列问题​

14.3 高维问题​

14.4 额外加练​

第十五章 区间与环形动态规划​

15.1 区间动态规划​

15.2 环形动态规划​

15.3 额外加练​

第十六章 树与图上的动态规划​

16.1 树上动态规划​

16.2 图上动态规划​

16.3 额外加练​

第十七章 状态压缩动态规划​

17.1 状态压缩是什么​

17.2 状态压缩的一般技巧​

17.3 状态压缩与其他算法的交叉应用​

17.4 额外加练​

第十八章 动态规划的设计与优化​

18.1 如何优化转移​

18.2 额外加练​

第十九章 进阶数论​

19.1 模意义下的数和运算​

19.2 乘法逆元​

19.3 同余方程与中国剩余定理​

19.4 线性筛与积性函数​

19.5 欧拉函数​

19.6 额外加练​

第二十章 组合数学与计数​

20.1 集合与容斥原理​

20.2 常见的组合计数方法​

20.3 二项式定理​

20.4 卡特兰数与斯特林数​

20.5 额外加练​

第二十一章 概率与统计​

21.1 概率模型​

21.2 数学期望​

21.3 额外加练​

第二十二章 基础线性代数​

22.1 向量与矩阵变换​

22.2 高斯消元​

22.3 额外加练​