算法思维：竞赛真题精选精讲（第2版）

解锁数据结构与算法的核心能力：系统拆解哈希表、递归、动态规划、树、图、堆等概念，帮你搭建“问题分析→最优解设计”的完整思维框架。
竞赛真题实战演练：精选28道IOI、NOIP、USACO、CCC、CCO、ICPC、DWITE等竞赛经典题，在真实竞赛场景中，锤炼算法思维，精进编程技巧。
从容应对技术面试：通过循序渐进的讲解与练习，培养算法化思维，掌握方案权衡与优化技巧，轻松攻克各类技术面试难关。
C语言实现，跨语言适配：所有示例以C语言编写，代码结构清晰、逻辑严谨。即便你使用的是C++、Java或Python，也能轻松理解并迁移应用。

本书精选IOI、NOIP、USACO、CCC、CCO、ICPC、DWITE等竞赛中28个富有趣味与挑战性的算法竞赛题，采用“问题描述 – 输入 – 输出 – 解决方案”的结构，引导读者在实战中培养算法思维，牢固掌握数据结构与算法的核心知识。全书共分10章，涵盖哈希表、树与递归、记忆化与动态规划、图与广度优先搜索、加权图中的最短路径、二分搜索、堆与线段树、并查集以及随机化算法等主题。所有示例均用C语言实现，但无论你使用C++、Java还是Python，都能轻松理解并迁移所学思想与方法。

丹尼尔·津加罗（Daniel Zingaro）
多伦多大学计算机科学系副教授，以其独特的互动式教学方法和在“主动学习”领域的开创性研究而享誉国际。他的课程涵盖计算机基础、数据结构与算法、程序设计、操作系统等核心方向。除本书外，他还是Learn to Code by Solving Problems和Learn AI-Assisted Python Programming等书的作者，深受全球计算机学习者的喜爱。

第 1章 哈希表1
1.1 问题1：独特的雪花1
1.1.1 题干1
1.1.2 简化问题3
1.1.3 解决核心问题4
1.1.4 解法1：成对比较7
1.1.5 解法2：减少工作量11
1.2 哈希表概览16
1.2.1 设计哈希表16
1.2.2 为什么使用哈希表18
1.3 问题2：登录风波19
1.3.1 题干19
1.3.2 解法1：遍历所有密码20
1.3.3 解法2：使用哈希表22
1.4 问题3：拼写检查27
1.4.1 题干27
1.4.2 考虑哈希表28
1.4.3 临时解决方案30
1.5 小结33
1.6 说明33
第 2章 树与递归34
2.1 问题1：万圣节扫荡34
2.1.1 题干34
2.1.2 二叉树36
2.1.3 求解用例38
2.1.4 二叉树的表示38
2.1.5 收集所有糖果42
2.1.6 一个完全不同的解法47
2.1.7 最小遍历街道数52
2.1.8 读取输入54
2.2 为什么使用递归60
2.3 问题2：后代距离61
2.3.1 题干61
2.3.2 读取输入63
2.3.3 一个节点的后代数量67
2.3.4 所有节点的后代数量68
2.3.5 节点排序68
2.3.6 输出信息69
2.3.7 main函数70
2.4 小结70
2.5 说明71
第3章 记忆化与动态规划72
3.1 问题1：汉堡狂72
3.1.1 题干72
3.1.2 制订计划73
3.1.3 确定最优解的特征74
3.1.4 解法1：递归76
3.1.5 解法2：记忆化80
3.1.6 解法3：动态规划85
3.2 记忆化与动态规划的步骤88
3.2.1 第 一步：最优解的结构88
3.2.2 第二步：递归解89
3.2.3 第三步：记忆化89
3.2.4 第四步：动态规划90
3.3 问题2：精打细算91
3.3.1 题干91
3.3.2 确定最优解的特征92
3.3.3 解法1：递归94
3.3.4 解法2：记忆化99
3.4 问题3：冰球劲敌101
3.4.1 题干101
3.4.2 关于劲敌102
3.4.3 确定最优解的特征104
3.4.4 解法1：递归106
3.4.5 解法2：记忆化109
3.4.6 解法3：动态规划110
3.4.7 空间优化113
3.5 小结114
3.6 说明115
第4章 高级记忆化与动态规划116
4.1 问题1：跳一跳116
4.1.1 题干116
4.1.2 示例解析117
4.1.3 解法1：反向构造119
4.1.4 解法2：正向构造123
4.2 问题2：构建方式127
4.2.1 题干127
4.2.2 示例解析128
4.2.3 解法1：使用“恰好”子问题129
4.2.4 解法2：引入更多子问题134
4.3 小结138
4.4 说明138
第5章 图与广度优先搜索139
5.1 问题1：骑士追击139
5.1.1 题干139
5.1.2 最优走法141
5.1.3 骑士的最佳结果148
5.1.4 骑士往返150
5.1.5 时间优化153
5.2 图与BFS154
5.2.1 图是什么154
5.2.2 图与树155
5.2.3 图的BFS157
5.2.4 图与动态规划158
5.3 问题2：攀绳158
5.3.1 题干158
5.3.2 解法1：寻找动作159
5.3.3 解法2：重新建模163
5.4 问题3：图书翻译171
5.4.1 题干171
5.4.2 读取语言名称172
5.4.3 构造图173
5.4.4 BFS176
5.4.5 总成本177
5.5 小结178
5.6 说明178
第6章 加权图中的最短路径179
6.1 问题1：老鼠迷宫179
6.1.1 题干179
6.1.2 从BFS出发180
6.1.3 加权图中的最短路径181
6.1.4 构造图185
6.1.5 实现Dijkstra算法187
6.1.6 两项优化189
6.2 Dijkstra算法190
6.2.1 Dijkstra算法的运行时间191
6.2.2 负权边192
6.3 问题2：探亲计划194
6.3.1 题干194
6.3.2 邻接矩阵195
6.3.3 构造图196
6.3.4 特殊路径197
6.3.5 任务1：最短路径200
6.3.6 任务2：最短路径的数量202
6.4 小结208
6.5 说明209
第7章 二分搜索210
7.1 问题1：喂蚂蚁210
7.1.1 题干210
7.1.2 树问题的变种212
7.1.3 读取输入213
7.1.4 可行性检验215
7.1.5 搜索解217
7.2 二分搜索概览218
7.2.1 二分搜索的运行时间219
7.2.2 判断可行性220
7.2.3 搜索有序数组220
7.3 问题2：河边跳220
7.3.1 题干221
7.3.2 贪心思想221
7.3.3 可行性检验223
7.3.4 搜索解227
7.3.5 读取输入230
7.4 问题3：生活质量231
7.4.1 题干231
7.4.2 给每个矩形排序232
7.4.3 使用二分搜索235
7.4.4 可行性检验236
7.4.5 更高效的可行性检验237
7.5 问题4：洞穴之门242
7.5.1 题干242
7.5.2 求解子问题243
7.5.3 使用线性搜索245
7.5.4 使用二分搜索247
7.6 小结249
7.7 说明249
第8章 堆与线段树250
8.1 问题1：促销活动250
8.1.1 题干250
8.1.2 解法1：数组中的最大值与最小值251
8.1.3 最大堆254
8.1.4 最小堆264
8.1.5 解法2：堆266
8.2 堆269
8.2.1 另外两个应用场景269
8.2.2 选择数据结构270
8.3 问题2：构造树堆270
8.3.1 题干271
8.3.2 递归输出树堆272
8.3.3 按标签排序273
8.3.4 解法1：递归274
8.3.5 区间最大值查询277
8.3.6 用线段树处理区间查询278
8.3.7 解法2：线段树285
8.4 线段树286
8.5 问题3：两数之和287
8.5.1 题干287
8.5.2 填充线段树288
8.5.3 查询线段树291
8.5.4 更新线段树293
8.5.5 main函数295
8.6 小结296
8.7 说明296
第9章 并查集297
9.1 问题1：社交网络297
9.1.1 题干297
9.1.2 建模为图298
9.1.3 解法1：BFS302
9.1.4 并查集305
9.1.5 解法2：并查集308
9.1.6 优化1：按大小求并312
9.1.7 优化2：路径压缩315
9.2 并查集概览317
9.2.1 关系：三个条件317
9.2.2 选择并查集318
9.2.3 优化318
9.3 问题2：盟友和敌人318
9.3.1 题干319
9.3.2 扩充并查集320
9.3.3 main函数323
9.3.4 查找与合并325
9.3.5 SetFriends与SetEnemies326
9.3.6 AreFriends与AreEnemies327
9.4 问题3：收拾抽屉328
9.4.1 题干328
9.4.2 等价的抽屉329
9.4.3 main函数334
9.4.4 查找与合并336
9.5 小结337
9.6 说明337
第 10章 随机化338
10.1 问题1：羊羹338
10.1.1 题干338
10.1.2 随机选一块339
10.1.3 生成随机数341
10.1.4 确定块数342
10.1.5 猜口味344
10.1.6 需要试几次346
10.1.7 填充口味数组347
10.1.8 main函数348
10.2 随机化概览349
10.2.1 蒙特卡罗算法349
10.2.2 拉斯维加斯算法350
10.2.3 确定性算法与随机化算法351
10.3 问题2：瓶盖和瓶子351
10.3.1 题干351
10.3.2 求解子问题352
10.3.3 解法1：递归354
10.3.4 解法2：添加随机化358
10.4 快速排序359
10.4.1 实现快速排序359
10.4.2 最坏情况与预期运行时间361
10.5 小结363
10.6 说明363
附录A 算法运行时间364
附录B 未尽之言369
附录C 问题来源385
后记387