算法訓(xùn)練營(yíng)：海量圖解+競(jìng)賽刷題（進(jìn)階篇）

第1章  實(shí)用數(shù)據(jù)結(jié)構(gòu)... 1

1.1  并查集... 1

原理  并查集詳解... 1

訓(xùn)練1  暢通工程

訓(xùn)練2  方塊棧... 7

訓(xùn)練3  食物鏈... 10

訓(xùn)練4  幫派... 16

1.2  優(yōu)先隊(duì)列... 19

原理1  優(yōu)先隊(duì)列的實(shí)現(xiàn)原理... 19

原理2  優(yōu)先隊(duì)列詳解... 23

訓(xùn)練1  第k大的數(shù)... 26

訓(xùn)練2  圍欄修復(fù)... 27

訓(xùn)練3  表演評(píng)分... 29

訓(xùn)練4  叢林探險(xiǎn)

第2章  區(qū)間信息維護(hù)與查詢... 33

2.1  倍增、ST、RMQ.. 33

原理1  倍增... 33

原理2  ST. 34

原理3  RMQ.. 36

訓(xùn)練1  區(qū)間最值差... 36

訓(xùn)練2  最頻繁值... 37

訓(xùn)練3  最小分段數(shù)... 40

訓(xùn)練4  二維區(qū)間最值差.... 41

2.2  最近公共祖先LCA.. 43

原理1  暴力搜索法... 44

原理2  樹(shù)上倍增法... 45

原理3  在線RMQ算法... 49

原理4  Tarjan算法... 51

訓(xùn)練1  最近公共祖先... 55

訓(xùn)練2  樹(shù)上距離... 57

訓(xùn)練3  距離查詢... 59

訓(xùn)練4  城市之間的聯(lián)系... 60

2.3  樹(shù)狀數(shù)組... 62

原理1  一維樹(shù)狀數(shù)組... 62

原理2  多維樹(shù)狀數(shù)組... 67

訓(xùn)練1  數(shù)星星... 69

訓(xùn)練2  公路交叉數(shù)... 71

訓(xùn)練3  子樹(shù)查詢... 74

訓(xùn)練4  矩形區(qū)域查詢... 76

2.4  線段樹(shù)... 78

原理1  線段樹(shù)的基本操作... 78

原理2  線段樹(shù)中的“懶操作”... 83

訓(xùn)練1  敵兵布陣... 87

訓(xùn)練2  簡(jiǎn)單的整數(shù)問(wèn)題... 89

訓(xùn)練3  數(shù)據(jù)結(jié)構(gòu)難題... 91

訓(xùn)練4  顏色統(tǒng)計(jì)... 97

2.5  分塊... 102

原理  分塊詳解... 102

訓(xùn)練1  簡(jiǎn)單的整數(shù)問(wèn)題... 105

訓(xùn)練2  數(shù)字序列... 106

訓(xùn)練3  區(qū)間最值差... 107

訓(xùn)練4  超級(jí)馬里奧... 109

訓(xùn)練5  序列操作

第3章  字符串處理... 115

3.1  字典樹(shù)... 115

原理  字典樹(shù)詳解... 115

訓(xùn)練1  單詞翻譯... 120

訓(xùn)練2  電話表... 122

訓(xùn)練3  統(tǒng)計(jì)難題... 123

訓(xùn)練4  彩色的木棒... 124

訓(xùn)練5  最長(zhǎng)xor路徑... 127

3.2  AC自動(dòng)機(jī)... 129

原理  AC自動(dòng)機(jī)詳解... 129

訓(xùn)練1  關(guān)鍵字檢索... 132

訓(xùn)練2  病毒侵襲... 134

訓(xùn)練3  DNA序列... 136

訓(xùn)練4  單詞情結(jié)... 140

3.3  后綴數(shù)組... 145

原理1  基數(shù)排序... 145

原理2  后綴數(shù)組詳解... 152

訓(xùn)練1  牛奶模式... 169

訓(xùn)練2  口吃的外星人... 171

訓(xùn)練3  音樂(lè)主題... 173

訓(xùn)練4  星際迷航

第4章  樹(shù)上操作... 178

4.1  點(diǎn)分治... 178

原理  重心分解... 178

訓(xùn)練1  樹(shù)上兩點(diǎn)之間的路徑數(shù)... 179

訓(xùn)練2  游船之旅... 185

訓(xùn)練3  摩天大樹(shù)... 189

訓(xùn)練4  查詢子樹(shù)... 194

4.2  邊分治... 200

原理  邊分治詳解... 200

訓(xùn)練1  樹(shù)上查詢I 203

訓(xùn)練2  樹(shù)上查詢II 212

訓(xùn)練3  樹(shù)上兩點(diǎn)之間的路徑數(shù)... 217

4.3  樹(shù)鏈剖分... 221

原理  樹(shù)鏈剖分詳解... 221

訓(xùn)練1  樹(shù)上距離... 230

訓(xùn)練2  樹(shù)的統(tǒng)計(jì)... 231

訓(xùn)練3  家庭主婦... 232

訓(xùn)練4  樹(shù)上操作... 233

4.4  動(dòng)態(tài)樹(shù)... 236

原理  動(dòng)態(tài)樹(shù)詳解... 236

訓(xùn)練1  距離查詢... 247

訓(xùn)練2  動(dòng)態(tài)樹(shù)xor和... 249

訓(xùn)練3  動(dòng)態(tài)樹(shù)的最值... 252

訓(xùn)練4  動(dòng)態(tài)樹(shù)的第2大值... 255

訓(xùn)練5  樹(shù)上操作

第5章  平衡二叉樹(shù)... 263

5.1  Treap. 263

原理  Treap詳解... 263

訓(xùn)練1  雙重隊(duì)列... 270

訓(xùn)練2  普通平衡樹(shù)... 272

訓(xùn)練3  黑盒子... 276

訓(xùn)練4  少林功夫... 279

5.2  伸展樹(shù)... 283

原理  伸展樹(shù)詳解... 283

訓(xùn)練1  雙重隊(duì)列... 291

訓(xùn)練2  玩鏈子... 293

訓(xùn)練3  超強(qiáng)記憶... 300

訓(xùn)練4  循環(huán)... 310

5.3  SBT. 324

原理  SBT詳解... 324

訓(xùn)練1  雙重隊(duì)列... 331

訓(xùn)練2  第k小的數(shù)... 333

訓(xùn)練3  第k大的數(shù)... 334

訓(xùn)練4  區(qū)間第k小... 334

訓(xùn)練5  郁悶的出納員

第6章  數(shù)據(jù)結(jié)構(gòu)進(jìn)階... 339

6.1  KD樹(shù)... 339

原理  KD樹(shù)詳解... 339

訓(xùn)練1  最近的取款機(jī)... 343

訓(xùn)練2  找旅館... 346

訓(xùn)練3  最近鄰M點(diǎn)... 348

訓(xùn)練4  蟻巢... 349

6.2  左偏樹(shù)... 352

原理  左偏樹(shù)詳解... 352

訓(xùn)練1  猴王... 360

訓(xùn)練2  小根堆... 363

訓(xùn)練3  路面修整... 365

訓(xùn)練4  K-單調(diào)... 369

6.3  跳躍表... 373

原理  跳躍表詳解... 373

訓(xùn)練1  雙重隊(duì)列... 379

訓(xùn)練2  第k大的數(shù)... 381

訓(xùn)練3  郁悶的出納員... 386

6.4  樹(shù)套樹(shù)... 388

原理  樹(shù)套樹(shù)詳解... 388

訓(xùn)練1  動(dòng)態(tài)區(qū)間問(wèn)題... 389

訓(xùn)練2  動(dòng)態(tài)區(qū)間第k小... 395

訓(xùn)練3  矩形區(qū)域查詢... 396

訓(xùn)練4  馬賽克處理... 400

6.5  可持久化數(shù)據(jù)結(jié)構(gòu)... 406

原理1  可持久化線段樹(shù)詳解... 406

原理2  可持久化Trie詳解... 413

訓(xùn)練1  超級(jí)馬里奧... 415

訓(xùn)練2  記憶重現(xiàn)... 419

訓(xùn)練3  最大異或和

第7章  動(dòng)態(tài)規(guī)劃及其優(yōu)化... 431

7.1  動(dòng)態(tài)規(guī)劃求解原理... 431

原理1  動(dòng)態(tài)規(guī)劃的三個(gè)要素... 432

原理2  動(dòng)態(tài)規(guī)劃設(shè)計(jì)方法... 432

7.2  背包問(wèn)題... 433

原理1  01背包... 433

訓(xùn)練1  骨頭收藏家... 441

原理2  完全背包... 443

訓(xùn)練2  存錢罐... 443

原理3  多重背包... 445

訓(xùn)練3  硬幣... 447

原理4  分組背包... 449

訓(xùn)練4  價(jià)值最大化... 450

原理5  混合背包... 452

訓(xùn)練5  最少的硬幣... 452

7.3  線性DP. 455

訓(xùn)練1  超級(jí)樓梯... 455

訓(xùn)練2  數(shù)字三角形... 456

訓(xùn)練3  最長(zhǎng)上升子序列... 458

訓(xùn)練4  最長(zhǎng)公共子序列... 461

訓(xùn)練5  最大連續(xù)子段和... 462

7.4  區(qū)間DP. 464

訓(xùn)練1  回文... 464

訓(xùn)練2  括號(hào)匹配... 466

訓(xùn)練3  猴子派對(duì)... 468

訓(xùn)練4  乘法難題... 470

7.5  樹(shù)形DP. 472

訓(xùn)練1  別墅派對(duì)... 473

訓(xùn)練2  戰(zhàn)略游戲... 476

訓(xùn)練3  工人請(qǐng)?jiān)笗?shū)... 478

訓(xùn)練4  完美的服務(wù)... 480

訓(xùn)練5  背包類樹(shù)形DP. 484

訓(xùn)練6  蘋果樹(shù)... 487

訓(xùn)練7  二次掃描與換根... 490

訓(xùn)練8  最遠(yuǎn)距離... 494

7.6  數(shù)位DP. 497

訓(xùn)練1  不吉利的數(shù)字... 498

訓(xùn)練2  定時(shí)炸彈... 503

訓(xùn)練3  Round Numbers. 506

訓(xùn)練4  計(jì)數(shù)問(wèn)題... 508

訓(xùn)練5  數(shù)字權(quán)值... 511

7.7  狀態(tài)壓縮DP. 513

訓(xùn)練1  旅行商問(wèn)題... 514

訓(xùn)練2  旅行商變形1. 520

訓(xùn)練3  旅行商變形2. 521

訓(xùn)練4  玉米田... 523

訓(xùn)練5  炮兵陣地... 525

訓(xùn)練6  馬車旅行... 528

7.8  插頭DP. 531

訓(xùn)練1  鋪磚... 531

訓(xùn)練2  方格取數(shù)... 537

訓(xùn)練3  多回路連通性問(wèn)題... 539

訓(xùn)練4  單回路連通性問(wèn)題... 543

訓(xùn)練5  單通路連通性問(wèn)題... 550

7.9  動(dòng)態(tài)規(guī)劃優(yōu)化... 552

原理1  倍增優(yōu)化... 552

原理2  數(shù)據(jù)結(jié)構(gòu)優(yōu)化... 552

訓(xùn)練1  最長(zhǎng)公共上升子序列... 552

訓(xùn)練2  有序子序列... 554

訓(xùn)練3  最大化器... 557

訓(xùn)練4  灑水裝置... 559

原理3  單調(diào)隊(duì)列優(yōu)化... 562

訓(xùn)練5  滑動(dòng)窗口... 563

訓(xùn)練6  灑水裝置... 564

訓(xùn)練7  股票交易... 565

原理4  斜率優(yōu)化... 568

訓(xùn)練8  打印文章... 569

訓(xùn)練9  覆蓋走道... 573

訓(xùn)練10  批處理調(diào)度... 575

訓(xùn)練11  劃分... 580

訓(xùn)練12  勞倫斯... 583

原理5  四邊不等式優(yōu)化... 587

訓(xùn)練13  劃分

第8章  網(wǎng)絡(luò)流... 592

8.1  EK算法... 595

原理  EK算法詳解... 595

訓(xùn)練1  最大流問(wèn)題... 600

訓(xùn)練2  排水系統(tǒng)... 600

8.2  Dinic算法... 601

原理  Dinic算法詳解... 601

訓(xùn)練1  最大銷售量... 605

訓(xùn)練2  電力網(wǎng)絡(luò).... 606

8.3  ISAP算法... 608

原理  ISAP算法詳解... 608

訓(xùn)練1  島嶼運(yùn)輸... 613

訓(xùn)練2  美味佳肴... 614

訓(xùn)練3  跳躍蜥蜴... 615

訓(xùn)練4  計(jì)算機(jī)工廠... 618

8.4  二分圖匹配... 619

原理1  最大匹配算法... 620

原理2  匈牙利算法... 621

訓(xùn)練1  完美的牛棚... 624

訓(xùn)練2  機(jī)器調(diào)度... 625

訓(xùn)練3  逃脫... 626

8.5  最大流最小割... 627

原理  最大流最小割定理... 627

訓(xùn)練1  最小邊割集... 629

訓(xùn)練2  最小點(diǎn)割集... 631

訓(xùn)練3  雙核CPU.. 632

訓(xùn)練4  最大收益... 633

8.6  最小費(fèi)用最大流... 635

原理  最小費(fèi)用路算法... 635

訓(xùn)練1  農(nóng)場(chǎng)之旅... 639

訓(xùn)練2  航空路線... 640

訓(xùn)練3  區(qū)間覆蓋... 642

訓(xùn)練4  疏散計(jì)劃... 643