算法訓(xùn)練營：海量圖解+競賽刷題（進(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)先隊列... 19

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

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

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

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

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

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

第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  樹上倍增法... 45

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

原理4  Tarjan算法... 51

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

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

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

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

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

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

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

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

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

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

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

2.4  線段樹... 78

原理1  線段樹的基本操作... 78

原理2  線段樹中的“懶操作”... 83

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

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

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

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

2.5  分塊... 102

原理  分塊詳解... 102

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

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

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

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

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

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

3.1  字典樹... 115

原理  字典樹詳解... 115

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

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

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

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

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

3.2  AC自動機(jī)... 129

原理  AC自動機(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  音樂主題... 173

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

第4章  樹上操作... 178

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

原理  重心分解... 178

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

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

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

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

4.2  邊分治... 200

原理  邊分治詳解... 200

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

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

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

4.3  樹鏈剖分... 221

原理  樹鏈剖分詳解... 221

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

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

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

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

4.4  動態(tài)樹... 236

原理  動態(tài)樹詳解... 236

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

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

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

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

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

第5章  平衡二叉樹... 263

5.1  Treap. 263

原理  Treap詳解... 263

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

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

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

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

5.2  伸展樹... 283

原理  伸展樹詳解... 283

訓(xùn)練1  雙重隊列... 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  雙重隊列... 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樹... 339

原理  KD樹詳解... 339

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

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

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

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

6.2  左偏樹... 352

原理  左偏樹詳解... 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  雙重隊列... 379

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

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

6.4  樹套樹... 388

原理  樹套樹詳解... 388

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

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

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

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

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

原理1  可持久化線段樹詳解... 406

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

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

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

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

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

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

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

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

7.2  背包問題... 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  價值最大化... 450

原理5  混合背包... 452

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

7.3  線性DP. 455

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

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

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

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

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

7.4  區(qū)間DP. 464

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

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

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

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

7.5  樹形DP. 472

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

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

訓(xùn)練3  工人請愿書... 478

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

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

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

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

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

7.6  數(shù)位DP. 497

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

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

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

訓(xùn)練4  計數(shù)問題... 508

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

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

訓(xùn)練1  旅行商問題... 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  多回路連通性問題... 539

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

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

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

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

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

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

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

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

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

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

訓(xùn)練5  滑動窗口... 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  最大流問題... 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ī)工廠... 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)場之旅... 639

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

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

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