算法競賽入門經典（第2版）

第1部分 語言篇

第1章 程序設計入門1
1.1算術表達式1
1.2變量及其輸入3
1.3順序結構程序設計6
1.4分支結構程序設計9
1.5注解與習題13
1.5.1C語言、C99、C11及其他13
1.5.2數據類型與輸入格式14
1.5.3習題15
1.5.4小結16
第2章 循環結構程序設計18
2.1for循環18
2.2while循環和do—while循環22
2.3循環的代價25
2.4算法競賽中的輸入輸出框架27
2.5注解與習題34
2.5.1習題34
2.5.2小結36
第3章 數組和字符串37
3.1數組37
3.2字符數組41
3.3競賽題目選講45
3.4注解與習題53
3.4.1進位制與整數表示54
3.4.2思考題55
3.4.3黑盒測試和在線評測系統55
3.4.4例題一覽與習題56
3.4.5小結59
第4章 函數和遞歸61
4.1自定義函數和結構體61
4.2函數調用與參數傳遞65
4.2.1形參與實參65
4.2.2調用棧66
4.2.3用指針作參數69
4.2.4初學者易犯的錯誤71
4.2.5數組作為參數和返回值71
4.2.6把函數作為函數的參數73
4.3遞歸74
4.3.1遞歸定義74
4.3.2遞歸函數75
4.3.3C語言對遞歸的支持75
4.3.4段錯誤與棧溢出77
4.4競賽題目選講79
4.5注解與習題92
4.5.1頭文件、副作用及其他93
4.5.2例題一覽和習題95
4.5.3小結99
第5章 C++與STL入門100
5.1從C到C++100
5.1.1C++版框架101
5.1.2引用102
5.1.3字符串103
5.1.4再談結構體105
5.1.5模板106
5.2STL初步108
5.2.1排序與檢索108
5.2.2不定長數組：vector109
5.2.3集合：set112
5.2.4映射：map113
5.2.5棧、隊列與優先隊列115
5.2.6測試STL120
5.3應用：大整數類123
5.3.1大整數類BigInteger124
5.3.2四則運算125
5.3.3比較運算符126
5.4競賽題目舉例127
5.5習題134

第2部分 基礎篇
第6章 數據結構基礎139
6.1再談棧和隊列139
6.2鏈表143
6.3樹和二叉樹148
6.3.1二叉樹的編號148
6.3.2二叉樹的層次遍歷150
6.3.3二叉樹的遞歸遍歷155
6.3.4非二叉樹160
6.4圖162
6.4.1用DFS求連通塊162
6.4.2用BFS求最短路164
6.4.3拓撲排序167
6.4.4歐拉回路168
6.5競賽題目選講170
6.6訓練參考175
第7章 暴力求解法182
7.1簡單枚舉182
7.2枚舉排列184
7.2.1生成1～～n的排列184
7.2.2生成可重集的排列185
7.2.3解答樹186
7.2.4下一個排列187
7.3子集生成188
7.3.1增量構造法188
7.3.2位向量法188
7.3.3二進制法189
7.4回溯法191
7.4.1八皇后問題191
7.4.2其他應用舉例194
7.5路徑尋找問題198
7.6迭代加深搜索206
7.7競賽題目選講209
7.8訓練參考213

第3部分 競賽篇
第8章 高效算法設計220
8.1算法分析初步220
8.1.1漸進時間復雜度220
8.1.2上界分析222
8.1.3分治法223
8.1.4正確對待算法分析結果224
8.2再談排序與檢索225
8.2.1歸並排序225
8.2.2快速排序227
8.2.3二分查找227
8.3遞歸與分治229
8.4貪心法231
8.4.1背包相關問題231
8.4.2區間相關問題232
8.4.3Huffman編碼234
8.5算法設計與優化策略235
8.6競賽題目選講244
8.7訓練參考252
第9章 動態規划初步259
9.1數字三角形259
9.1.1問題描述與狀態定義259
9.1.2記憶化搜索與遞推260
9.2DAG上的動態規划262
9.2.1DAG模型262
9.2.2最長路及其字典序262
9.2.3固定終點的最長路和最短路264
9.2.4小結與應用舉例267
9.3多階段決策問題270
9.3.1多段圖的最短路270
9.3.20—1背包問題271
9.4更多經典模型274
9.4.1線性結構上的動態規划274
9.4.2樹上的動態規划280
9.4.3復雜狀態的動態規划284
9.5競賽題目選講290
9.6訓練參考303
第10章 數學概念與方法310
10.1數論初步310
10.1.1歐幾里德算法和唯一分解定理310
10.1.2Eratosthenes篩法312
10.1.3擴展歐幾里德算法313
10.1.4同余與模算術314
10.1.5應用舉例316
10.2計數與概率基礎318
10.2.1楊輝三角與二項式定理319
10.2.2數論中的計數問題321
10.2.3編碼與解碼323
10.2.4離散概率初步324
10.3其他數學專題327
10.3.1遞推327
10.3.2數學期望332
10.3.3連續概率334
10.4競賽題目選講336
10.5訓練參考341
第11章 圖論模型與算法352
11.1再談樹352
11.1.1無根樹轉有根樹352
11.1.2表達式樹353
11.2最小生成樹355
11.2.1Kruskal算法356
11.2.2競賽題目選解358
11.3最短路問題359
11.3.1Dijkstra算法359
11.3.2Bellman—Ford算法363
11.3.3Floyd算法364
11.3.4競賽題目選講365
11.4網絡流初步366
11.4.1最大流問題366
11.4.2增廣路算法367
11.4.3最小割最大流定理369
11.4.4最小費用最大流問題370
11.4.5應用舉例372
11.5競賽題目選講375
11.6訓練參考379
11.7總結與展望384
第12章 高級專題386
12.1知識點選講386
12.1.1自動機386
12.1.2樹的經典問題和方法392
12.1.3可持久化數據結構397
12.1.4多邊形的布爾運算399
12.2難題選解404
12.2.1數據結構404
12.2.2網絡流409
12.2.3數學411
12.2.4幾何415
12.2.5非完美算法419
12.2.6雜題選講423
12.3小結與習題446

附錄A 開發環境與方法455
A.1命令行455
A.1.1文件系統455
A.1.2進程456
A.1.3程序的執行456
A.1.4重定向和管道457
A.1.5常見命令457
A.2操作系統腳本編程入門458
A.2.1Windows下的批處理458
A.2.2Linux下的Bash腳本459
A.2.3再談隨機數460
A.3編譯器和調試器460
A.3.1gcc的安裝和測試460
A.3.2常見編譯選項461
A.3.3gdb簡介462
A.3.4gdb的高級功能463
A.4淺談IDE464
主要參考書目465