算法競(jìng)賽入門經(jīng)典（第2版）

第1部分　語言篇
第1章　程序設(shè)計(jì)入門 1
1.1 算術(shù)表達(dá)式 1
1.2 變量及其輸入 3
1.3 順序結(jié)構(gòu)程序設(shè)計(jì) 6
1.4 分支結(jié)構(gòu)程序設(shè)計(jì) 9
1.5 注解與習(xí)題 13
1.5.1 C語言、C99、C11及其他 13
1.5.2 數(shù)據(jù)類型與輸入格式 14
1.5.3 習(xí)題 15
1.5.4 小結(jié) 16
第2章　循環(huán)結(jié)構(gòu)程序設(shè)計(jì) 18
2.1 for循環(huán) 18
2.2 while循環(huán)和do-while循環(huán) 22
2.3 循環(huán)的代價(jià) 25
2.4 算法競(jìng)賽中的輸入輸出框架 27
2.5 注解與習(xí)題 34
2.5.1 習(xí)題 34
2.5.2 小結(jié) 36
第3章　數(shù)組和字符串 37
3.1 數(shù)組 37
3.2 字符數(shù)組 41
3.3 競(jìng)賽題目選講 45
3.4 注解與習(xí)題 53
3.4.1 進(jìn)位制與整數(shù)表示 54
3.4.2 思考題 55
3.4.3 黑盒測(cè)試和在線評(píng)測(cè)系統(tǒng) 55
3.4.4 例題一覽與習(xí)題 56
3.4.5 小結(jié) 59
第4章　函數(shù)和遞歸 61
4.1 自定義函數(shù)和結(jié)構(gòu)體 61
4.2 函數(shù)調(diào)用與參數(shù)傳遞 65
4.2.1 形參與實(shí)參 65
4.2.2 調(diào)用棧 66
4.2.3 用指針作參數(shù) 69
4.2.4 初學(xué)者易犯的錯(cuò)誤 71
4.2.5 數(shù)組作為參數(shù)和返回值 71
4.2.6 把函數(shù)作為函數(shù)的參數(shù) 73
4.3 遞歸 74
4.3.1 遞歸定義 74
4.3.2 遞歸函數(shù) 75
4.3.3 C語言對(duì)遞歸的支持 75
4.3.4 段錯(cuò)誤與棧溢出 77
4.4 競(jìng)賽題目選講 79
4.5 注解與習(xí)題 92
4.5.1 頭文件、副作用及其他 93
4.5.2 例題一覽和習(xí)題 95
4.5.3 小結(jié) 99
第5章　 C++與STL入門 100
5.1 從C到C++ 100
5.1.1 C++版框架 101
5.1.2 引用 102
5.1.3 字符串 103
5.1.4 再談結(jié)構(gòu)體 105
5.1.5 模板 106
5.2 STL初步 108
5.2.1 排序與檢索 108
5.2.2 不定長(zhǎng)數(shù)組：vector 109
5.2.3 集合：set 112
5.2.4 映射：map 113
5.2.5 棧、隊(duì)列與優(yōu)先隊(duì)列 115
5.2.6 測(cè)試STL 120
5.3 應(yīng)用：大整數(shù)類 123
5.3.1 大整數(shù)類BigInteger 124
5.3.2 四則運(yùn)算 125
5.3.3 比較運(yùn)算符 126
5.4 競(jìng)賽題目舉例 127
5.5 習(xí)題 134
第2部分　基礎(chǔ)篇
第6章　數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 139
6.1 再談棧和隊(duì)列 139
6.2 鏈表 143
6.3 樹和二叉樹 148
6.3.1 二叉樹的編號(hào) 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 拓?fù)渑判?167
6.4.4 歐拉回路 168
6.5 競(jìng)賽題目選講 170
6.6 訓(xùn)練參考 175
第7章　暴力求解法 182
7.1 簡(jiǎn)單枚舉 182
7.2 枚舉排列 184
7.2.1 生成1~n的排列 184
7.2.2 生成可重集的排列 185
7.2.3 解答樹 186
7.2.4 下一個(gè)排列 187
7.3 子集生成 188
7.3.1 增量構(gòu)造法 188
7.3.2 位向量法 188
7.3.3 二進(jìn)制法 189
7.4 回溯法 191
7.4.1 八皇后問題 191
7.4.2 其他應(yīng)用舉例 194
7.5 路徑尋找問題 198
7.6 迭代加深搜索 206
7.7 競(jìng)賽題目選講 209
7.8 訓(xùn)練參考 213
第3部分　競(jìng)賽篇
第8章　高效算法設(shè)計(jì) 220
8.1 算法分析初步 220
8.1.1 漸進(jìn)時(shí)間復(fù)雜度 220
8.1.2 上界分析 222
8.1.3 分治法 223
8.1.4 正確對(duì)待算法分析結(jié)果 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 背包相關(guān)問題 231
8.4.2 區(qū)間相關(guān)問題 232
8.4.3 Huffman編碼 234
8.5 算法設(shè)計(jì)與優(yōu)化策略 235
8.6 競(jìng)賽題目選講 244
8.7 訓(xùn)練參考 252
第9章　動(dòng)態(tài)規(guī)劃初步 259
9.1 數(shù)字三角形 259
9.1.1 問題描述與狀態(tài)定義 259
9.1.2 記憶化搜索與遞推 260
9.2 DAG上的動(dòng)態(tài)規(guī)劃 262
9.2.1 DAG模型 262
9.2.2 最長(zhǎng)路及其字典序 262
9.2.3 固定終點(diǎn)的最長(zhǎng)路和最短路 264
9.2.4 小結(jié)與應(yīng)用舉例 267
9.3 多階段決策問題 270
9.3.1 多段圖的最短路 270
9.3.2 0-1背包問題 271
9.4 更多經(jīng)典模型 274
9.4.1 線性結(jié)構(gòu)上的動(dòng)態(tài)規(guī)劃 274
9.4.2 樹上的動(dòng)態(tài)規(guī)劃 280
9.4.3 復(fù)雜狀態(tài)的動(dòng)態(tài)規(guī)劃 284
9.5 競(jìng)賽題目選講 290
9.6 訓(xùn)練參考 303
第10章　數(shù)學(xué)概念與方法 310
10.1 數(shù)論初步 310
10.1.1 歐幾里德算法和唯一分解定理 310
10.1.2 Eratosthenes篩法 312
10.1.3 擴(kuò)展歐幾里德算法 313
10.1.4 同余與模算術(shù) 314
10.1.5 應(yīng)用舉例 316
10.2 計(jì)數(shù)與概率基礎(chǔ) 318
10.2.1 楊輝三角與二項(xiàng)式定理 319
10.2.2 數(shù)論中的計(jì)數(shù)問題 321
10.2.3 編碼與解碼 323
10.2.4 離散概率初步 324
10.3 其他數(shù)學(xué)專題 327
10.3.1 遞推 327
10.3.2 數(shù)學(xué)期望 332
10.3.3 連續(xù)概率 334
10.4 競(jìng)賽題目選講 336
10.5 訓(xùn)練參考 341
第11章　圖論模型與算法 352
11.1 再談樹 352
11.1.1 無根樹轉(zhuǎn)有根樹 352
11.1.2 表達(dá)式樹 353
11.2 最小生成樹 355
11.2.1 Kruskal算法 356
11.2.2 競(jìng)賽題目選解 358
11.3 最短路問題 359
11.3.1 Dijkstra算法 359
11.3.2 Bellman-Ford算法 363
11.3.3 Floyd算法 364
11.3.4 競(jìng)賽題目選講 365
11.4 網(wǎng)絡(luò)流初步 366
11.4.1 最大流問題 366
11.4.2 增廣路算法 367
11.4.3 最小割最大流定理 369
11.4.4 最小費(fèi)用最大流問題 370
11.4.5 應(yīng)用舉例 372
11.5 競(jìng)賽題目選講 375
11.6 訓(xùn)練參考 379
11.7 總結(jié)與展望 384
第12章　高級(jí)專題 386
12.1 知識(shí)點(diǎn)選講 386
12.1.1 自動(dòng)機(jī) 386
12.1.2 樹的經(jīng)典問題和方法 392
12.1.3 可持久化數(shù)據(jù)結(jié)構(gòu) 397
12.1.4 多邊形的布爾運(yùn)算 399
12.2 難題選解 404
12.2.1 數(shù)據(jù)結(jié)構(gòu) 404
12.2.2 網(wǎng)絡(luò)流 409
12.2.3 數(shù)學(xué) 411
12.2.4 幾何 415
12.2.5 非完美算法 419
12.2.6 雜題選講 423
12.3 小結(jié)與習(xí)題 446
附錄A 開發(fā)環(huán)境與方法 455
A.1 命令行 455
A.1.1 文件系統(tǒng) 455
A.1.2 進(jìn)程 456
A.1.3 程序的執(zhí)行 456
A.1.4 重定向和管道 457
A.1.5 常見命令 457
A.2 操作系統(tǒng)腳本編程入門 458
A.2.1 Windows下的批處理 458
A.2.2 Linux下的Bash腳本 459
A.2.3 再談隨機(jī)數(shù) 460
A.3 編譯器和調(diào)試器 460
A.3.1 gcc的安裝和測(cè)試 460
A.3.2 常見編譯選項(xiàng) 461
A.3.3 gdb簡(jiǎn)介 462
A.3.4 gdb的高級(jí)功能 463
A.4 淺談IDE 464
主要參考書目 465