算法思维 竞赛真题精选精讲 第2版 算法编程竞赛真题解析 数据结构与算法 动态规划C语言竞赛
￥90.80
| 运费： | ¥ 0.00-20.00 |
商品详情
书名：算法思维：竞赛真题精选精讲：第2版
定价：129.8
ISBN：9787115683649
作者：[加] 丹尼尔·津加罗（Daniel Zingaro）
版次：第1版
出版时间：2026-01
内容提要：
本书精选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 图与BFS 154
5.2.1 图是什么 154
5.2.2 图与树 155
5.2.3 图的BFS 157
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 BFS 176
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：BFS 302
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与SetEnemies 326
9.3.6 AreFriends与AreEnemies 327
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
定价：129.8
ISBN：9787115683649
作者：[加] 丹尼尔·津加罗（Daniel Zingaro）
版次：第1版
出版时间：2026-01
内容提要：
本书精选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 图与BFS 154
5.2.1 图是什么 154
5.2.2 图与树 155
5.2.3 图的BFS 157
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 BFS 176
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：BFS 302
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与SetEnemies 326
9.3.6 AreFriends与AreEnemies 327
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
- 人民邮电出版社有限公司 （微信公众号认证）
- 人民邮电出版社微店，为您提供最全面，最专业的一站式购书服务
- 扫描二维码，访问我们的微信店铺
- 随时随地的购物、客服咨询、查询订单和物流...
