算法訓練營：提高篇（全彩版）

第1章 STL 1
1.1 deque（雙端隊列） 1
訓練 度度熊學隊列 1
1.2 priority_queue（優(yōu)先隊列） 4
訓練1 第k大的數(shù) 4
訓練2 表演評分 6
1.3 bitset（位圖） 7
1.3.1 定義和初始化 8
1.3.2 基本操作 9
訓練 集合運算 10
1.4 set、multiset（集合、多重集合） 12
訓練1 集合合并 13
訓練2 并行處理 14
1.5 map、multimap（映射、多重映射） 16
訓練1 硬木種類 18
訓練2 水果 19
1.6 STL中的常用函數(shù) 21
1.6.1 fill() 21
1.6.2 nth_element() 22
1.6.3 lower_bound()、upper_bound() 23
1.6.4 next_permutation()、pre_permutation() 23
訓練1 中位數(shù) 25
訓練2 字謎 26
第2章 實用的數(shù)據(jù)結(jié)構(gòu) 28
2.1 并查集 28
訓練1 暢通工程 33
訓練2 方塊棧 35
2.2 倍增、稀疏表（ST）、區(qū)間最值查詢（RMQ） 38
2.2.1 倍增 38
2.2.2 稀疏表 39
2.2.3 區(qū)間最值查詢 41
訓練1 區(qū)間最值差 41
訓練2 最頻繁值 42
2.3 最近公共祖先（LCA） 45
2.3.1 暴力搜索法 46
2.3.2 樹上倍增法 47
2.3.3 在線區(qū)間最值查詢算法 51
2.3.4 離線Tarjan算法 53
訓練1 最近公共祖先 57
訓練2 樹上距離 59
2.4 樹狀數(shù)組 61
2.4.1 一維樹狀數(shù)組 61
2.4.2 多維樹狀數(shù)組 67
訓練1 數(shù)星星 68
訓練2 矩形區(qū)域查詢 70
2.5 線段樹 71
2.5.1 基本操作 71
2.5.2 懶操作 76
訓練1 敵兵布陣 80
訓練2 簡單的整數(shù)問題 83
第3章 查找算法 85
3.1 散列表 85
3.1.1 散列函數(shù) 86
3.1.2 開放地址法 88
3.1.3 鏈地址法 96
3.1.4 建立公共溢出區(qū) 98
3.1.5 散列查找及其性能分析 98
訓練 雪花 99
3.2 字符串模式匹配 100
3.2.1 BF算法 101
3.2.2 KMP算法 103
訓練1 統(tǒng)計單詞數(shù) 109
訓練2 字符串匹配 111
3.3 字典樹（Trie樹） 112
3.3.1 創(chuàng)建 113
3.3.2 查找 115
3.3.3 應(yīng)用 116
訓練 單詞翻譯 116
第4章 平衡樹 118
4.1 樹高與性能 118
4.2 平衡二叉搜索樹（AVL樹） 119
4.2.1 調(diào)整平衡的方法 120
4.2.2 插入 122
4.2.3 創(chuàng)建 126
4.2.4 刪除 128
訓練 雙重隊列 131
4.3 樹堆（Treap） 134
4.3.1 右旋和左旋 135
4.3.2 插入 136
4.3.3 刪除 138
4.3.4 前驅(qū) 140
4.3.5 后繼 140
訓練 少林功夫 141
4.4 伸展樹（Splay樹） 144
4.4.1 時空局部性的原理 144
4.4.2 右旋和左旋 145
4.4.3 伸展 146
4.4.4 查找 149
4.4.5 插入 150
4.4.6 分裂 150
4.4.7 合并 150
4.4.8 刪除 151
4.4.9 區(qū)間操作 151
4.4.10 算法分析 152
訓練1 玩鏈子 152
訓練2 超強記憶 159
第5章 圖論提高 169
5.1 連通圖與強連通圖 169
5.2 橋與割點 170
5.3 雙連通分量的縮點 171
5.4 Tarjan算法 172
5.4.1 無向圖的橋 173
5.4.2 無向圖的割點 174
5.4.3 有向圖的強連通分量 175
訓練1 道路建設(shè) 177
訓練2 校園網(wǎng)絡(luò) 180
第6章 圖論算法 183
6.1 最小生成樹 183
6.1.1 Prim算法 184
6.1.2 Kruskal算法 191
訓練1 叢林之路 195
訓練2 聯(lián)網(wǎng) 197
6.2 最短路徑 199
6.2.1 Dijkstra算法 199
6.2.2 Floyd算法 204
6.2.3 Bellman-Ford算法 208
6.2.4 SPFA算法 209
訓練1 重型運輸 211
訓練2 貨幣兌換 212
訓練3 蟲洞 214
6.3 拓撲排序 216
訓練1 家族樹 220
訓練2 標簽球 222
6.4 關(guān)鍵路徑 224
訓練1 指令安排 232
訓練2 家務(wù)瑣事 233
第7章 搜索算法提高 235
7.1 剪枝優(yōu)化 235
訓練1 數(shù)獨游戲 235
訓練2 小木棍 238
7.2 嵌套廣度優(yōu)先搜索 240
訓練 推箱子 240
7.3 雙向廣度優(yōu)先搜索 244
訓練 魔鬼Ⅱ 244
7.4 啟發(fā)式搜索 246
7.4.1 A*算法 247
7.4.2 IDA*算法 247
訓練1 八數(shù)碼問題 248
訓練2 第k短路徑 257
第8章 動態(tài)規(guī)劃提高 260
8.1 樹形動態(tài)規(guī)劃 260
訓練1 戰(zhàn)略游戲 260
訓練2 工人請愿書 262
8.2 狀態(tài)壓縮動態(tài)規(guī)劃 264
訓練1 旅行商問題 265
訓練2 玉米田 269
8.3 動態(tài)規(guī)劃優(yōu)化 271
8.3.1 倍增優(yōu)化 272
8.3.2 數(shù)據(jù)結(jié)構(gòu)優(yōu)化 272
8.3.3 單調(diào)隊列優(yōu)化 272
訓練1 最長公共上升子序列 273
訓練2 滑動窗口 275