第一部分 開始解決問題
第1 章 解決問題與程序設計競賽 4
1.1 引言 4
1.2 程序設計競賽 4
1.3 閱讀本書的方法 7
1.4 值得參加的程序設計競賽 8
1.5 對賽前準備工作的一些建議 9
1.6 續讀 12
第2 章 解決問題概述 13
2.1 引言 13
2.2 解決問題的過程 13
2.3 解決問題的策略 17
2.4 續讀 26
第3 章 編碼與調試 27
3.1 引言：不要忽視編碼的重要性 27
3.2 編寫優秀代碼的原則 27
3.3 常見失誤 32
3.4 調試與測試 39
3.5 變量的取值範圍 42
3.6 理解實數型數據類型 46
3.7 續讀 55
第二部分 算法分析
第4 章 分析算法的時間復雜度 60
4.1 引言 60
4.2 綫性時間算法 62
4.3 次綫性時間算法 65
4.4 指數時間算法 67
4.5 時間復雜度 70
4.6 推測執行時間 76
4.7 計算復雜度類：P、NP、NP-完備 81
4.8 續讀 84
第5 章 算法正確性證明 85
5.1 引言 85
5.2 數學歸納法和循環不變式 86
5.3 歸謬法 90
5.4 其他技巧 92
5.5 續讀 95
第三部分 算法設計範式
第6 章 暴力解決法 99
6.1 引言 99
6.2 遞歸調用和窮舉搜索法 100
6.3 練習題：郊遊（習題 ID：PICNIC，難度：低） 106
6.4 解題：郊遊 107
6.5 練習題：蓋遊戲闆（習題 ID：BOARDCOVER，難度：低） 109
6.6 解題：蓋遊戲闆 111
6.7 優化問題 113
6.8 練習題：時鍾同步（習題 ID：CLOCKSYNC，難度：中） 116
6.9 解題：時鍾同步 117
6.10 常見窮舉搜索類型 119
第7 章 分治法 120
7.1 引言 120
7.2 練習題：四叉樹問題（題目 ID：QUADTREE，難度：低） 130
7.3 解題：四叉樹問題 131
7.4 練習題：切割籬笆（習題 ID：FENCE，難度：中） 134
7.5 解題：切割籬笆 135
7.6 練習題：粉絲見麵會（題目 ID：FANMEETING，難度：高） 139
7.7 解題：粉絲見麵會 141
第8 章 動態規劃法 143
8.1 引言 143
8.2 練習題：通配符（習題 ID：WILDCARD，難度：中） 151
8.3 解題：通配符 152
8.4 典型優化問題 156
8.5 練習題：閤並LIS（題目 ID：JLIS，難度：低） 163
8.6 解題：閤並LIS 164
8.7 練習題：背誦圓周率（題目 ID：PI，難度：低） 166
8.8 解題：背誦圓周率 167
8.9 練習題：Quantization（題目 ID：QUANTIZE，難度：中） 169
8.10 解題：Quantization 170
8.11 所有可能的個數與概率 174
8.12 練習題：非對稱鋪設（題目 ID：ASYMTILING，難度：低） 180
8.13 解題：非對稱鋪設 181
8.14 練習題：多聯骨牌（題目 ID：POLY，難度：中） 183
8.15 解題：多聯骨牌 185
8.16 練習題：逃獄的韓尼拔博士（題目 ID：NUMB3RS，難度：中） 187
8.17 解題：逃獄的韓尼拔博士 189
第9 章 動態規劃技巧 194
9.1 計算優化問題的實際答案 194
9.2 練習題：打包行李（題目 ID：PACKING，難度：中） 195
9.3 解題：打包行李 197
9.4 練習題：光學字符識彆（題目 ID：OCR，難度：高） 199
9.5 解題：光學字符識彆 201
9.6 計算第k個答案 204
9.7 練習題：第k個最大遞增子序列（題目 ID：KLIS，難度：高） 209
9.8 解題：第k個最長遞增子序列 210
9.9 練習題：龍麯綫（題目 ID：DRAGON，難度：中） 214
9.10 解題：龍麯綫 216
9.11 對非整數型輸入的製錶 219
9.12 練習題：韋布巴津（題目 ID：ZIMBABWE，難度：高） 224
9.13 解題：韋布巴津 225
9.14 練習題：恢復實驗數據（題目 ID：RESTORE，難度：中） 230
9.15 解題：恢復實驗數據 231
9.16 組閤遊戲 234
9.17 練習題：數字遊戲（題目 ID：NUMBERGAME，難度：低） 239
9.18 解題：數字遊戲 240
9.19 練習題：方塊遊戲（題目 ID：BLOCKGAME，難度：中） 242
9.20 解題：方塊遊戲 243
9.21 迭代動態規劃法 245
9.22 練習題：迴轉壽司（題目 ID：SUSHI，難度：中） 249
9.23 解題：迴轉壽司 250
9.24 練習題：Genius（題目 ID：GENIUS，難度：中） 253
9.25 解題：Genius 254
9.26 續讀 256
第10 章 貪心法 257
10.1 引言 257
10.2 練習題：加熱便當（題目 ID：LUNCHBOX，難度：低） 264
10.3 解題：加熱便當 265
10.4 練習題：閤並字符串（題目 ID：STRJOIN，難度：中） 268
10.5 解題：閤並字符串 269
10.6 練習題：米那斯雅諾（題目 ID：MINASTIRITH，難度：高） 273
10.7 解題：米那斯雅諾 275
第11 章 組閤搜索 281
11.1 引言 281
11.2 組閤搜索的方法 283
11.3 練習題：蓋遊戲闆2（題目 ID：BOARDCOVER2，難度：低） 298
11.4 解題：蓋遊戲闆2 299
11.5 練習題：患有嚴重過敏癥的朋友們（題目 ID：ALLERGY，難度：中） 303
11.6 解題：患有嚴重過敏癥的朋友們........304
11.7 練習題：數謎（題目 ID：KAKURO2，難度：中） 307
11.8 解題：數謎 309
11.9 續讀 315
第12 章 將優化問題轉換為決策問題求解 316
12.1 引言 316
12.2 練習題：南極基地（題目 ID：ARCTIC，難度：低） 320
12.3 解題：南極基地 321
12.4 練習題：加拿大旅行（題目 ID：CANADATRIP，難度：中） 323
12.5 解題：加拿大旅行 324
12.6 練習題：退選課程（題目 ID：WITHDRAWAL，難度：高） 326
12.7 解題：退選課程 327
第四部分 一些著名的算法
第13 章 數值分析 331
13.1 引言 331
13.2 二分法 331
13.3 練習題：提高獲勝率（題目 ID：RATIO，難度：低） 338
13.4 解題：提高獲勝率 339
13.5 三叉搜索 341
13.6 練習題：花粉化石（題目 ID：FOSSIL，難度：高） 346
13.7 解題：花粉化石 347
13.8 其他主題 351
第14 章 整數論 352
14.1 引言 352
14.2 素數 352
14.3 練習題：密碼486（題目 ID：PASS486，難度：中） 357
14.4 解題：密碼486 357
14.5 歐幾裏得算法 360
14.6 練習題：魔法藥水（題目 ID：POTION，難度：中） 361
14.7 解題：魔法藥水 362
14.8 模運算 364
14.9 續讀 366
第15 章 計算幾何 367
15.1 引言 367
15.2 計算幾何的工具 367
15.3 相交、距離、麵積 373
15.4 練習題：彈球模擬（題目 ID：PINBALL，難度：高） 377
15.5 解題：彈球模擬 379
15.6 多邊形 383
15.7 練習題：金銀島（題目 ID：TREASURE，難度：高） 386
15.8 解題：金銀島 387
15.9 練習題：是呆子？不是呆子？（題目ID：NERDS，難度：中） 390
15.10 解題：是呆子？不是呆子？ 392
15.11 計算幾何算法設計範式 396
15.12 常見失誤與注意事項 403
15.13 續讀 404
第五部分 基本數據結構
第16 章 位掩碼 410
16.1 引言 410
16.2 利用位掩碼實現集閤 413
16.3 位掩碼應用示例 417
16.4 練習題：畢業學期（題目 ID：GRADUATION，難度：中） 420
16.5 解題：畢業學期 422
16.6 續讀 424
第17 章 部分和 425
17.1 引言 425
17.2 練習題：聖誕娃娃（題目 ID：CHRISTMAS，難度：中） 429
17.3 解題：聖誕娃娃 430
17.4 其他學習內容 432
第18 章 綫性數據結構 433
18.1 引言 433
18.2 動態數組 433
18.3 鏈錶 437
18.4 動態數組和鏈錶的比較 440
18.5 練習題：約瑟夫斯（題目 ID：JOSEPHUS，難度：低） 440
18.6 解題：約瑟夫斯 441
18.7 續讀 442
第19 章 隊列、棧以及雙端隊列 443
19.1 引言 443
19.2 隊列、棧以及雙端隊列的實現方法 444
19.3 隊列與棧的應用 445
19.4 練習題：不匹配括號（題目 ID：BRACKETS2，難度：低） 448
19.5 解題：不匹配括號 449
19.6 練習題：分析外星信號（題目 ID：ITES，難度：中） 450
19.7 解題：分析外星信號 451
第20 章 字符串 455
20.1 引言 455
20.2 字符串檢索 456
20.3 練習題：宰河的保險箱（題目 ID：JAEHASAFE，難度：中） 466
20.4 解題：宰河的保險箱 467
20.5 後綴數組 468
20.6 練習題：口頭禪（題目 ID：HABIT，難度：中） 476
20.7 解題：口頭禪 477
20.8 續讀 478
第六部分 樹
第21 章 樹的實現與遍曆 481
21.1 引言 481
21.2 樹的遍曆 483
21.3 練習題：變更樹的遍曆順序（題目 ID：TRAVERSAL，難度：低） 484
21.4 解題：變更樹的遍曆順序 486
21.5 練習題：要塞（題目 ID：FORTRESS，難度：中） 487
21.6 解題：要塞 488
第22 章 二叉搜索樹 493
22.1 引言 493
22.2 二叉搜索樹的定義和操作 493
22.3 時間復雜度分析與平衡二叉搜索樹 496
22.4 練習題：是呆子？不是呆子？2（題目ID：NERD2，難度：中） 496
22.5 解題：是呆子？不是呆子？2 498
22.6 直接實現平衡二叉搜索樹：樹堆 501
22.7 練習題：反轉插入排序（題目 ID：INSERTION，難度：中） 508
22.8 解題：反轉插入排序 509
第23 章 優先級隊列和堆 511
23.1 引言 511
23.2 堆的定義與實現方法 512
23.3 練習題：變化的中間值（題目 ID：RUNNINGMEDIAN，難度：低） 518
23.4 解題：變化的中間值 519
第24 章 區間樹 521
24.1 區間樹：區間相關問題解答 521
24.2 練習題：登山路（題目 ID：MORDDR，難度：中） 527
24.3 解題：登山路 528
24.4 練習題：尋根問祖（題目 ID：FAMILYTREE，難度：高） 529
24.5 解題：尋根問祖 530
24.6 樹狀數組：快速而簡單的區間和 533
24.7 練習題：計算插入排序的時間（題目 ID：MEASURETIME，難度：中） 536
24.8 解題：計算插入排序的時間 537
第25 章 互斥集閤 541
25.1 引言 541
25.2 練習題：編輯器之爭（題目 ID：EDITORWARS，難度：中） 546
25.3 解題：編輯器之爭 548
第26 章 字典樹 553
26.1 引言 553
26.2 練習題：再見，謝謝所有的魚（題目 ID：SOLONG，難度：中） 557
26.3 解題：再見，謝謝所有的魚 559
26.4 利用字典樹檢索多重字符串 563
26.5 練習題：安全終結者（題目 ID：NH，難度：高） 569
26.6 解題：安全終結者 570
第七部分 圖
第27 章 圖的錶示方式及定義 576
27.1 引言 576
27.2 圖的應用示例 579
27.3 隱式圖結構 580
27.4 圖的幾種錶示法 581
第28 章 圖的深度優先搜索 585
28.1 引言 585
28.2 練習題：古語詞典（習題 ID：DICTIONARY，難度：低） 590
28.3 解題：古語詞典 591
28.4 歐拉迴路 594
28.5 練習題：有限單詞接龍（題目 ID：WORDCHAIN，難度：低） 597
28.6 解題：有限單詞接龍 598
28.7 理論背景及應用 602
28.8 練習題：安裝監控攝像頭（題目 ID：GALLERY，難度：中） 613
28.9 解題：安裝監控攝像頭 614
28.10 練習題：安排會議室（題目 ID：MEETINGROOM，難度：高） 616
28.11 解題：安排會議室 618
第29 章 圖的寬度優先搜索 625
29.1 引言 625
29.2 練習題：排序遊戲（題目 ID：SORTGAME，難度：中） 629
29.3 解題：排序遊戲 630
29.4 練習題：兒童節（題目 ID：CHILDRENDAY，難度：高） 633
29.5 解題：兒童節 634
29.6 最短路徑策略 637
29.7 練習題：漢諾塔（題目 ID：HANOI4B，難度：中） 648
29.8 解題：漢諾塔 650
第30 章 最短路徑問題 653
30.1 引言 653
30.2 迪傑斯特拉最短路徑算法 654
30.3 練習題：信號路由（題目 ID：ROUTING，難度：低） 661
30.4 解題：信號路由 662
30.5 練習題：消防車（題目 ID：FIRETRUCKS，難度：中） 663
30.6 解題：消防車 664
30.7 練習題：鐵人N項比賽（題目 ID：NTHLON，難度：高） 665
30.8 解題：鐵人N項比賽 667
30.9 貝爾曼－福特最短路徑算法 669
30.10 練習題：時間旅行（題目 ID：TIMETRIP，難度：中） 674
30.11 解題：時間旅行 675
30.12 弗洛伊德多源最短路徑算法 677
30.13 練習題：檢查酒駕（題目 ID：DRUNKEN，難度：中） 682
30.14 解題：檢查酒駕 684
30.15 練習題：競選承諾（題目 ID：PROMISES，難度：中） 685
30.16 解題：競選承諾 687
第31 章 最小生成樹 689
31.1 引言 689
31.2 剋魯斯剋爾最小生成樹算法 690
31.3 普裏姆最小生成樹算法 694
31.4 練習題：局域網（題目 ID：LAN，難度：低） 697
31.5 解題：局域網 698
31.6 練習題：選定旅行路綫（題目 ID：TPATH，難度：高） 699
31.7 解題：選定旅行路綫 700
第32 章 網絡流 705
32.1 引言 705
32.2 福特－富爾剋森算法 706
32.3 網絡建模 713
32.4 練習題：操縱比賽（題目 ID：MATCHFIX，難度：中） 715
32.5 解題：操縱比賽 717
32.6 練習題：國傢項目（題目 ID：PROJECTS，難度：高） 719
32.7 解題：國傢項目 720
32.8 二分圖匹配 723
32.9 練習題：象（題目 ID：BISHOPS，難度：中） 729
32.10 解題：象 730
32.11 練習題：設置陷阱（題目 ID：TRAPCARD，難度：高） 732
32.12 解題：設置陷阱 734
32.13 其他學習內容 737
· · · · · · (
收起)
