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

羅勇軍

上海交通大學電腦系博士畢業，現為華東理工大學電腦系教師。擔任華東理工大學程序設計競賽主教練 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