《算法竞赛进阶指南》勘误
以下为针对《算法竞赛进阶指南》第一版( 年 月印刷)的勘误,关于最新信息或更多
内容,请访问网址 。对于第一版的错误之处,我们深
表歉意,第二版计划于 年 月印制。
I. 重要勘误
这部分勘误涉及逻辑错误,可能影响整部分讲解的正确性。
【第 24 页】【0x04 二分】【三分法】
以单峰函数 为例 ,(原文)
若
,(原文),极大值点都在 右侧,可令 。
同理,若
,则极大值点一定在 左侧,可令 。
注意,我们在介绍单峰函数时特别强调了“严格”单调性。若在三分过程中遇到
,当函数严格单调时,令 或 均可。如果函数不严格单调,即在函
数中存在一段值相等的部分,那么我们无法判断定义域的左右边界如何缩小,三分法就不再适
用。
【第 137 页】【0x32 约数】【 例题 Hankson 的趣味题】
解法二中间,结合两种情况,有以下结论:
若
,则
只有一种取法,即
。
若
,则
只有一种取法,即
。
若
,则
只有一种取法,即
。
若
,则
可取
之间的任意值,共有
种取法。
其他情况,
无解。
【第 385 页】【0x67 Tarjan 算法与有向图连通性】【有向图的强连通分量】
程序第三行,low[x] = min(low[x], dfn[ver[i]]);
【第 393 页】【0x68 二分图的匹配】【二分图判定】
伪代码文本框中,if v[y] == color,判定无向图不是二分图,算法结束
【第 411 页】【0x6A 网络流初步】【 最大流】
图片下边的一段,最后一行,原二分图每条边的容量设为 1,再求最大流即可。
II. 一般勘误
这部分勘误比较微小,主要是手滑或者拼写错误,读者自己也很容易发现。