本書是針對大學(xué)生程序設(shè)計競賽的訓(xùn)練指南, 主要介紹程序設(shè)計和針對競賽訓(xùn)練所需的基礎(chǔ)知識和基本數(shù)學(xué)概念, 包括UVa OJ平臺的使用方法、C++的輸入輸出處理、C++庫實現(xiàn)所包含的數(shù)據(jù)結(jié)構(gòu)、高級數(shù)據(jù)結(jié)構(gòu)、字符串的處理和相關(guān)算法、排序與查找算法、代數(shù)、組合數(shù)學(xué)、數(shù)論、幾何等內(nèi)容。本書在介紹基礎(chǔ)概念的基礎(chǔ)上, 引入了眾多題目, 以C++解題, 針對部分題目給出參考代碼, 方便參考和練習(xí)。

邱秋, 大學(xué)期間自學(xué)計算機(jī)技術(shù), 工作期間曾開發(fā)數(shù)字營區(qū)、局域網(wǎng)考核、患者健康隨訪等用途的多款軟件。

目錄
第 1章 準(zhǔn)備 1
1.1 什么是程序設(shè)計競賽 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 注冊 3
1.2.2 提交 3
1.3 如何選擇編程語言 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章 入門 8
2.1 基本數(shù)據(jù)類型 8
2.1.1 整數(shù)的表示 8
2.1.2 浮點數(shù)的表示及精度 9
2.1.3 數(shù)據(jù)類型的取值范圍 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 輸出對齊 20
2.3.3 整數(shù)輸出 20
2.3.4 實數(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 約瑟夫問題 30
3.2 向量 34
3.3 棧 37
3.4 隊列及優(yōu)先隊列 41
3.4.1 隊列 41
3.4.2 優(yōu)先隊列 44
3.5 雙端隊列 46
3.6 映射 48
3.7 集合 52
3.8 位集 55
3.9 鏈表 58
3.10 二叉樹 59
3.11 范圍查詢 64
3.11.1 線段樹 64
3.11.2 二維線段樹 70
3.11.3 區(qū)間樹 76
3.11.4 樹狀數(shù)組 77
3.11.5 稀疏表 80
3.11.6 根號分塊 81
3.12 并查集 85
3.13 算法庫函數(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 字符串類 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 字符串庫函數(shù) 99
4.4 字符串類應(yīng)用 101
4.4.1 文本解析 101
4.4.2 語法分析 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 長公共子串 131
4.5.5 長重復(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 字符類和可選模式 137
4.6.5 斷言 138
4.6.6 正則表達(dá)式類 138
4.7 算法庫函數(shù) 139
4.7.1 lexicographical_compare 139
4.7.2 next_permutation和prev_
permutation 140
4.7.3 rece 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 計數(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 大值小化問題 159
5.8.5 三分搜索 160
5.9 算法庫函數(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 le_sort 171
5.9.8 unique 172
5.10 小結(jié) 173
第6章 算術(shù)與代數(shù) 174
6.1 割雞焉用牛刀乎 174
6.2 他山之石，可以攻玉 180
6.3 高精度整數(shù)類的實現(xiàn) 182
6.4制及其轉(zhuǎn)換 190
6.4.1 制數(shù)轉(zhuǎn)換為制數(shù) 190
6.4.2 制數(shù)轉(zhuǎn)換為制數(shù) 191
6.4.3 任制數(shù)之間的相互轉(zhuǎn)換 192
6.4.4 羅馬計數(shù)法 193
6.5 實數(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ù)大小的比較 200
6.6 代數(shù) 201
6.6.1 多項式運算 201
6.6.2 高斯消元法 202
6.7 冪與對數(shù) 209
6.8 實數(shù)函數(shù)庫 211
6.9 小結(jié) 212
第7章 組合數(shù)學(xué) 213
7.1 計數(shù)原理 213
7.1.1 加法原理 213
7.1.2 乘法原理 214
7.2 排列與組合 216
7.2.1 康托展開和康托逆展開 217
7.2.2 方程的整數(shù)解個數(shù) 222
7.3 Pólya計數(shù)定理 223
7.3.1 基本概念 223
7.3.2 Burnside引理 228
7.3.3 Pólya計數(shù)定理 231
7.4 鴿籠原理 236
7.4.1 拉姆齊理論 238
7.5 容斥原理 238
7.5.1 錯排問題 239
7.6 初等數(shù)列 240
7.6.1 等差數(shù)列 240
7.6.2 等比數(shù)列 240
7.6.3 其他數(shù)列 240
7.7 計數(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)和級數(shù) 249
7.7.6 其他序列 250
7.8 概率論 251
7.8.1 基本概念 251
7.8.2 條件概率和獨立事件 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 素數(shù) 283
8.1.1 素數(shù)判定 284
8.1.2 米勒-拉賓素性測試 285
8.1.3 高斯素數(shù) 287
8.1.4 生成素數(shù)序列 288
8.1.5 素因子分解 291
8.2 整除性 292
8.2.1 大公約數(shù) 292
8.2.2 擴(kuò)展歐幾里得算法 295
8.2.3 線性同余方程 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 可樂兌換 306
8.3.3 模運算規(guī)則 306
8.3.4 模的逆元 307
8.3.5 離散對數(shù) 309
8.3.6 中國剩余定理 310
8.3.7 波拉德ρ啟發(fā)式因子分解
算法 311
8.4 日期和時間轉(zhuǎn)換 313
8.4.1 日期轉(zhuǎn)換 313
8.4.2 時間轉(zhuǎn)換 317
8.5 小結(jié) 318
第9章 幾何 319
9.1 點 319
9.2 直線 320
9.2.1 直線的表示 320
9.2.2 直線間關(guān)系 321
9.2.3 相互垂直的兩條直線交點 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ù)庫 336
9.4.7 桌球碰撞問題 337
9.5 多邊形 339
9.5.1 矩形 339
9.5.2 四邊形和正多邊形 341
9.6 圓 341
9.6.1 圓的周長和面積 342
9.6.2 圓的切線 343
9.6.3 三角形的內(nèi)切圓與外接圓 345
9.6.4 圓與圓的位置關(guān)系 347
9.6.5 小圓覆蓋 351
9.7 小結(jié) 352
第 10章 計算幾何 353
10.1 基本概念 353
10.1.1 線段 353
10.1.2 多邊形 353
10.2 幾何對象間的關(guān)系 354
10.2.1 向量、內(nèi)積和外積 354
10.2.2 點和直線的關(guān)系 356
10.2.3 確定線段轉(zhuǎn)動方向 358
10.2.4 確定線段是否相交 359
10.2.5 點的投影 362
10.2.6 點的映像 364
10.2.7 點和直線間距離 364
10.2.8 點和線段間距離 365
10.2.9 線段和線段間距離 366
10.2.10 點和多邊形的關(guān)系 366
10.2.11 直線和圓的交點 369
10.2.12 圓和圓的交點 370
10.2.13 圓的切點 370
10.3 掃描線算法 371
10.4 坐標(biāo)離散化 373
10.4.1 大化矩形問題 376
10.4.2 矩形并的面積 377
10.4.3 矩形并的周長 379
10.5 383
10.5.1 Graham掃描法 383
10.5.2 Jarvis法 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 面交問題 396
10.7.1 凸多邊形切分 396
10.7.2 多邊形內(nèi)核 401
10.8 點對問題 402
10.9 遠(yuǎn)點對問題 405
10.10 三維空間計算幾何 409
10.10.1 點 410
10.10.2 直線 411
10.10.3面 414
10.10.2 三維 419
10.11 小結(jié) 423
附錄 425
1 ASCII表 425
2 C++運算符優(yōu)先級 426
3 引 426
參考資料 427