算法訓練營：海量圖解+競賽刷題（進階篇）

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

1.1  并查集... 1

原理  并查集詳解... 1

訓練1  暢通工程

訓練2  方塊棧... 7

訓練3  食物鏈... 10

訓練4  幫派... 16

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

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

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

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

訓練2  圍欄修復... 27

訓練3  表演評分... 29

訓練4  叢林探險

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

2.1  倍增、ST、RMQ.. 33

原理1  倍增... 33

原理2  ST. 34

原理3  RMQ.. 36

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

訓練2  最頻繁值... 37

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

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

2.2  最近公共祖先LCA.. 43

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

原理2  樹上倍增法... 45

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

原理4  Tarjan算法... 51

訓練1  最近公共祖先... 55

訓練2  樹上距離... 57

訓練3  距離查詢... 59

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

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

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

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

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

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

訓練3  子樹查詢... 74

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

2.4  線段樹... 78

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

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

訓練1  敵兵布陣... 87

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

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

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

2.5  分塊... 102

原理  分塊詳解... 102

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

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

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

訓練4  超級馬里奧... 109

訓練5  序列操作

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

3.1  字典樹... 115

原理  字典樹詳解... 115

訓練1  單詞翻譯... 120

訓練2  電話表... 122

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

訓練4  彩色的木棒... 124

訓練5  最長xor路徑... 127

3.2  AC自動機... 129

原理  AC自動機詳解... 129

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

訓練2  病毒侵襲... 134

訓練3  DNA序列... 136

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

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

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

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

訓練1  牛奶模式... 169

訓練2  口吃的外星人... 171

訓練3  音樂主題... 173

訓練4  星際迷航

第4章  樹上操作... 178

4.1  點分治... 178

原理  重心分解... 178

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

訓練2  游船之旅... 185

訓練3  摩天大樹... 189

訓練4  查詢子樹... 194

4.2  邊分治... 200

原理  邊分治詳解... 200

訓練1  樹上查詢I 203

訓練2  樹上查詢II 212

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

4.3  樹鏈剖分... 221

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

訓練1  樹上距離... 230

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

訓練3  家庭主婦... 232

訓練4  樹上操作... 233

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

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

訓練1  距離查詢... 247

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

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

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

訓練5  樹上操作

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

5.1  Treap. 263

原理  Treap詳解... 263

訓練1  雙重隊列... 270

訓練2  普通平衡樹... 272

訓練3  黑盒子... 276

訓練4  少林功夫... 279

5.2  伸展樹... 283

原理  伸展樹詳解... 283

訓練1  雙重隊列... 291

訓練2  玩鏈子... 293

訓練3  超強記憶... 300

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

5.3  SBT. 324

原理  SBT詳解... 324

訓練1  雙重隊列... 331

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

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

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

訓練5  郁悶的出納員

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

6.1  KD樹... 339

原理  KD樹詳解... 339

訓練1  最近的取款機... 343

訓練2  找旅館... 346

訓練3  最近鄰M點... 348

訓練4  蟻巢... 349

6.2  左偏樹... 352

原理  左偏樹詳解... 352

訓練1  猴王... 360

訓練2  小根堆... 363

訓練3  路面修整... 365

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

6.3  跳躍表... 373

原理  跳躍表詳解... 373

訓練1  雙重隊列... 379

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

訓練3  郁悶的出納員... 386

6.4  樹套樹... 388

原理  樹套樹詳解... 388

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

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

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

訓練4  馬賽克處理... 400

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

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

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

訓練1  超級馬里奧... 415

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

訓練3  最大異或和

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

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

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

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

7.2  背包問題... 433

原理1  01背包... 433

訓練1  骨頭收藏家... 441

原理2  完全背包... 443

訓練2  存錢罐... 443

原理3  多重背包... 445

訓練3  硬幣... 447

原理4  分組背包... 449

訓練4  價值最大化... 450

原理5  混合背包... 452

訓練5  最少的硬幣... 452

7.3  線性DP. 455

訓練1  超級樓梯... 455

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

訓練3  最長上升子序列... 458

訓練4  最長公共子序列... 461

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

7.4  區(qū)間DP. 464

訓練1  回文... 464

訓練2  括號匹配... 466

訓練3  猴子派對... 468

訓練4  乘法難題... 470

7.5  樹形DP. 472

訓練1  別墅派對... 473

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

訓練3  工人請愿書... 478

訓練4  完美的服務... 480

訓練5  背包類樹形DP. 484

訓練6  蘋果樹... 487

訓練7  二次掃描與換根... 490

訓練8  最遠距離... 494

7.6  數(shù)位DP. 497

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

訓練2  定時炸彈... 503

訓練3  Round Numbers. 506

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

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

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

訓練1  旅行商問題... 514

訓練2  旅行商變形1. 520

訓練3  旅行商變形2. 521

訓練4  玉米田... 523

訓練5  炮兵陣地... 525

訓練6  馬車旅行... 528

7.8  插頭DP. 531

訓練1  鋪磚... 531

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

訓練3  多回路連通性問題... 539

訓練4  單回路連通性問題... 543

訓練5  單通路連通性問題... 550

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

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

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

訓練1  最長公共上升子序列... 552

訓練2  有序子序列... 554

訓練3  最大化器... 557

訓練4  灑水裝置... 559

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

訓練5  滑動窗口... 563

訓練6  灑水裝置... 564

訓練7  股票交易... 565

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

訓練8  打印文章... 569

訓練9  覆蓋走道... 573

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

訓練11  劃分... 580

訓練12  勞倫斯... 583

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

訓練13  劃分

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

8.1  EK算法... 595

原理  EK算法詳解... 595

訓練1  最大流問題... 600

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

8.2  Dinic算法... 601

原理  Dinic算法詳解... 601

訓練1  最大銷售量... 605

訓練2  電力網(wǎng)絡.... 606

8.3  ISAP算法... 608

原理  ISAP算法詳解... 608

訓練1  島嶼運輸... 613

訓練2  美味佳肴... 614

訓練3  跳躍蜥蜴... 615

訓練4  計算機工廠... 618

8.4  二分圖匹配... 619

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

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

訓練1  完美的牛棚... 624

訓練2  機器調(diào)度... 625

訓練3  逃脫... 626

8.5  最大流最小割... 627

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

訓練1  最小邊割集... 629

訓練2  最小點割集... 631

訓練3  雙核CPU.. 632

訓練4  最大收益... 633

8.6  最小費用最大流... 635

原理  最小費用路算法... 635

訓練1  農(nóng)場之旅... 639

訓練2  航空路線... 640

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

訓練4  疏散計劃... 643