程序設計競賽訓練營 : 基礎與數學概念

本書是針對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