算法競賽入門筆記

目錄

 

第1章  賽前準備 1

1.1  算法競賽簡介 1

1.1.1  ACM-ICPC簡介 2

1.1.2  CCPC簡介 4

1.1.3  NOIP/NOI/ CSP-J/S簡介 4

1.1.4  藍橋杯簡介 7

1.1.5  天梯賽簡介 7

1.2  語言和工具 8

1.2.1  競賽語言 8

1.2.2  編程環境 8

1.2.3  訓練平臺 8

1.3  能力要求和學習建議 9

1.3.1  如何邁出算法競賽第一步 9

1.3.2  如何合理且高效地訓練 10

1.3.3  補題和總結的重要性 10

1.3.4  如何正確看待算法競賽的付出和收益 10

第2章  基礎語法 12

2.1  第一個程序：Hello World 12

2.1.1  程序示例 12

2.1.2  頭文件 13

2.1.3  命名空間 13

2.1.4  main函數 14

2.2  輸入與輸出 14

2.2.1  scanf和printf 14

2.2.2  cin和cout 15

2.2.3  各種輸入/輸出示例 16

2.3  常用的基礎數據類型和數學運算 17

2.3.1  基本數據類型 17

2.3.2  常用的數學運算 17

2.4  分支語句 19

2.4.1  if語句 19

2.4.2  三目運算符 21

2.5  循環語句 22

2.5.1  for循環 22

2.5.2  while循環 23

2.6  數組 23

2.6.1  數組的結構 23

2.6.2  開闢數組空間 24

2.6.3  數組元素初始化 26

2.6.4  數組和指針的關系 27

2.7  函數 28

2.7.1  函數的聲明和實現 28

2.7.2  函數的調用 28

2.7.3  Lambda函數 29

2.8  結構體 29

2.8.1  結構體的定義 29

2.8.2  結構體數組 30

2.9  推薦代碼規範 31

2.9.1  使用頭文件bits/stdc++.h 31

2.9.2  使用std命名空間 31

2.9.3  代碼縮進規範 31

2.9.4  代碼換行規範 32

2.9.5  for循環規範 32

2.9.6  使用longlong類型是好習慣 32

2.9.7  不要過分壓行 33

2.9.8  不要輕易使用宏定義 33

2.9.9  適當撰寫註釋 33

2.10  語法練習題 34

第3章  基礎算法 36

3.1  時空復雜度分析 36

3.1.1  時間復雜度分析 36

3.1.2  空間復雜度分析 38

3.2  暴力枚舉 39

3.2.1  什麽是解空間 39

3.2.2  解空間的枚舉方法 40

3.2.3  例題講解 42

3.3  二分法 46

3.3.1  二分法的特徵 46

3.3.2  二分法的類型 46

3.3.3  例題講解 48

3.4  雙指針 52

3.4.1  雙指針題的特徵 52

3.4.2  雙指針的類型 54

3.4.3  例題講解 54

3.5  其他 57

3.5.1  遞歸 57

3.5.2  排序 58

3.5.3  位運算 61

3.5.4  貪心算法 62

3.5.5  分治法 66

第4章  STL的基本使用 70

4.1  STL中的數據結構 70

4.1.1  向量（vector） 70

4.1.2  棧（stack） 72

4.1.3  隊列（queue） 75

4.1.4  map 77

4.1.5  堆優先隊列（priority_queue） 80

4.1.6  集合（set） 86

4.1.7  多重集合（multiset） 91

4.1.8  雙端隊列（deque） 94

4.1.9  string 95

4.1.10  pair 98

4.1.11  bitset 99

4.2  STL中的算法 100

4.2.1  sort()函數 101

4.2.2  lower_bound()和upper_bound()函數 102

4.2.3  reverse()函數 103

4.2.4  swap()函數 104

4.2.5  next_permutation()和prev_permutation()函數 105

第5章  搜索 108

5.1  深度優先搜索（回溯法） 108

5.1.1  子集樹 108

5.1.2  排列樹 109

5.1.3  FloodFill算法 109

5.1.4  例題講解 111

5.2  廣度優先搜索 116

5.2.1  等權的最短路徑 116

5.2.2  最少操作次數 121

5.3  搜索的優化方法 122

5.3.1  剪枝 122

5.3.2  記憶化搜索 122

5.3.3  例題講解 125

第6章  動態規劃 128

6.1  動態規劃基礎 128

6.1.1  狀態的定義 129

6.1.2  狀態轉移方程 129

6.1.3  註意邊界條件 130

6.1.4  做題的基本步驟 130

6.2  背包DP 130

6.2.1  01背包 130

6.2.2  完全背包 134

6.2.3  多重背包 134

6.2.4  例題講解 136

6.3  區間DP 139

6.3.1  石子合並 140

6.3.2  例題講解 141

6.4  存在性DP 143

6.4.1  什麽是存在性DP 144

6.4.2  例題講解 144

6.5  狀壓DP 145

6.5.1  狀態壓縮的方法 145

6.5.2  例題講解 145

6.6  期望DP 148

6.6.1  期望的性質和轉移 148

6.6.2  例題講解 149

6.7  樹形DP 156

6.7.1  樹形動態規劃介紹 156

6.7.2  自下而上樹形動態規劃 156

6.7.3  換根動態規劃 158

6.7.4  例題講解 161

第7章  圖論 168

7.1  圖的存儲方法 168

7.1.1  鄰接矩陣 168

7.1.2  鄰接表 169

7.1.3  鏈式前向星 170

7.2  圖上問題 172

7.2.1  圖的分類和性質 172

7.2.2  圖的遍歷方法 173

7.2.3  Dijkstra最短路徑 176

7.2.4  Bellman-Ford最短路徑 183

7.2.5  Johnson最短路徑 186

7.2.6  Floyd最短路徑 192

7.2.7  匈牙利算法 195

7.2.8  Tarjan算法 199

7.2.9  DAG-DP 206

7.3  樹上問題 210

7.3.1  樹的概念 210

7.3.2  最小生成樹 211

7.3.3  倍增LCA 214

7.3.4  例題講解 217

第8章  進階數據結構 221

8.1  單調棧 221

8.1.1  單調棧介紹 221

8.1.2  例題講解 222

8.2  單調隊列 224

8.2.1  單調隊列介紹 224

8.2.2  例題講解 226

8.3  ST表 231

8.3.1  ST表介紹 232

8.3.2  例題講解 232

8.4  樹狀數組 235

8.4.1  單點修改型樹狀數組 235

8.4.2  區間修改型樹狀數組 238

8.4.3  例題講解 238

8.5  線段樹 239

8.5.1  線段樹區間加法 240

8.5.2  線段樹的區間乘法、加法和賦值 243

8.5.3  例題講解 245

8.6  並查集 250

8.6.1  樸素並查集 250

8.6.2  並查集的路徑壓縮 251

8.6.3  並查集的啟發式合並 251

8.6.4  可撤銷並查集 253

8.6.5  例題講解 255

8.7  鏈表 258

8.7.1  數組實現雙向鏈表 258

8.7.2  例題講解 260

第9章  字符串 263

9.1  字符串匹配 263

9.1.1  樸素的字符串匹配算法 263

9.1.2  KMP算法 264

9.1.3  進制哈希 266

9.1.4  例題講解 269

9.2  迴文串 273

9.2.1  迴文串介紹 273

9.2.2  Manacher算法 275

9.2.3  例題講解 277

9.3  Trie樹（字典樹） 280

9.3.1  Trie樹介紹 280

9.3.2  字符Trie樹 282

9.3.3  01Trie樹 284

9.3.4  例題講解 286

第10章  數論 290

10.1  數論基礎 290

10.1.1  數論的討論範圍 290

10.1.2  整數除法的性質 290

10.1.3  取模運算的性質 291

10.2  唯一分解定理和約數定理 292

10.2.1  唯一分解定理 292

10.2.2  約數定理 292

10.2.3  因子分解和質因子分解 293

10.2.4  例題講解 294

10.3  最大公約數和最小公倍數 297

10.3.1  輾轉相除法 297

10.3.2  最大公約數和最小公倍數在唯一分解中的性質 298

10.3.3  例題講解 299

10.4  拓展歐幾里得 301

10.4.1  裴蜀定理 301

10.4.2  拓展歐幾里得算法 302

10.4.3  例題講解 304

10.5  快速冪 306

10.5.1  為什麽要用快速冪 306

10.5.2  快速冪的原理和模板 306

10.5.3  例題講解 307

10.6  乘法逆元 308

10.6.1  乘法逆元如何表示除法 309

10.6.2  費馬小定理求逆元 309

10.7  組合計數 310

10.7.1  分類加法和分步乘法 310

10.7.2  組合數 311

10.7.3  普通型生成函數 313

10.7.4  Lucas定理 316

10.7.5  例題講解 317

10.8  關於質數的判斷 322

10.8.1  單點質數判斷（試除法） 322

10.8.2  埃氏篩法 323

10.8.3  歐拉篩法 326

10.8.4  例題講解 327

10.9  歐拉函數 328

10.9.1  單點歐拉函數 328

10.9.2  篩法求歐拉函數 329

10.9.3  歐拉定理 332

10.9.4  歐拉降冪 333

10.9.5  例題講解 333

10.10  異或線性基 336

10.10.1  異或線性基的原理和性質 336

10.10.2  例題講解 339

第11章  博弈論 341

11.1  基礎博弈類型 341

11.1.1  Bash博弈 341

11.1.2  Nim博弈 342

11.1.3  例題講解 343

11.2  SG函數 346

11.2.1  mex運算 346

11.2.2  SG函數的定義和性質 346

11.2.3  子游戲的合並 348

11.2.4  SG函數打表 348

11.2.5  例題講解 348

11.3  反Nim博弈 350

11.3.1  反Nim博弈結論 350

11.3.2  結論的證明 351

11.3.3  例題講解 352

11.4  博弈雜題選講 353

第12章  高級算法策略與技巧 358

12.1  構造 358

12.1.1  構造的常見思維 358

12.1.2  例題講解 359

12.2  分塊思想 363

12.2.1  根號分塊優化 364

12.2.2  整除分塊 369

12.3  離散化 371

12.4  離線思想 374

12.5  莫隊算法 374

12.5.1  莫隊算法介紹 375

12.5.2  例題講解 376

12.6  CDQ分治 383

12.6.1  點對/區間相關問題 383

12.6.2  三維偏序問題 384

12.7  本章小結 388

第13章  真題選講 389

13.1  XCPC往年真題選講 389

13.2  NOI/NOIP往年真題選講 399

13.3  藍橋杯往年真題選講 421

13.4  天梯賽往年真題選講 428