算法競賽入門經典 — 訓練指南 (升級版)

劉汝佳，2000年3月獲得NOI2000全國青少年信息學奧林匹克競賽一等獎。
大一時獲2001年ACM/ICPC國際大學生程序設計競賽亞洲-上海賽區冠軍和2002年世界總決賽銀牌。
2004年至今共為ACM/ICPC亞洲賽區命題二十餘道，擔任6次裁判和2次命題總監，並應邀參加IOI和ACM/ICPC相關國際研討會。
曾出版《算法競賽入門經典》《算法競賽入門經典——訓練指南》《編程挑戰》等暢銷書。

陳鋒，任職於廈門宇道信隆信息科技有限公司，擔任技術總監職務，專注於人工智能以及算法技術在金融科技領域的應用。
同時擔任四川大學ACM/ICPC算法競賽集訓隊特邀指導老師，榕陽編程NOI、NOIP指導教練。
所帶學員多次獲得ICPC金/銀牌，進入NOI省隊等。
曾出版《算法競賽入門經典——訓練指南》《算法競賽入門經典——習題與解答》《算法競賽入門經典——算法實現》等暢銷書。

第1章算法設計基礎 1
1.1 思維的體操 1
1.2 問題求解常見策略14
1.3 高效算法設計舉例36
1.4 動態規劃專題55
1.5 小結與習題71
1.5.1 問題求解策略72
1.5.2 高效算法設計80
1.5.3 動態規劃83

第2章數學基礎86
2.1 基本計數方法86
2.2 遞推關係92
2.3 數論101
2.3.1 基本概念102
2.3.2 模方程107
2.3.3 線性篩113
2.3.4 積性函數與莫比烏斯反演116
2.3.5 篩法求解積性函數118
2.4 組合遊戲124
2.5 概率與數學期望130
2.6 置換及其應用135
2.7 矩陣和線性方程組142
2.8 快速傅里葉變換（FFT） 154
2.9 數值方法165
2.10 小結與習題171
2.10.1 組合計數173
2.10.2 數論177
2.10.3 組合遊戲181
2.10.4 概率183
2.10.5 置換184
2.10.6 矩陣與線性方程組186
2.10.7 快速傅里葉變換（FFT） 188
2.10.8 數值方法189

第3章實用數據結構192
3.1 基礎數據結構回顧192
3.1.1 抽像數據類型（ADT） 192
3.1.2 優先隊列194
3.1.3 並查集197
3.2 區間信息的維護與查詢199
3.2.1 二叉索引樹（樹狀數組） 200
3.2.2 RMQ問題202
3.2.3 線段樹（1）：點修改204
3.2.4 線段樹（2）：區間修改207
3.3 字符串（1） 219
3.3.1 Trie 219
3.3.2 KMP算法222
3.3.3 Aho-Corasick自動機225
3.4 字符串（2） 229
3.4.1 後綴數組229
3.4.2 最長公共前綴（LCP） 233
3.4.3 基於哈希值的LCP算法235
3.4.4 回文的Manacher算法238
3.5 字符串（3） 240
3.5.1 後綴自動機的性質241
3.5.2 後綴鏈接樹（Suffix Link Tree） 241
3.5.3 後綴自動機的構造算法242
3.6 排序二叉樹255
3.6.1 基本概念255
3.6.2 用Treap實現名次樹258
3.6.3 用伸展樹實現可分裂與合併的序列266
3.7 樹的經典問題與方法270
3.8 動態樹與LCT 289
3.9 離線算法299
3.10 kd-Tree 312
3.11 可持久化數據結構319
3.12 小結與習題331
3.12.1 基礎數據結構332
3.12.2 區間信息維護333
3.12.3 字符串算法335
3.12.4 排序二叉樹338
3.12.5 樹的經典問題與方法339
3.12.6 動態樹與LCT 342
3.12.7 離線算法344
3.12.8 kd-Tree 347
3.12.9 可持久化數據結構348

第4章幾何問題351
4.1 二維幾何基礎351
4.1.1 基本運算352
4.1.2 點和直線353
4.1.3 多邊形355
4.1.4 例題選講356
4.1.5 二維幾何小結359
4.2 與圓和球有關的計算問題360
4.2.1 圓的相關計算360
4.2.2 球面相關問題366
4.3 二維幾何常用算法366
4.3.1 點在多邊形內的判定366
4.3.2 凸包368
4.3.3 半平面交372
4.3.4 平面區域378
4.4 三維幾何基礎382
4.4.1 三維點積383
4.4.2 三維叉積384
4.4.3 三維凸包386
4.4.4 例題選講388
4.4.5 三維幾何小結392
4.5 小結與習題393
4.5.1 基礎題目393
4.5.2 二維幾何計算395
4.5.3 幾何算法398
4.5.4 三維幾何403

第5章圖論算法與模型408
5.1 基礎題目選講408
5.2 深度優先遍歷411
5.2.1 無向圖的割頂和橋413
5.2.2 無向圖的雙連通分量416
5.2.3 有向圖的強連通分量420
5.2.4 2-SAT問題424
5.3 最短路問題428
5.3.1 再談Dijkstra算法428
5.3.2 再談Bellman-Ford算法432
5.3.3 例題選講436
5.4 生成樹相關問題443
5.5 二分圖匹配447
5.5.1 二分圖最大匹配447
5.5.2 二分圖最佳完美匹配448
5.5.3 穩定婚姻問題452
5.5.4 常見模型455
5.6 網絡流問題457
5.6.1 最短增廣路算法457
5.6.2 最小費用最大流算法462
5.6.3 建模與模型變換464
5.6.4 例題選講467
5.7 小結與習題472
5.7.1 基礎知識和算法472
5.7.2 DFS及其應用472
5.7.3 最短路及其應用476
5.7.4 最小生成樹477
5.7.5 二分圖匹配479
5.7.6 網絡流480

第6章更多算法專題484
6.1 輪廓線動態規劃484
6.2 嵌套和分塊數據結構490
6.3 暴力法專題500
6.3.1 路徑尋找問題500
6.3.2 對抗搜索505
6.3.3 精確覆蓋問題和DLX算法510
6.4 幾何專題516
6.4.1 仿射變換與矩陣516
6.4.2 離散化和掃描法518
6.4.3 運動規劃527
6.5 數學專題529
6.5.1 小專題集錦530
6.5.2 線性規劃532
6.6 淺談代碼設計與靜態查錯533
6.6.1 簡單的Bash 533
6.6.2 《仙劍奇俠傳四》之最後的戰役542
6.7 小結與習題548
6.7.1 輪廓線上的動態規劃548
6.7.2 數據結構綜合應用550
6.7.3 暴力法557
6.7.4 幾何專題562
6.7.5 數學專題567
6.7.6 代碼組織與調試569

附錄Java、C#和Python語言簡介575
主要參考書目582