程序設計競賽專題挑戰(zhàn)教程（藍橋杯官方備賽指南）

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

1.1　藍橋杯軟件類大賽的競賽規(guī)則　1

1.2　競賽題示例　4

1.3　算法知識點總覽　5

1.4　歷年真題知識點統(tǒng)計　7

1.5　藍橋杯軟件類大賽的評測系統(tǒng)　9

小結　12

第 2章　手算題和雜題　13

2.1　手算題攻略　13

2.1.1　巧用編輯器　13

2.1.2　眼看手數(shù)　14

2.1.3　巧用Excel　16

2.1.4　巧用Python　17

2.2　雜題　22

小結　32

第3章　基礎數(shù)據(jù)結構　33

3.1　數(shù)組　33

3.2　鏈表　37

3.2.1　C++鏈表實現(xiàn)　38

3.2.2　Python鏈表實現(xiàn)　42

3.3　隊列　44

3.3.1　C++普通隊列　44

3.3.2　Python普通隊列　47

3.3.3　C++優(yōu)先隊列　49

3.3.4　Python優(yōu)先隊列　51

3.4　?！?1

3.4.1　C++棧的實現(xiàn)　52

3.4.2　Python棧的實現(xiàn)　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()函數(shù)　73

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

4.2.3　Java的sort()函數(shù)　75

4.2.4　例題　75

4.3　排列和組合　87

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

4.3.2　Python的排列函數(shù)permutations()　89

4.3.3　Python的組合函數(shù)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　整數(shù)二分　103

4.5.3　整數(shù)二分例題　104

4.5.4　實數(shù)二分　112

4.6　倍增法和ST算法　114

4.6.1　用暴力法解決區(qū)間問題　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章　高級數(shù)據(jù)結構　183

6.1　并查集　183

6.1.1　用并查集檢查連通性　183

6.1.2　并查集的基本操作　185

6.1.3　路徑壓縮　188

6.1.4　例題　189

6.2　樹狀數(shù)組　197

6.2.1　區(qū)間和問題　197

6.2.2　樹狀數(shù)組的原理　199

6.2.3　lowbit()　201

6.2.4　樹狀數(shù)組的代碼　202

6.2.5　逆序對問題　203

6.3　線段樹　207

6.3.1　線段樹的概念　208

6.3.2　區(qū)間查詢　209

6.3.3　區(qū)間查詢例題　214

6.3.4　區(qū)間修改和懶惰標記　221

小結　226

第7章　動態(tài)規(guī)劃　227

7.1　動態(tài)規(guī)劃的概念　227

7.2　動態(tài)規(guī)劃基礎　228

7.3　線性DP　235

7.4　狀態(tài)壓縮DP　247

7.4.1　狀態(tài)壓縮DP的概念　247

7.4.2　狀態(tài)壓縮DP的原理　249

7.4.3　位運算　249

7.4.4　例題　250

7.5　樹形DP　255

7.6　數(shù)位DP　259

小結　264

第8章　數(shù)學　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的編程實現(xiàn)　278

8.5.3　LCM　279

8.5.4　例題　280

8.6　素數(shù)　286

8.6.1　素數(shù)的判斷　287

8.6.2　素數(shù)的篩選　290

8.6.3　區(qū)間素數(shù)　294

8.6.4　分解質因子　295

8.7　組合數(shù)學　297

8.7.1　基本計數(shù)　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　字符串函數(shù)　316

9.1.1　C++的字符串函數(shù)　316

9.1.2　Python的字符串處理　317

9.1.3　Java的字符串函數(shù)　318

9.2　簡單字符串例題　319

9.3　樸素模式匹配算法　325

9.4　KMP算法　326

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

9.4.2　Z長公共前后綴和Next[]數(shù)組　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　編程實現(xiàn)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　Z小生成樹　358

10.8.1　Prim算法　358

10.8.2　Kruskal算法　360

小結　363