《从零基础到金牌：算法竞赛入门笔记》是一本专为初学者设计的算法竞赛指南，旨在帮助读者迈出算法竞赛的第一步，并在此领域中取得奖牌荣誉。
本书通过简明扼要的讲解，将复杂的算法竞赛概念和技巧转化为易于理解和应用的知识点。无论您是完全没有算法竞赛经验的初学者，还是希望提高竞赛成绩的进阶选手，本书都能为您提供全面的指导。
您将通过本书学习到如何构建算法思维模式、分析问题和设计高效算法的方法。我们将深入探讨各种常见的算法和数据结构，包括贪心算法、动态规划、图论、搜索算法等。每个主题都配有清晰的示例和实战练习，以帮助您巩固所学知识并提升实际应用能力。
此外，本书还提供了大量经典算法竞赛题目的解析和详细讲解，让您能够更好地理解和掌握各种常见问题的解题思路。

目录

第1章 赛前准备\t1
1.1 算法竞赛简介\t1
1.1.1 ACM-ICPC简介\t2
1.1.2 CCPC简介\t4
1.1.3 NOIP/NOI/ CSP-J/S简介\t4
1.1.4 蓝桥杯简介\t7
1.1.5 天梯赛简介\t7
1.2 语言和工具\t8
1.2.1 竞赛语言\t8
1.2.2 编程环境\t8
1.2.3 训练平台\t8
1.3 能力要求和学习建议\t9
1.3.1 如何迈出算法竞赛第一步\t9
1.3.2 如何合理且高效地训练\t10
1.3.3 补题和总结的重要性\t10
1.3.4 如何正确看待算法竞赛的付出和收益\t10
第2章 基础语法\t12
2.1 第一个程序：Hello World\t12
2.1.1 程序示例\t12
2.1.2 头文件\t13
2.1.3 命名空间\t13
2.1.4 main函数\t14
2.2 输入与输出\t14
2.2.1 scanf和printf\t14
2.2.2 cin和cout\t15
2.2.3 各种输入/输出示例\t16
2.3 常用的基础数据类型和数学运算\t17
2.3.1 基本数据类型\t17
2.3.2 常用的数学运算\t17
2.4 分支语句\t19
2.4.1 if语句\t19
2.4.2 三目运算符\t21
2.5 循环语句\t22
2.5.1 for循环\t22
2.5.2 while循环\t23
2.6 数组\t23
2.6.1 数组的结构\t23
2.6.2 开辟数组空间\t24
2.6.3 数组元素初始化\t26
2.6.4 数组和指针的关系\t27
2.7 函数\t28
2.7.1 函数的声明和实现\t28
2.7.2 函数的调用\t28
2.7.3 Lambda函数\t29
2.8 结构体\t29
2.8.1 结构体的定义\t29
2.8.2 结构体数组\t30
2.9 推荐代码规范\t31
2.9.1 使用头文件bits/stdc++.h\t31
2.9.2 使用std命名空间\t31
2.9.3 代码缩进规范\t31
2.9.4 代码换行规范\t32
2.9.5 for循环规范\t32
2.9.6 使用longlong类型是好习惯\t32
2.9.7 不要过分压行\t33
2.9.8 不要轻易使用宏定义\t33
2.9.9 适当撰写注释\t33
2.10 语法练习题\t34
第3章 基础算法\t36
3.1 时空复杂度分析\t36
3.1.1 时间复杂度分析\t36
3.1.2 空间复杂度分析\t38
3.2 暴力枚举\t39
3.2.1 什么是解空间\t39
3.2.2 解空间的枚举方法\t40
3.2.3 例题讲解\t42
3.3 二分法\t46
3.3.1 二分法的特征\t46
3.3.2 二分法的类型\t46
3.3.3 例题讲解\t48
3.4 双指针\t52
3.4.1 双指针题的特征\t52
3.4.2 双指针的类型\t54
3.4.3 例题讲解\t54
3.5 其他\t57
3.5.1 递归\t57
3.5.2 排序\t58
3.5.3 位运算\t61
3.5.4 贪心算法\t62
3.5.5 分治法\t66
第4章 STL的基本使用\t70
4.1 STL中的数据结构\t70
4.1.1 向量（vector）\t70
4.1.2 栈（stack）\t72
4.1.3 队列（queue）\t75
4.1.4 map\t77
4.1.5 堆优先队列（priority_queue）\t80
4.1.6 集合（set）\t86
4.1.7 多重集合（multiset）\t91
4.1.8 双端队列（deque）\t94
4.1.9 string\t95
4.1.10 pair\t98
4.1.11 bitset\t99
4.2 STL中的算法\t100
4.2.1 sort()函数\t101
4.2.2 lower_bound()和upper_bound()函数\t102
4.2.3 reverse()函数\t103
4.2.4 swap()函数\t104
4.2.5 next_permutation()和prev_permutation()函数\t105
第5章 搜索\t108
5.1 深度优先搜索（回溯法）\t108
5.1.1 子集树\t108
5.1.2 排列树\t109
5.1.3 FloodFill算法\t109
5.1.4 例题讲解\t111
5.2 广度优先搜索\t116
5.2.1 等权的最短路径\t116
5.2.2 最少操作次数\t121
5.3 搜索的优化方法\t122
5.3.1 剪枝\t122
5.3.2 记忆化搜索\t122
5.3.3 例题讲解\t125
第6章 动态规划\t128
6.1 动态规划基础\t128
6.1.1 状态的定义\t129
6.1.2 状态转移方程\t129
6.1.3 注意边界条件\t130
6.1.4 做题的基本步骤\t130
6.2 背包DP\t130
6.2.1 01背包\t130
6.2.2 完全背包\t134
6.2.3 多重背包\t134
6.2.4 例题讲解\t136
6.3 区间DP\t139
6.3.1 石子合并\t140
6.3.2 例题讲解\t141
6.4 存在性DP\t143
6.4.1 什么是存在性DP\t144
6.4.2 例题讲解\t144
6.5 状压DP\t145
6.5.1 状态压缩的方法\t145
6.5.2 例题讲解\t145
6.6 期望DP\t148
6.6.1 期望的性质和转移\t148
6.6.2 例题讲解\t149
6.7 树形DP\t156
6.7.1 树形动态规划介绍\t156
6.7.2 自下而上树形动态规划\t156
6.7.3 换根动态规划\t158
6.7.4 例题讲解\t161
第7章 图论\t168
7.1 图的存储方法\t168
7.1.1 邻接矩阵\t168
7.1.2 邻接表\t169
7.1.3 链式前向星\t170
7.2 图上问题\t172
7.2.1 图的分类和性质\t172
7.2.2 图的遍历方法\t173
7.2.3 Dijkstra最短路径\t176
7.2.4 Bellman-Ford最短路径\t183
7.2.5 Johnson最短路径\t186
7.2.6 Floyd最短路径\t192
7.2.7 匈牙利算法\t195
7.2.8 Tarjan算法\t199
7.2.9 DAG-DP\t206
7.3 树上问题\t210
7.3.1 树的概念\t210
7.3.2 最小生成树\t211
7.3.3 倍增LCA\t214
7.3.4 例题讲解\t217
第8章 进阶数据结构\t221
8.1 单调栈\t221
8.1.1 单调栈介绍\t221
8.1.2 例题讲解\t222
8.2 单调队列\t224
8.2.1 单调队列介绍\t224
8.2.2 例题讲解\t226
8.3 ST表\t231
8.3.1 ST表介绍\t232
8.3.2 例题讲解\t232
8.4 树状数组\t235
8.4.1 单点修改型树状数组\t235
8.4.2 区间修改型树状数组\t238
8.4.3 例题讲解\t238
8.5 线段树\t239
8.5.1 线段树区间加法\t240
8.5.2 线段树的区间乘法、加法和赋值\t243
8.5.3 例题讲解\t245
8.6 并查集\t250
8.6.1 朴素并查集\t250
8.6.2 并查集的路径压缩\t251
8.6.3 并查集的启发式合并\t251
8.6.4 可撤销并查集\t253
8.6.5 例题讲解\t255
8.7 链表\t258
8.7.1 数组实现双向链表\t258
8.7.2 例题讲解\t260
第9章 字符串\t263
9.1 字符串匹配\t263
9.1.1 朴素的字符串匹配算法\t263
9.1.2 KMP算法\t264
9.1.3 进制哈希\t266
9.1.4 例题讲解\t269
9.2 回文串\t273
9.2.1 回文串介绍\t273
9.2.2 Manacher算法\t275
9.2.3 例题讲解\t277
9.3 Trie树（字典树）\t280
9.3.1 Trie树介绍\t280
9.3.2 字符Trie树\t282
9.3.3 01Trie树\t284
9.3.4 例题讲解\t286
第10章 数论\t290
10.1 数论基础\t290
10.1.1 数论的讨论范围\t290
10.1.2 整数除法的性质\t290
10.1.3 取模运算的性质\t291
10.2 专享分解定理和约数定理\t292
10.2.1 专享分解定理\t292
10.2.2 约数定理\t292
10.2.3 因数分解和质因数分解\t293
10.2.4 例题讲解\t294
10.3 优选公约数和最小公倍数\t297
10.3.1 辗转相除法\t297
10.3.2 优选公约数和最小公倍数在专享分解中的性质\t298
10.3.3 例题讲解\t299
10.4 拓展欧几里得\t301
10.4.1 裴蜀定理\t301
10.4.2 拓展欧几里得算法\t302
10.4.3 例题讲解\t304
10.5 快速幂\t306
10.5.1 为什么要用快速幂\t306
10.5.2 快速幂的原理和模板\t306
10.5.3 例题讲解\t307
10.6 乘法逆元\t308
10.6.1 乘法逆元如何表示除法\t309
10.6.2 费马小定理求逆元\t309
10.7 组合计数\t310
10.7.1 分类加法和分步乘法\t310
10.7.2 组合数\t311
10.7.3 普通型生成函数\t313
10.7.4 Lucas定理\t316
10.7.5 例题讲解\t317
10.8 关于质数的判断\t322
10.8.1 单点质数判断（试除法）\t322
10.8.2 埃氏筛法\t323
10.8.3 欧拉筛法\t326
10.8.4 例题讲解\t327
10.9 欧拉函数\t328
10.9.1 单点欧拉函数\t328
10.9.2 筛法求欧拉函数\t329
10.9.3 欧拉定理\t332
10.9.4 欧拉降幂\t333
10.9.5 例题讲解\t333
10.10 异或线性基\t336
10.10.1 异或线性基的原理和性质\t336
10.10.2 例题讲解\t339
第11章 博弈论\t341
11.1 基础博弈类型\t341
11.1.1 Bash博弈\t341
11.1.2 Nim博弈\t342
11.1.3 例题讲解\t343
11.2 SG函数\t346
11.2.1 mex运算\t346
11.2.2 SG函数的定义和性质\t346
11.2.3 子游戏的合并\t348
11.2.4 SG函数打表\t348
11.2.5 例题讲解\t348
11.3 反Nim博弈\t350
11.3.1 反Nim博弈结论\t350
11.3.2 结论的证明\t351
11.3.3 例题讲解\t352
11.4 博弈杂题选讲\t353
第12章 高级算法策略与技巧\t358
12.1 构造\t358
12.1.1 构造的常见思维\t358
12.1.2 例题讲解\t359
12.2 分块思想\t363
12.2.1 根号分块优化\t364
12.2.2 整除分块\t369
12.3 离散化\t371
12.4 离线思想\t374
12.5 莫队算法\t374
12.5.1 莫队算法介绍\t375
12.5.2 例题讲解\t376
12.6 CDQ分治\t383
12.6.1 点对/区间相关问题\t383
12.6.2 三维偏序问题\t384
12.7 本章小结\t388
第13章 真题选讲\t389
13.1 XCPC往年真题选讲\t389
13.2 NOI/NOIP往年真题选讲\t399
13.3 蓝桥杯往年真题选讲\t421
13.4 天梯赛往年真题选讲\t428