信息學進階

第１章　深度優(yōu)先搜索的優(yōu)化       1
1.1　剪枝優(yōu)化          2
【知識講解】         2
【實踐鞏固】         5
1.2　迭代加深優(yōu)化          5
【知識講解】         5
【實踐鞏固】         9
第2 章　廣度搜索的優(yōu)化       11
2.1　雙向廣度優(yōu)先搜索      12
2.2　優(yōu)先隊列廣度優(yōu)先搜索      13
2.3　Hash 判重       15
第3 章　動態(tài)規(guī)劃進階      19
3.1　區(qū)間類動態(tài)規(guī)劃      20
3.2　樹形動態(tài)規(guī)劃        23
3.3　數(shù)位DP          27
3.3.1　數(shù)位DP 的基本思想      27
3.3.2 　數(shù)位DP 的應用     29
3.4　狀態(tài)壓縮DP          34
3.4.1　狀態(tài)壓縮DP 的基本思想    34
3.4.2　狀態(tài)壓縮DP 的應用      36
3.5 　單調(diào)隊列優(yōu)化       42
3.6　斜率優(yōu)化動態(tài)規(guī)劃      46
3.6.1　知識講解       46
3.6.2　實踐鞏固       50
第4 章　圖論      51
4.1　圖的基本概念        52
4.1.1　圖的一些定義和概念     52
4.1.2　圖的存儲結(jié)構         54
4.2　圖的遍歷        58
4.2.1　深度優(yōu)先遍歷和廣度優(yōu)先遍歷       58
4.2.2　一筆畫問題       60
4.3　短路徑算法        67
4.3.1　Bellman-Ford 算法的實現(xiàn)及運用       67
4.3.2　SPFA 算法的實現(xiàn)及運用     70
4.3.3　Dijkstra 算法的實現(xiàn)及運用     73
4.3.4　Floyd 算法的實現(xiàn)及運用     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 網(wǎng)         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 章　高級數(shù)據(jù)結(jié)構        111
6.1　并查集   112
6.2　樹狀數(shù)組      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　線段樹的區(qū)間查詢       134
6.5.4　區(qū)間修改和標記       139
6.6　平衡樹          144
6.6.1　二叉查找樹的基本思想與應用         144
6.6.2　Treap 的基本思想與應用       148
第7 章　數(shù)學基礎       153
7.1　GCD 與拓展GCD         154
7.1.1　公約數(shù)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