算法訓(xùn)練營：提高篇（全彩版）

第1章 STL 1
1.1 deque（雙端隊(duì)列） 1
訓(xùn)練 度度熊學(xué)隊(duì)列 1
1.2 priority_queue（優(yōu)先隊(duì)列） 4
訓(xùn)練1 第k大的數(shù) 4
訓(xùn)練2 表演評(píng)分 6
1.3 bitset（位圖） 7
1.3.1 定義和初始化 8
1.3.2 基本操作 9
訓(xùn)練 集合運(yùn)算 10
1.4 set、multiset（集合、多重集合） 12
訓(xùn)練1 集合合并 13
訓(xùn)練2 并行處理 14
1.5 map、multimap（映射、多重映射） 16
訓(xùn)練1 硬木種類 18
訓(xùn)練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
訓(xùn)練1 中位數(shù) 25
訓(xùn)練2 字謎 26
第2章 實(shí)用的數(shù)據(jù)結(jié)構(gòu) 28
2.1 并查集 28
訓(xùn)練1 暢通工程 33
訓(xùn)練2 方塊棧 35
2.2 倍增、稀疏表（ST）、區(qū)間最值查詢（RMQ） 38
2.2.1 倍增 38
2.2.2 稀疏表 39
2.2.3 區(qū)間最值查詢 41
訓(xùn)練1 區(qū)間最值差 41
訓(xùn)練2 最頻繁值 42
2.3 最近公共祖先（LCA） 45
2.3.1 暴力搜索法 46
2.3.2 樹上倍增法 47
2.3.3 在線區(qū)間最值查詢算法 51
2.3.4 離線Tarjan算法 53
訓(xùn)練1 最近公共祖先 57
訓(xùn)練2 樹上距離 59
2.4 樹狀數(shù)組 61
2.4.1 一維樹狀數(shù)組 61
2.4.2 多維樹狀數(shù)組 67
訓(xùn)練1 數(shù)星星 68
訓(xùn)練2 矩形區(qū)域查詢 70
2.5 線段樹 71
2.5.1 基本操作 71
2.5.2 懶操作 76
訓(xùn)練1 敵兵布陣 80
訓(xùn)練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
訓(xùn)練 雪花 99
3.2 字符串模式匹配 100
3.2.1 BF算法 101
3.2.2 KMP算法 103
訓(xùn)練1 統(tǒng)計(jì)單詞數(shù) 109
訓(xùn)練2 字符串匹配 111
3.3 字典樹（Trie樹） 112
3.3.1 創(chuàng)建 113
3.3.2 查找 115
3.3.3 應(yīng)用 116
訓(xùn)練 單詞翻譯 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
訓(xùn)練 雙重隊(duì)列 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
訓(xùn)練 少林功夫 141
4.4 伸展樹（Splay樹） 144
4.4.1 時(shí)空局部性的原理 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
訓(xùn)練1 玩鏈子 152
訓(xùn)練2 超強(qiáng)記憶 159
第5章 圖論提高 169
5.1 連通圖與強(qiáng)連通圖 169
5.2 橋與割點(diǎn) 170
5.3 雙連通分量的縮點(diǎn) 171
5.4 Tarjan算法 172
5.4.1 無向圖的橋 173
5.4.2 無向圖的割點(diǎn) 174
5.4.3 有向圖的強(qiáng)連通分量 175
訓(xùn)練1 道路建設(shè) 177
訓(xùn)練2 校園網(wǎng)絡(luò) 180
第6章 圖論算法 183
6.1 最小生成樹 183
6.1.1 Prim算法 184
6.1.2 Kruskal算法 191
訓(xùn)練1 叢林之路 195
訓(xùn)練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
訓(xùn)練1 重型運(yùn)輸 211
訓(xùn)練2 貨幣兌換 212
訓(xùn)練3 蟲洞 214
6.3 拓?fù)渑判?216
訓(xùn)練1 家族樹 220
訓(xùn)練2 標(biāo)簽球 222
6.4 關(guān)鍵路徑 224
訓(xùn)練1 指令安排 232
訓(xùn)練2 家務(wù)瑣事 233
第7章 搜索算法提高 235
7.1 剪枝優(yōu)化 235
訓(xùn)練1 數(shù)獨(dú)游戲 235
訓(xùn)練2 小木棍 238
7.2 嵌套廣度優(yōu)先搜索 240
訓(xùn)練 推箱子 240
7.3 雙向廣度優(yōu)先搜索 244
訓(xùn)練 魔鬼Ⅱ 244
7.4 啟發(fā)式搜索 246
7.4.1 A*算法 247
7.4.2 IDA*算法 247
訓(xùn)練1 八數(shù)碼問題 248
訓(xùn)練2 第k短路徑 257
第8章 動(dòng)態(tài)規(guī)劃提高 260
8.1 樹形動(dòng)態(tài)規(guī)劃 260
訓(xùn)練1 戰(zhàn)略游戲 260
訓(xùn)練2 工人請(qǐng)?jiān)笗?262
8.2 狀態(tài)壓縮動(dòng)態(tài)規(guī)劃 264
訓(xùn)練1 旅行商問題 265
訓(xùn)練2 玉米田 269
8.3 動(dòng)態(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)隊(duì)列優(yōu)化 272
訓(xùn)練1 最長公共上升子序列 273
訓(xùn)練2 滑動(dòng)窗口 275