程序設(shè)計(jì)競(jìng)賽專(zhuān)題挑戰(zhàn)教程（藍(lán)橋杯官方備賽指南）

第 1章　藍(lán)橋杯軟件類(lèi)大賽介紹　1

1.1　藍(lán)橋杯軟件類(lèi)大賽的競(jìng)賽規(guī)則　1

1.2　競(jìng)賽題示例　4

1.3　算法知識(shí)點(diǎn)總覽　5

1.4　歷年真題知識(shí)點(diǎn)統(tǒng)計(jì)　7

1.5　藍(lán)橋杯軟件類(lèi)大賽的評(píng)測(cè)系統(tǒng)　9

小結(jié)　12

第 2章　手算題和雜題　13

2.1　手算題攻略　13

2.1.1　巧用編輯器　13

2.1.2　眼看手?jǐn)?shù)　14

2.1.3　巧用Excel　16

2.1.4　巧用Python　17

2.2　雜題　22

小結(jié)　32

第3章　基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)　33

3.1　數(shù)組　33

3.2　鏈表　37

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

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

3.3　隊(duì)列　44

3.3.1　C++普通隊(duì)列　44

3.3.2　Python普通隊(duì)列　47

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

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

3.4　棧　51

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

3.4.2　Python棧的實(shí)現(xiàn)　55

3.4.3　例題　57

3.5　二叉樹(shù)　59

3.5.1　二叉樹(shù)的定義　60

3.5.2　二叉樹(shù)的存儲(chǔ)　60

3.5.3　二叉樹(shù)的遍歷　61

3.5.4　例題　63

小結(jié)　66

第4章　基本算法　67

4.1　算法復(fù)雜度　67

4.1.1　算法的概念　67

4.1.2　計(jì)算資源　68

4.1.3　選擇解題方法　69

4.1.4　算法復(fù)雜度概述　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　手寫(xiě)排列和組合代碼　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í)數(shù)二分　112

4.6　倍增法和ST算法　114

4.6.1　用暴力法解決區(qū)間問(wèn)題　115

4.6.2　ST算法　116

4.6.3　ST算法的模板代碼　118

4.7　前綴和　119

4.8　貪心算法　124

小結(jié)　132

第5章　搜索　133

5.1　DFS基礎(chǔ)　134

5.1.1　遞歸和記憶化搜索　134

5.1.2　DFS的代碼框架　136

5.1.3　DFS的所有路徑　137

5.1.4　DFS與排列組合　140

5.1.5　DFS應(yīng)用詳解　143

5.1.6　DFS真題　147

5.2　BFS基礎(chǔ)　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

小結(jié)　182

第6章　高級(jí)數(shù)據(jù)結(jié)構(gòu)　183

6.1　并查集　183

6.1.1　用并查集檢查連通性　183

6.1.2　并查集的基本操作　185

6.1.3　路徑壓縮　188

6.1.4　例題　189

6.2　樹(shù)狀數(shù)組　197

6.2.1　區(qū)間和問(wèn)題　197

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

6.2.3　lowbit()　201

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

6.2.5　逆序?qū)?wèn)題　203

6.3　線段樹(shù)　207

6.3.1　線段樹(shù)的概念　208

6.3.2　區(qū)間查詢　209

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

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

小結(jié)　226

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

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

7.2　動(dòng)態(tài)規(guī)劃基礎(chǔ)　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　位運(yùn)算　249

7.4.4　例題　250

7.5　樹(shù)形DP　255

7.6　數(shù)位DP　259

小結(jié)　264

第8章　數(shù)學(xué)　265

8.1　模運(yùn)算　265

8.2　快速冪　266

8.3　矩陣乘法　271

8.4　矩陣快速冪　273

8.5　GCD和LCM　278

8.5.1　GCD的定義和性質(zhì)　278

8.5.2　GCD的編程實(shí)現(xiàn)　278

8.5.3　LCM　279

8.5.4　例題　280

8.6　素?cái)?shù)　286

8.6.1　素?cái)?shù)的判斷　287

8.6.2　素?cái)?shù)的篩選　290

8.6.3　區(qū)間素?cái)?shù)　294

8.6.4　分解質(zhì)因子　295

8.7　組合數(shù)學(xué)　297

8.7.1　基本計(jì)數(shù)　297

8.7.2　鴿巢原理　301

8.7.3　二項(xiàng)式定理和楊輝三角　302

8.8　幾何　304

8.8.1　普通幾何題　305

8.8.2　點(diǎn)和向量　306

8.8.3　點(diǎn)積和叉積　307

8.8.4　點(diǎn)和線的關(guān)系　310

小結(jié)　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　簡(jiǎn)單字符串例題　319

9.3　樸素模式匹配算法　325

9.4　KMP算法　326

9.4.1　模式串P的特征與匹配的關(guān)系　327

9.4.2　Z長(zhǎng)公共前后綴和Next[]數(shù)組　328

9.4.3　例題　329

小結(jié)　335

第 10章　圖論　336

10.1　圖的基本概念　336

10.2　圖的存儲(chǔ)　337

10.3　拓?fù)渑判颉?38

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　編程實(shí)現(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小生成樹(shù)　358

10.8.1　Prim算法　358

10.8.2　Kruskal算法　360

小結(jié)　363