程序設(shè)計(jì)競(jìng)賽訓(xùn)練營(yíng)：基礎(chǔ)與數(shù)學(xué)概念

目錄

第　1章 準(zhǔn)備　1
1.1　什么是程序設(shè)計(jì)競(jìng)賽　1
1.1.1　ACM-ICPC　1
1.1.2　Google Code Jam（GCJ）　1
1.1.3　TopCoder　2
1.1.4　CodeForces　2
1.1.5　IOI　2
1.2　如何使用UVa OJ　3
1.2.1　注冊(cè)　3
1.2.2　提交　3
1.3　如何選擇編程語(yǔ)言　6
1.4　輔助工具　6
1.3.1　UVa Arena　6
1.3.2　uHunt　6
1.3.3　uDebug　6
1.3.4　VirtualBox　6
1.3.5　Virtual Judge　7
1.3.6　洛谷　7
第　2章 入門(mén)　8
2.1　基本數(shù)據(jù)類(lèi)型　8
2.1.1　整數(shù)的表示　8
2.1.2　浮點(diǎn)數(shù)的表示及精度　9
2.1.3　數(shù)據(jù)類(lèi)型的取值范圍　12
2.2　格式化輸入　13
2.2.1　概述　13
2.2.2　標(biāo)準(zhǔn)輸入　14
2.2.3　字符串輸入　15
2.3　格式化輸出　18
2.3.1　概述　18
2.3.2　輸出對(duì)齊　20
2.3.3　整數(shù)輸出　20
2.3.4　實(shí)數(shù)輸出　21
2.3.5　緩沖區(qū)與輸入輸出同步　24
2.4　小結(jié)　26

第3章　數(shù)據(jù)結(jié)構(gòu)　27
3.1　內(nèi)置數(shù)組　27
3.1.1　順序記錄　27
3.1.2　游戲模擬　29
3.1.3　矩陣變換　30
3.1.4　約瑟夫問(wèn)題　30
3.2　向量　34
3.3　?！?7
3.4　隊(duì)列及優(yōu)先隊(duì)列　41
3.4.1　隊(duì)列　41
3.4.2　優(yōu)先隊(duì)列　44
3.5　雙端隊(duì)列　46
3.6　映射　48
3.7　集合　52
3.8　位集　55
3.9　鏈表　58
3.10　二叉樹(shù)　59
3.11　范圍查詢(xún)　64
3.11.1　線(xiàn)段樹(shù)　64
3.11.2　二維線(xiàn)段樹(shù)　70
3.11.3　區(qū)間樹(shù)　76
3.11.4　樹(shù)狀數(shù)組　77
3.11.5　稀疏表　80
3.11.6　根號(hào)分塊　81
3.12　并查集　85
3.13　算法庫(kù)函數(shù)　87
3.13.1　accumulate和count、
　count_if　87
3.13.2　copy和reverse_copy　88
3.13.3　fill　88
3.13.4　iotac 11　89
3.13.5　max和min　89
3.13.6　max_element和min_element　90
3.13.7　memcpy和memset　90
3.14　小結(jié)　92

第4章　字符串　93
4.1　編碼　93
4.2　字符串類(lèi)　94
4.2.1　聲明　95
4.2.2　賦值　96
4.2.3　遍歷　96
4.2.4　連接與刪除　97
4.2.5　查找與替換　98
4.2.6　其他操作　99
4.3　字符串庫(kù)函數(shù)　99
4.4　字符串類(lèi)應(yīng)用　101
4.4.1　文本解析　101
4.4.2　語(yǔ)法分析　105
4.4.3　KMP匹配算法　108
4.4.4　擴(kuò)展KMP匹配算法　114
4.4.5　Z算法　116
4.4.6　字符串的小表示　117
4.5　字符串?dāng)?shù)據(jù)結(jié)構(gòu)及應(yīng)用　118
4.5.1　Trie　118
4.5.2　Aho-Corasick算法　119
4.5.3　后綴數(shù)組　124
4.5.4　長(zhǎng)公共子串　131
4.5.5　長(zhǎng)重復(fù)子串　134
4.5.6　Burrows-Wheeler變換　135
4.6　正則表達(dá)式　136
4.6.1　元字符　136
4.6.2　轉(zhuǎn)義字符　137
4.6.3　數(shù)量匹配符和分組　137
4.6.4　字符類(lèi)和可選模式　137
4.6.5　斷言　138
4.6.6　正則表達(dá)式類(lèi)　138
4.7　算法庫(kù)函數(shù)　139
4.7.1　lexicographical_compare　139
4.7.2　next_permutation和prev_
　permutation　140
4.7.3　replace　143
4.7.4　reverse　143
4.7.5　transform　144
4.8　小結(jié)　144
第5章　排序與查找　145
5.1　交換排序　145
5.1.1　冒泡排序　145
5.1.2　快速排序　146
5.1.3　中位數(shù)　147
5.2　插入排序　149
5.2.1　直接插入排序　149
5.2.2　希爾排序　149
5.3　選擇排序　150
5.3.1　直接選擇排序　150
5.3.2　堆排序　150
5.4　歸并排序　151
5.4.1　逆序?qū)?shù)　151
5.5　計(jì)數(shù)排序　153
5.6　基數(shù)排序　153
5.7　桶排序　155
5.8　查找　155
5.8.1　順序查找　155
5.8.2　二分查找　156
5.8.3　方程求近似解　157
5.8.4　值小化問(wèn)題　159
5.8.5　三分搜索　160
5.9　算法庫(kù)函數(shù)　162
5.9.1　binary_search　162
5.9.2　find　162
5.9.3　lower_bound和upper_bound　163
5.9.4　nth_element　167
5.9.5　partial_sort　168
5.9.6　sort　168
5.9.7　stable_sort　171
5.9.8　unique　172
5.10　小結(jié)　173
第6章　算術(shù)與代數(shù)　174
6.1　割雞焉用牛刀乎　174
6.2　他山之石，可以攻玉　180
6.3　高精度整數(shù)類(lèi)的實(shí)現(xiàn)　182
6.4　進(jìn)制及其轉(zhuǎn)換　190
6.4.1　R進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)　190
6.4.2　十進(jìn)制數(shù)轉(zhuǎn)換為R進(jìn)制數(shù)　191
6.4.3　任意進(jìn)制數(shù)之間的相互轉(zhuǎn)換　192
6.4.4　羅馬計(jì)數(shù)法　193
6.5　實(shí)數(shù)　195
6.5.1　分?jǐn)?shù)　195
6.5.2　連續(xù)分?jǐn)?shù)　198
6.5.3　分?jǐn)?shù)轉(zhuǎn)換為小數(shù)　198
6.5.4　小數(shù)轉(zhuǎn)換為分?jǐn)?shù)　199
6.5.5　實(shí)數(shù)大小的比較　200
6.6　代數(shù)　201
6.6.1　多項(xiàng)式運(yùn)算　201
6.6.2　高斯消元法　202
6.7　冪與對(duì)數(shù)　209
6.8　實(shí)數(shù)函數(shù)庫(kù)　211
6.9　小結(jié)　212
第7章　組合數(shù)學(xué)　213
7.1　計(jì)數(shù)原理　213
7.1.1　加法原理　213
7.1.2　乘法原理　214
7.2　排列與組合　216
7.2.1　康托展開(kāi)和康托逆展開(kāi)　217
7.2.2　方程的整數(shù)解個(gè)數(shù)　222
7.3　Pólya計(jì)數(shù)定理　223
7.3.1　基本概念　223
7.3.2　Burnside引理　228
7.3.3　Pólya計(jì)數(shù)定理　231
7.4　鴿籠原理　236
7.4.1　拉姆齊理論　238
7.5　容斥原理　238
7.5.1　錯(cuò)排問(wèn)題　239
7.6　初等數(shù)列　240
7.6.1　等差數(shù)列　240
7.6.2　等比數(shù)列　240
7.6.3　其他數(shù)列　240
7.7　計(jì)數(shù)序列　241
7.7.1　斐波那契數(shù)　241
7.7.2　卡特蘭數(shù)　245
7.7.3　歐拉數(shù)　248
7.7.4　斯特林?jǐn)?shù)　248
7.7.5　調(diào)和級(jí)數(shù)　249
7.7.6　其他序列　250
7.8　概率論　251
7.8.1　基本概念　251
7.8.2　條件概率和獨(dú)立事件　254
7.8.3　全概率公式與貝葉斯公式　256
7.8.4　隨機(jī)變量　260
7.8.5　期望　261
7.9　博弈論　269
7.9.1　Nim游戲　270
7.9.2　Sprague-Grundy定理　272
7.9.3　Nim游戲和Sprague-Grundy定理
　擴(kuò)展　273
7.9.4　PN態(tài)分析　278
7.10　小結(jié)　282
第8章　數(shù)論　283
8.1　素?cái)?shù)　283
8.1.1　素?cái)?shù)判定　284
8.1.2　米勒-拉賓素性測(cè)試　285
8.1.3　高斯素?cái)?shù)　287
8.1.4　生成素?cái)?shù)序列　288
8.1.5　素因子分解　291
8.2　整除性　292
8.2.1　公約數(shù)　292
8.2.2　擴(kuò)展歐幾里得算法　295
8.2.3　線(xiàn)性同余方程　297
8.2.4　小公倍數(shù)　298
8.2.5　歐拉函數(shù)　299
8.2.6　莫比烏斯函數(shù)　303
8.3　模算術(shù)　305
8.3.1　整數(shù)拆分　306
8.3.2　可樂(lè)兌換　306
8.3.3　模運(yùn)算規(guī)則　306
8.3.4　模的逆元　307
8.3.5　離散對(duì)數(shù)　309
8.3.6　中國(guó)剩余定理　310
8.3.7　波拉德ρ啟發(fā)式因子分解
　算法　311
8.4　日期和時(shí)間轉(zhuǎn)換　313
8.4.1　日期轉(zhuǎn)換　313
8.4.2　時(shí)間轉(zhuǎn)換　317
8.5　小結(jié)　318
第9章　幾何　319
9.1　點(diǎn)　319
9.2　直線(xiàn)　320
9.2.1　直線(xiàn)的表示　320
9.2.2　直線(xiàn)間關(guān)系　321
9.2.3　相互垂直的兩條直線(xiàn)交點(diǎn)　322
9.3　坐標(biāo)和坐標(biāo)系變換　322
9.3.1　平移　322
9.3.2　旋轉(zhuǎn)　323
9.3.3　縮放　325
9.4　三角形　329
9.4.1　勾股定理　329
9.4.2　三角函數(shù)　331
9.4.3　正弦定理　332
9.4.4　余弦定理　332
9.4.5　三角形面積　334
9.4.6　三角函數(shù)庫(kù)　336
9.4.7　桌球碰撞問(wèn)題　337
9.5　多邊形　339
9.5.1　矩形　339
9.5.2　四邊形和正多邊形　341
9.6　圓　341
9.6.1　圓的周長(zhǎng)和面積　342
9.6.2　圓的切線(xiàn)　343
9.6.3　三角形的內(nèi)切圓與外接圓　345
9.6.4　圓與圓的位置關(guān)系　347
9.6.5　小圓覆蓋　351
9.7　小結(jié)　352
第　10章 計(jì)算幾何　353
10.1　基本概念　353
10.1.1　線(xiàn)段　353
10.1.2　多邊形　353
10.2　幾何對(duì)象間的關(guān)系　354
10.2.1　向量、內(nèi)積和外積　354
10.2.2　點(diǎn)和直線(xiàn)的關(guān)系　356
10.2.3　確定線(xiàn)段轉(zhuǎn)動(dòng)方向　358
10.2.4　確定線(xiàn)段是否相交　359
10.2.5　點(diǎn)的投影　362
10.2.6　點(diǎn)的映像　364
10.2.7　點(diǎn)和直線(xiàn)間距離　364
10.2.8　點(diǎn)和線(xiàn)段間距離　365
10.2.9　線(xiàn)段和線(xiàn)段間距離　366
10.2.10　點(diǎn)和多邊形的關(guān)系　366
10.2.11　直線(xiàn)和圓的交點(diǎn)　369
10.2.12　圓和圓的交點(diǎn)　370
10.2.13　圓的切點(diǎn)　370
10.3　掃描線(xiàn)算法　371
10.4　坐標(biāo)離散化　373
10.4.1　化矩形問(wèn)題　376
10.4.2　矩形并的面積　377
10.4.3　矩形并的周長(zhǎng)　379
10.5　凸包　383
10.5.1　Graham掃描法　383
10.5.2　Jarvis步進(jìn)法　387
10.5.3　Andrew合并法　389
10.5.4　Melkman算法　391
10.6　公式及定理應(yīng)用　392
10.6.1　Pick定理　392
10.6.2　多邊形面積　393
10.6.3　多邊形重心　393
10.6.4　三維幾何體的表面積和體積　395
10.7　半平面交問(wèn)題　396
10.7.1　凸多邊形切分　396
10.7.2　多邊形內(nèi)核　401
10.8　近點(diǎn)對(duì)問(wèn)題　402
10.9　遠(yuǎn)點(diǎn)對(duì)問(wèn)題　405
10.10　三維空間計(jì)算幾何　409
10.10.1　點(diǎn)　410
10.10.2　直線(xiàn)　411
10.10.3　平面　414
10.10.2　三維凸包　419
10.11　小結(jié)　423
附錄　425
1　ASCII表　425
2　C 運(yùn)算符優(yōu)先級(jí)　426
3　習(xí)題索引　426
參考資料　427