目錄


第1部分　[準(zhǔn)備篇]攻克程序設(shè)計(jì)競(jìng)賽的學(xué)習(xí)方法 1
第1章　有效運(yùn)用在線評(píng)測(cè)系統(tǒng) 3
1．1　攻克程序設(shè)計(jì)競(jìng)賽的學(xué)習(xí)方法 3
1．2　什么是在線評(píng)測(cè) 7
1．3　用戶注冊(cè) 9
1．4　瀏覽問(wèn)題 10
1．5　解答問(wèn)題 12
1．6　個(gè)人頁(yè)面 18
1．7　如何運(yùn)用本書 19
第2部分　[基礎(chǔ)篇]為程序設(shè)計(jì)競(jìng)賽做準(zhǔn)備的算法與數(shù)據(jù)結(jié)構(gòu) 21
第2章　算法與復(fù)雜度 23
2．1　算法是什么 23
2．2　問(wèn)題與算法示例 23
2．3　偽代碼 25
2．4　算法的效率 26
2．5　入門問(wèn)題 28
第3章　初等排序 33
3．1　挑戰(zhàn)問(wèn)題之前——排序 33
3．2　插入排序法 35
3．3　冒泡排序法 40
3．4　選擇排序法 44
3．5　穩(wěn)定排序 48
3．6　希爾排序法 52
第4章　數(shù)據(jù)結(jié)構(gòu) 57
4．1　挑戰(zhàn)問(wèn)題之前——什么是數(shù)據(jù)結(jié)構(gòu) 57
4．2　棧 59
4．3　隊(duì)列 64
4．4　鏈表 70
4．5　標(biāo)準(zhǔn)庫(kù)的數(shù)據(jù)結(jié)構(gòu) 77
4．6　數(shù)據(jù)結(jié)構(gòu)的應(yīng)用——計(jì)算面積 86
第5章　搜索 89
5．1　挑戰(zhàn)問(wèn)題之前——搜索 89
5．2　線性搜索 91
5．3　二分搜索 94
5．4　散列法 98
5．5　借助標(biāo)準(zhǔn)庫(kù)搜索 102
5．6　搜索的應(yīng)用——計(jì)算最優(yōu)解 106
第6章　遞歸和分治法 109
6．1　挑戰(zhàn)問(wèn)題之前——遞歸與分治 109
6．2　窮舉搜索 111
6．3　科赫曲線 114
第7章　高等排序 119
7．1　歸并排序 120
7．2　分割 125
7．3　快速排序 129
7．4　計(jì)數(shù)排序 133
7．5　利用標(biāo)準(zhǔn)庫(kù)排序 137
7．6　逆序數(shù) 139
7．7　最小成本排序 143
第8章　樹 147
8．1　挑戰(zhàn)問(wèn)題之前——樹結(jié)構(gòu) 148
8．2　有根樹的表達(dá) 150
8．3　二叉樹的表達(dá) 154
8．4　樹的遍歷 159
8．5　樹遍歷的應(yīng)用——樹的重建 163
第9章　二叉搜索樹 167
9．1　挑戰(zhàn)問(wèn)題之前——二叉搜索樹 168
9．2　二叉搜索樹——插入 169
9．3　二叉搜索樹——搜索 174
9．4　二叉搜索樹——?jiǎng)h除 177
9．5　通過(guò)標(biāo)準(zhǔn)庫(kù)管理集合 182
第10章　堆 189
10．1　挑戰(zhàn)問(wèn)題之前——堆 190
10．2　完全二叉樹 191
10．3　最大/最小堆 193
10．4　優(yōu)先級(jí)隊(duì)列 197
10．5　通過(guò)標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 201
第11章　動(dòng)態(tài)規(guī)劃法 203
11．1　挑戰(zhàn)問(wèn)題之前——?jiǎng)討B(tài)規(guī)劃法的概念 203
11．2　斐波那契數(shù)列 204
11．3　最長(zhǎng)公共子序列 208
11．4　矩陣鏈乘法 211
第12章　圖 217
12．1　挑戰(zhàn)問(wèn)題之前——圖 218
12．2　圖的表示 221
12．3　深度優(yōu)先搜索 224
12．4　廣度優(yōu)先搜索 232
12．5　連通分量 237
第13章　加權(quán)圖 241
13．1　挑戰(zhàn)問(wèn)題之前——加權(quán)圖 242
13．2　最小生成樹 244
13．3　單源最短路徑 249
第3部分　[應(yīng)用篇]程序設(shè)計(jì)競(jìng)賽的必備程序庫(kù) 261
第14章　高等數(shù)據(jù)結(jié)構(gòu) 263
14．1　互質(zhì)的集合 264
14．2　范圍搜索 269
14．3　其他問(wèn)題 278
第15章　高等圖算法 279
15．1　所有點(diǎn)對(duì)間最短路徑 280
15．2　拓?fù)渑判?284
15．3　關(guān)節(jié)點(diǎn) 290
15．4　樹的直徑 295
15．5　最小生成樹 299
15．6　其他問(wèn)題 303
第16章　計(jì)算幾何學(xué) 305
16．1　幾何對(duì)象的基本元素與表現(xiàn) 306
16．2　直線的正交/平行判定 312
16．3　投影 314
16．4　映象 316
16．5　距離 317
16．6　逆時(shí)針?lè)较?321
16．7　判斷線段相交 324
16．8　線段的交點(diǎn) 326
16．9　圓與直線的交點(diǎn) 328
16．10　圓與圓的交點(diǎn) 331
16．11　點(diǎn)的內(nèi)包 333
16．12　凸包 335
16．13　線段相交問(wèn)題 339
16．14　其他問(wèn)題 343
第17章　動(dòng)態(tài)規(guī)劃法 345
17．1　硬幣問(wèn)題 346
17．2　背包問(wèn)題 349
17．3　最長(zhǎng)遞增子序列 353
17．4　最大正方形 357
17．5　最大長(zhǎng)方形 360
17．6　其他問(wèn)題 364
第18章　數(shù)論 367
18．1　質(zhì)數(shù)檢驗(yàn) 368
18．2　最大公約數(shù) 372
18．3　冪乘 376
18．4　其他問(wèn)題 378
第19章　啟發(fā)式搜索 381
19．1　八皇后問(wèn)題 382
19．2　九宮格拼圖 386
19．3　十六格拼圖 391
附錄 399
通過(guò)本書可以獲得的技能 400
挑戰(zhàn)以往的程序設(shè)計(jì)競(jìng)賽真題！ 402
參考文獻(xiàn) 404