程序設計競賽專題挑戰教程

內容提要

　　本書面向藍橋杯全國軟件和信息技術專業人才大賽的軟件類賽項（以下簡稱藍橋杯軟件類大賽），從數據結構和算法的維度幫助廣大讀者訓練編程思維和計算思維，掌握編程方法和解題技巧。

　　本書共10章，第1章主要介紹了藍橋杯軟件類大賽的基本情況，歸類匯總了其涉及的知識點（包括算法知識點），詳細介紹了其在線評測系統以說明評分情況。第2~10章則由淺入深、由易到難地介紹了各類知識點，包括手算題和雜題、基礎數據結構、基本算法、搜索、高級數據結構、動態規劃、數學、字符串、圖論等，對於每一類知識點都簡明扼要地進行說明，並以真題作為例題進行細致講解，以更好地幫助讀者實現學用結合的學習效果。需要特別說明的是，本書例題的代碼部分，分別由C++、Python、Java三種語言來實現（書中僅提供以C++、Python語言編寫的代碼，以Java語言編寫的代碼可從本書的配套數字資源中獲取）。

　　本書不僅適合作為藍橋杯軟件類大賽參賽者的備賽用書，還適用於備賽其他編程或算法類大賽（如全國青少年信息學奧林匹克競賽NOI、國際大學生程序設計競賽ICPC、中國大學生程序設計競賽CCPC、中國高校電腦大賽?團體程序設計天梯賽GPLT等）。此外，本書還可作為本科生和研究生的相關算法課程的教材或參考資料。

　

罗勇军

上海交通大学计算机系博士毕业，现为华东理工大学计算机系教师。担任华东理工大学程序设计竞赛主教练 16 年，指导学生参加国际大学生程序设计竞赛 ICPC、中国大学生程序设计竞赛 CCPC、蓝桥杯大赛，成绩优异，曾两次带队参加 ICPC 全球总决赛。每年指导数百名学生参加蓝桥杯大赛。

杨培林

高级工程师，国信蓝桥教育科技股份有限公司教学总监，曾担任多所大学算法团队教练，参与多所大学的教学方案制订，线上课程的研发设计与教学工作。通过 10 多年以来的孜孜追求和学习，形成了自己独特的教育教学方式。对技术的学习和跟进一直没有停歇，在教育教学活动中把学习的方法、技巧、经验和知识传授给学生，让自己和学生共享学习的快乐，共同收获学习的成果。

目 錄

第 1章　藍橋杯軟件類大賽介紹　1

1.1　藍橋杯軟件類大賽的競賽規則　1

1.2　競賽題示例　4

1.3　算法知識點總覽　5

1.4　歷年真題知識點統計　7

1.5　藍橋杯軟件類大賽的評測系統　9

小結　12

第 2章　手算題和雜題　13

2.1　手算題攻略　13

2.1.1　巧用編輯器　13

2.1.2　眼看手數　14

2.1.3　巧用Excel　16

2.1.4　巧用Python　17

2.2　雜題　22

小結　32

第3章　基礎數據結構　33

3.1　數組　33

3.2　鏈表　37

3.2.1　C++鏈表實現　38

3.2.2　Python鏈表實現　42

3.3　隊列　44

3.3.1　C++普通隊列　44

3.3.2　Python普通隊列　47

3.3.3　C++優先隊列　49

3.3.4　Python優先隊列　51

3.4　棧　51

3.4.1　C++棧的實現　52

3.4.2　Python棧的實現　55

3.4.3　例題　57

3.5　二叉樹　59

3.5.1　二叉樹的定義　60

3.5.2　二叉樹的存儲　60

3.5.3　二叉樹的遍歷　61

3.5.4　例題　63

小結　66

第4章　基本算法　67

4.1　算法復雜度　67

4.1.1　算法的概念　67

4.1.2　計算資源　68

4.1.3　選擇解題方法　69

4.1.4　算法復雜度概述　71

4.2　排序　73

4.2.1　C++的sort()函數　73

4.2.2　Python的sort()和sorted()函數　74

4.2.3　Java的sort()函數　75

4.2.4　例題　75

4.3　排列和組合　87

4.3.1　C++的全排列函數next_permutation()　88

4.3.2　Python的排列函數permutations()　89

4.3.3　Python的組合函數combinations()　89

4.3.4　手寫排列和組合代碼　90

4.3.5　例題　92

4.4　尺取法　97

4.4.1　尺取法的概念　97

4.4.2　反向掃描　98

4.4.3　同向掃描　99

4.5　二分法　102

4.5.1　二分法的概念　102

4.5.2　整數二分　103

4.5.3　整數二分例題　104

4.5.4　實數二分　112

4.6　倍增法和ST算法　114

4.6.1　用暴力法解決區間問題　115

4.6.2　ST算法　116

4.6.3　ST算法的模板代碼　118

4.7　前綴和　119

4.8　貪心算法　124

小結　132

第5章　搜索　133

5.1　DFS基礎　134

5.1.1　遞歸和記憶化搜索　134

5.1.2　DFS的代碼框架　136

5.1.3　DFS的所有路徑　137

5.1.4　DFS與排列組合　140

5.1.5　DFS應用詳解　143

5.1.6　DFS真題　147

5.2　BFS基礎　152

5.2.1　BFS的原理　152

5.2.2　BFS與最短路徑　154

5.3　連通性判斷　158

5.3.1　DFS連通性判斷　159

5.3.2　BFS連通性判斷　161

5.3.3　連通性例題　163

5.4　BFS與判重　168

5.5　雙向廣搜　171

5.6　剪枝　174

小結　182

第6章　高級數據結構　183

6.1　並查集　183

6.1.1　用並查集檢查連通性　183

6.1.2　並查集的基本操作　185

6.1.3　路徑壓縮　188

6.1.4　例題　189

6.2　樹狀數組　197

6.2.1　區間和問題　197

6.2.2　樹狀數組的原理　199

6.2.3　lowbit()　201

6.2.4　樹狀數組的代碼　202

6.2.5　逆序對問題　203

6.3　線段樹　207

6.3.1　線段樹的概念　208

6.3.2　區間查詢　209

6.3.3　區間查詢例題　214

6.3.4　區間修改和懶惰標記　221

小結　226

第7章　動態規劃　227

7.1　動態規劃的概念　227

7.2　動態規劃基礎　228

7.3　線性DP　235

7.4　狀態壓縮DP　247

7.4.1　狀態壓縮DP的概念　247

7.4.2　狀態壓縮DP的原理　249

7.4.3　位運算　249

7.4.4　例題　250

7.5　樹形DP　255

7.6　數位DP　259

小結　264

第8章　數學　265

8.1　模運算　265

8.2　快速冪　266

8.3　矩陣乘法　271

8.4　矩陣快速冪　273

8.5　GCD和LCM　278

8.5.1　GCD的定義和性質　278

8.5.2　GCD的編程實現　278

8.5.3　LCM　279

8.5.4　例題　280

8.6　素數　286

8.6.1　素數的判斷　287

8.6.2　素數的篩選　290

8.6.3　區間素數　294

8.6.4　分解質因子　295

8.7　組合數學　297

8.7.1　基本計數　297

8.7.2　鴿巢原理　301

8.7.3　二項式定理和楊輝三角　302

8.8　幾何　304

8.8.1　普通幾何題　305

8.8.2　點和向量　306

8.8.3　點積和叉積　307

8.8.4　點和線的關系　310

小結　314

第9章　字符串　316

9.1　字符串函數　316

9.1.1　C++的字符串函數　316

9.1.2　Python的字符串處理　317

9.1.3　Java的字符串函數　318

9.2　簡單字符串例題　319

9.3　樸素模式匹配算法　325

9.4　KMP算法　326

9.4.1　模式串P的特徵與匹配的關系　327

9.4.2　最長公共前後綴和Next[]數組　328

9.4.3　例題　329

小結　335

第 10章　圖論　336

10.1　圖的基本概念　336

10.2　圖的存儲　337

10.3　拓撲排序　338

10.4　Floyd算法　342

10.4.1　Floyd算法思想　342

10.4.2　例題　344

10.5　Dijkstra算法　347

10.5.1　Dijkstra算法思想　348

10.5.2　編程實現Dijkstra算法　349

10.5.3　例題　350

10.6　Bellman-Ford算法　352

10.7　SPFA　355

10.7.1　SPFA原理　355

10.7.2　SPFA的模板代碼　356

10.8　最小生成樹　358

10.8.1　Prim算法　358

10.8.2　Kruskal算法　360

小結　363