第三版（2018年11月印刷）勘误与说明1
需积分: 0 96 浏览量
2022-08-04
13:22:36
上传
评论
收藏 406KB PDF 举报
《算法竞赛进阶指南》第 3 版·勘误与说明
自第 1 版出版以来，本书受到了广大读者的热情支持，同时也收到了不少有价值的反馈。为了使这本读物
能够更好地帮助到广大读者，我们决定在每次批量印刷前，都争取对上一版进行修订，目前是第 3 版。
版本修订历史：
版本
勘误
章节调整
内容调整
配套资源
第 1 版
18.01
－
－
－
－
第 2 版
18.06
第 1 版勘
误表 36 条
第 0x40 章《数据结构进阶》
新 增 两 节 “ 离 线 分 治 算
法”“可持久化数据结构”
对前三章的部分内容进行更细致的
讲解，涉及位运算、递归、二分、字
符串、剪枝、双向搜索等
提供标程、数
据的例题和习
题达到 80%
第 3 版
18.11
第 2 版勘
误表和未收
录的 10 条
第 0x02~0x03 节重组为“递
推与递归”“前缀和与差分”
第 0x12 节增加例题，第 0x08、0x18
节增加习题，第 0x43、0x63 节增加
动态开点与线段树合并、树上差分等
－
在第 1 版出版之后，我们还依托互联网进行了如下建设：
✓ 在 Contest Hunter（CH）设立了本书专用题库。地址：
http://contest-hunter.org:83/contest?type=1
✓ 在 GitHub 设立了 lydrainbowcat/tedukuri 项目，提供光盘内容的在线浏览，并随时更新勘误表、新
收集到的标程和数据。
地址：https://github.com/lydrainbowcat/tedukuri
光盘压缩包（请使用 RAR 5.0 以上版本解压）： http://noi.zzstep.com/jjzn_v3.rar
✓ 创建了读者交流 QQ 群 650836280。
请以“所在或毕业学校 – 姓名或常用 OJ 用户名”的半实名方式验证加入，并设置自己的群名片。格
式不符者可能会被管理员定期清理。
第 3 版勘误
【第 74/75 页】【0x15 字符串】【最小表示法】
74 页“最小表示法”的文本框中，原文为：
如果扫描了
𝑛
个字符后仍然相等，说明
𝑆
只由
1
种字符构成，任意
𝐵[𝑖]
都是它的最小表示。
应改为：
如果扫描了 𝑛 个字符后仍然相等，说明 S 有更小的循环元（例如 catcat 有循环元 cat），并且该循环元已
扫描完成，𝐵
[
min
(
𝑖, 𝑗
)
]
即为最小表示，算法结束。
75 页的代码注释，原文为：
// s
只由一个字符构成，形如
"aaaaa"
应改为：
// s 形如"catcat"，它的循环元已扫描完成
【第 234 页】【0x46 二叉查找树与平衡树初步】【 BST 的删除】
BST 删除函数 Remove 的模板代码有更新。
评论0