信息学进阶

第１章　深度优先搜索的优化       1
1.1　剪枝优化          2
【知识讲解】         2
【实践巩固】         5
1.2　迭代加深优化          5
【知识讲解】         5
【实践巩固】         9
第2 章　广度搜索的优化       11
2.1　双向广度优先搜索      12
2.2　优先队列广度优先搜索      13
2.3　Hash 判重       15
第3 章　动态规划进阶      19
3.1　区间类动态规划      20
3.2　树形动态规划        23
3.3　数位DP          27
3.3.1　数位DP 的基本思想      27
3.3.2 　数位DP 的应用     29
3.4　状态压缩DP          34
3.4.1　状态压缩DP 的基本思想    34
3.4.2　状态压缩DP 的应用      36
3.5 　单调队列优化       42
3.6　斜率优化动态规划      46
3.6.1　知识讲解       46
3.6.2　实践巩固       50
第4 章　图论      51
4.1　图的基本概念        52
4.1.1　图的一些定义和概念     52
4.1.2　图的存储结构         54
4.2　图的遍历        58
4.2.1　深度优先遍历和广度优先遍历       58
4.2.2　一笔画问题       60
4.3　短路径算法        67
4.3.1　Bellman-Ford 算法的实现及运用       67
4.3.2　SPFA 算法的实现及运用     70
4.3.3　Dijkstra 算法的实现及运用     73
4.3.4　Floyd 算法的实现及运用     75
4.4　图的连通性        77
4.4.1　无向图的割点与桥         77
4.4.2　无向图的双连通分量     80
4.4.3　有向图的强连通分量     81
4.5　小生成树        83
4.5.1　Prim 算法      83
4.5.2　Kruskal 算法       84
4.6　拓扑排序与关键路径      86
4.6.1　AOV 网         86
4.6.2　拓扑排序算法的基本思想
与应用           87
4.6.3　关键路径       89
第5 章　字符串算法      93
5.1　哈希和哈希表        94
5.2　KMP 算法      97
5.3　Trie 字典树           104
5.3.1　Trie 字典树的思想       104
5.3.2　Trie 字典树的应用       106
第6 章　高级数据结构        111
6.1　并查集   112
6.2　树状数组      115
6.3　RMQ      118
6.4　快速幂与矩阵乘法        122
6.4.1　快速幂         122
6.4.2　矩阵乘法       124
6.4.3　LCA         126
6.5　线段树          131
6.5.1　线段树的基本思想       131
6.5.2　线段树的单点修改       133
6.5.3　线段树的区间查询       134
6.5.4　区间修改和标记       139
6.6　平衡树          144
6.6.1　二叉查找树的基本思想与应用         144
6.6.2　Treap 的基本思想与应用       148
第7 章　数学基础       153
7.1　GCD 与拓展GCD         154
7.1.1　公约数GCD 的求法       154
7.1.2　扩展欧几里得算法的基本思想与应用       158
7.2　同余定理      164
7.2.1　同余定理概述       164
7.2.2　线性同余方程的求解     167
7.3　逆元问题      168
7.3.1　逆元问题的求解       168
7.3.2　逆元的应用       171
7.4　容斥原理      174