內容提要
本書面向藍橋杯全國軟件和信息技術專業(yè)人才大賽的軟件類賽項（以下簡稱藍橋杯軟件類大賽），從數據結構和算法的維度幫助廣大讀者訓練編程思維和計算思維，掌握編程方法和解題技巧。
本書共10章，第1章主要介紹了藍橋杯軟件類大賽的基本情況，歸類匯總了其涉及的知識點（包括算法知識點），詳細介紹了其在線評測系統(tǒng)以說明評分情況。第2~10章則由淺入深、由易到難地介紹了各類知識點，包括手算題和雜題、基礎數據結構、基本算法、搜索、高級數據結構、動態(tài)規(guī)劃、數學、字符串、圖論等，對于每一類知識點都簡明扼要地進行說明，并以真題作為例題進行細致講解，以更好地幫助讀者實現學用結合的學習效果。需要特別說明的是，本書例題的代碼部分，分別由C++、Python、Java三種語言來實現（書中僅提供以C++、Python語言編寫的代碼，以Java語言編寫的代碼可從本書的配套數字資源中獲�。�。
本書不僅適合作為藍橋杯軟件類大賽參賽者的備賽用書，還適用于備賽其他編程或算法類大賽（如全國青少年信息學奧林匹克競賽NOI、國際大學生程序設計競賽ICPC、中國大學生程序設計競賽CCPC、中國高校計算機大賽?團體程序設計天梯賽GPLT等）。此外，本書還可作為本科生和研究生的相關算法課程的教材或參考資料。
1.藍橋杯官方備賽指南，讓你實現精準備賽，有效刷題
2.覆蓋算法競賽考點，解析詳細又貼心
3.例題代碼用 C++、Python 兩種語言編寫，同時附帶Java語言源代碼的電子資源
4.體驗“在線評測系統(tǒng)”+“真題庫”，提前進“賽場”
5.配套資源豐富，提供配套源代碼和PPT
6.金牌”教練+“金牌”教研強強聯手，多年實戰(zhàn)經驗總結，讓你備賽不再困惑，學有所獲
羅勇軍
上海交通大學計算機系博士畢業(yè)，現為華東理工大學計算機系教師。擔任華東理工大學程序設計競賽主教練 16 年，指導學生參加國際大學生程序設計競賽 ICPC、中國大學生程序設計競賽 CCPC、藍橋杯大賽，成績優(yōu)異，曾兩次帶隊參加 ICPC 全球總決賽。每年指導數百名學生參加藍橋杯大賽。
楊培林
高級工程師，國信藍橋教育科技股份有限公司教學總監(jiān)，曾擔任多所大學算法團隊教練，參與多所大學的教學方案制訂，線上課程的研發(fā)設計與教學工作。通過 10 多年以來的孜孜追求和學習，形成了自己獨特的教育教學方式。對技術的學習和跟進一直沒有停歇，在教育教學活動中把學習的方法、技巧、經驗和知識傳授給學生，讓自己和學生共享學習的快樂，共同收獲學習的成果。
目 錄
第 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 眼看手數 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++優(yōu)先隊列 49
3.3.4 Python優(yōu)先隊列 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 用暴力法解決區(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章 高級數據結構 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 區(qū)間和問題 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 區(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 數位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 區(qū)間素數 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
書單推薦
