新书速览|算法竞赛入门笔记

《算法竞赛入门笔记》

本书内容

《算法竞赛入门笔记》从参赛者的视角出发，结合编者丰富的亲身竞赛经验，系统地介绍算法竞赛的关键知识点和核心技能。《算法竞赛入门笔记》共13章，内容涵盖赛前准备、基础算法、STL容器、搜索技巧、动态规划、图论、数论、博弈论以及真题解析等重要主题。

《算法竞赛入门笔记》的独特之处在于将算法竞赛中的实用知识点与竞赛题目紧密结合，并对高频考点和重要内容进行归纳总结。书中不仅详细讲解理论知识，还结合大量实战例题，使读者能够在实际问题中灵活运用所学算法。此外，书中提供的C++代码模板简洁高效，易于阅读和理解，便于快速上手练习。对于复杂的概念与核心算法，还配以直观的手绘图示说明，大大降低了学习难度，提高了学习效率。

本书作者

谢子扬

就读于武汉理工大学计算机科学与技术专业，曾获第47届ICPC亚洲区域赛银牌，第9届CCPC全国邀请赛金牌，第49届ICPC亚州区决赛(EC-Final)铜牌等奖项。蓝桥云课2023年度优秀讲师。B站UP主Erik_Tse在校期间曾任华为技术有限公司内核开发实习生。

尹志扬                                                                            中科院某京所研究生在读，多模态大模型相关研究方向。从事算法教学工作多年，培养的多名初高中信竞选手，获得CSP、NOIP高分并进入省队。参与多项国家重点研发项目，发表期刊、会议文章多篇。

本书读者

《算法竞赛入门笔记》讲解深入浅出，代码注释详尽，内容丰富实用，特别适合参加各类算法竞赛（如XCPC、蓝桥杯大赛、团体程序设计天梯赛等）的中学生和大学生阅读。同时，对于正在准备技术面试的求职者、希望提升编程技能的软件开发者以及算法爱好者来说，《算法竞赛入门笔记》也是一本极佳的算法学习指南。

本书目录

第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

本书特色

本文摘自《算法竞赛入门笔记》，获出版社和作者授权发布。

算法竞赛入门笔记——jd