程序設計競賽訓練營 : 基礎與數學概念
邱秋
買這商品的人也買了...
-
$281高效算法 競賽 應試與提高必修128例
-
$403ACM 大學生程序設計競賽在線題庫最新精選題解
-
$305算法競賽入門到進階
-
$288$274 -
$708$673 -
$588$559 -
$779$740 -
$254和秋葉一起學 秒懂 Excel (全彩版)
-
$254和秋葉一起學 秒懂 Word (全彩版)
-
$254和秋葉一起學 秒懂 PPT (全彩版)
-
$403算法設計與分析——以ACM大學生程序設計競賽在線題庫為例(微課版)
-
$407區塊鏈原理、技術及應用
-
$352開啟人工智能之門 — 運用 Excel 體驗學 AI (原書第2版)
-
$611ARM64 體系結構編程與實踐
-
$599$569 -
$407區塊鏈技術及應用
-
$6115G + AI 融合全景圖
-
$594$564 -
$580$458 -
$480$379 -
$620$490 -
$300$237 -
$454算法設計與分析——基於C++編程語言的描述
-
$390$308 -
$720$562
相關主題
商品描述
本書是針對ACM主辦的國際大學生程序設計競賽的訓練指南,主要介紹程序設計和針對競賽訓練所需的基礎知識和基本數學概念,包括UVa OJ平臺的使用方法、C++的輸入輸出處理、C++庫實現所包含的數據結構、高級數據結構、字符串的處理和相關算法、排序與查找算法、代數、組合數學、數論、幾何等內容。本書在介紹基礎概念的基礎上,引入了眾多題目,以C++解題,針對部分題目給出參考代碼,方便參考和練習。
本書適合有意參加國際大學生程序設計競賽的本科生、研究生閱讀,對有意參加國際信息學奧林匹克競賽的中學生具有參考價值,也可作為電腦專業相關課程的參考教材。
作者簡介
邱秋,大学期间自学计算机技术,并于2004年和2006年分别取得了全国计算机技术与软件专业技术资格考试中的程序员和软件工程师的证书。对数据库技术感兴趣,在住院医师实习期间曾帮助科室开发了一款对肾衰竭腹膜透析患者进行健康随访的软件,在工作期间开发了数字营区、局域网考核等软件。爱好算法,酷爱读书。
目錄大綱
目錄
第 1章 準備 1
1.1 什麽是程序設計競賽 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 基本數據類型 8
2.1.1 整數的表示 8
2.1.2 浮點數的表示及精度 9
2.1.3 數據類型的取值範圍 12
2.2 格式化輸入 13
2.2.1 概述 13
2.2.2 標準輸入 14
2.2.3 字符串輸入 15
2.3 格式化輸出 18
2.3.1 概述 18
2.3.2 輸出對齊 20
2.3.3 整數輸出 20
2.3.4 實數輸出 21
2.3.5 緩沖區與輸入輸出同步 24
2.4 小結 26
第3章 數據結構 27
3.1 內置數組 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 隊列及優先隊列 41
3.4.1 隊列 41
3.4.2 優先隊列 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 區間樹 76
3.11.4 樹狀數組 77
3.11.5 稀疏表 80
3.11.6 根號分塊 81
3.12 並查集 85
3.13 算法庫函數 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 小結 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 字符串庫函數 99
4.4 字符串類應用 101
4.4.1 文本解析 101
4.4.2 語法分析 105
4.4.3 KMP匹配算法 108
4.4.4 擴展KMP匹配算法 114
4.4.5 Z算法 116
4.4.6 字符串的最小表示 117
4.5 字符串數據結構及應用 118
4.5.1 Trie 118
4.5.2 Aho-Corasick算法 119
4.5.3 後綴數組 124
4.5.4 最長公共子串 131
4.5.5 最長重復子串 134
4.5.6 Burrows-Wheeler變換 135
4.6 正則表達式 136
4.6.1 元字符 136
4.6.2 轉義字符 137
4.6.3 數量匹配符和分組 137
4.6.4 字符類和可選模式 137
4.6.5 斷言 138
4.6.6 正則表達式類 138
4.7 算法庫函數 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 小結 144
第5章 排序與查找 145
5.1 交換排序 145
5.1.1 冒泡排序 145
5.1.2 快速排序 146
5.1.3 中位數 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 逆序對數 151
5.5 計數排序 153
5.6 基數排序 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 算法庫函數 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 小結 173
第6章 算術與代數 174
6.1 割雞焉用牛刀乎 174
6.2 他山之石,可以攻玉 180
6.3 高精度整數類的實現 182
6.4 進制及其轉換 190
6.4.1 R進制數轉換為十進制數 190
6.4.2 十進制數轉換為R進制數 191
6.4.3 任意進制數之間的相互轉換 192
6.4.4 羅馬計數法 193
6.5 實數 195
6.5.1 分數 195
6.5.2 連續分數 198
6.5.3 分數轉換為小數 198
6.5.4 小數轉換為分數 199
6.5.5 實數大小的比較 200
6.6 代數 201
6.6.1 多項式運算 201
6.6.2 高斯消元法 202
6.7 冪與對數 209
6.8 實數函數庫 211
6.9 小結 212
第7章 組合數學 213
7.1 計數原理 213
7.1.1 加法原理 213
7.1.2 乘法原理 214
7.2 排列與組合 216
7.2.1 康托展開和康托逆展開 217
7.2.2 方程的整數解個數 222
7.3 Pólya計數定理 223
7.3.1 基本概念 223
7.3.2 Burnside引理 228
7.3.3 Pólya計數定理 231
7.4 鴿籠原理 236
7.4.1 拉姆齊理論 238
7.5 容斥原理 238
7.5.1 錯排問題 239
7.6 初等數列 240
7.6.1 等差數列 240
7.6.2 等比數列 240
7.6.3 其他數列 240
7.7 計數序列 241
7.7.1 斐波那契數 241
7.7.2 卡特蘭數 245
7.7.3 歐拉數 248
7.7.4 斯特林數 248
7.7.5 調和級數 249
7.7.6 其他序列 250
7.8 概率論 251
7.8.1 基本概念 251
7.8.2 條件概率和獨立事件 254
7.8.3 全概率公式與貝葉斯公式 256
7.8.4 隨機變量 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定理
擴展 273
7.9.4 PN態分析 278
7.10 小結 282
第8章 數論 283
8.1 素數 283
8.1.1 素數判定 284
8.1.2 米勒-拉賓素性測試 285
8.1.3 高斯素數 287
8.1.4 生成素數序列 288
8.1.5 素因子分解 291
8.2 整除性 292
8.2.1 最大公約數 292
8.2.2 擴展歐幾里得算法 295
8.2.3 線性同餘方程 297
8.2.4 最小公倍數 298
8.2.5 歐拉函數 299
8.2.6 莫比烏斯函數 303
8.3 模算術 305
8.3.1 整數拆分 306
8.3.2 可樂兌換 306
8.3.3 模運算規則 306
8.3.4 模的逆元 307
8.3.5 離散對數 309
8.3.6 中國剩餘定理 310
8.3.7 波拉德ρ啟發式因子分解
算法 311
8.4 日期和時間轉換 313
8.4.1 日期轉換 313
8.4.2 時間轉換 317
8.5 小結 318
第9章 幾何 319
9.1 點 319
9.2 直線 320
9.2.1 直線的表示 320
9.2.2 直線間關系 321
9.2.3 相互垂直的兩條直線交點 322
9.3 坐標和坐標系變換 322
9.3.1 平移 322
9.3.2 旋轉 323
9.3.3 縮放 325
9.4 三角形 329
9.4.1 勾股定理 329
9.4.2 三角函數 331
9.4.3 正弦定理 332
9.4.4 餘弦定理 332
9.4.5 三角形面積 334
9.4.6 三角函數庫 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 三角形的內切圓與外接圓 345
9.6.4 圓與圓的位置關系 347
9.6.5 最小圓覆蓋 351
9.7 小結 352
第 10章 計算幾何 353
10.1 基本概念 353
10.1.1 線段 353
10.1.2 多邊形 353
10.2 幾何對象間的關系 354
10.2.1 向量、內積和外積 354
10.2.2 點和直線的關系 356
10.2.3 確定線段轉動方向 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 點和多邊形的關系 366
10.2.11 直線和圓的交點 369
10.2.12 圓和圓的交點 370
10.2.13 圓的切點 370
10.3 掃描線算法 371
10.4 坐標離散化 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 公式及定理應用 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 多邊形內核 401
10.8 最近點對問題 402
10.9 最遠點對問題 405
10.10 三維空間計算幾何 409
10.10.1 點 410
10.10.2 直線 411
10.10.3 平面 414
10.10.2 三維凸包 419
10.11 小結 423
附錄 425
1 ASCII表 425
2 C++運算符優先級 426
3 習題索引 426
參考資料 427