蓝书刘汝佳算法竞赛入门经典勘误
#《算法竞赛入门经典》勘误
关于勘误?下面的勘误很多来自于热心读者，再次向他们表示衷心的感谢！我并不清楚这些
错误实际是在哪个版本中改正过来的，所以麻烦大家都看一下。
有发现新错误的欢迎大家在留言中指出，谢谢！
一些一般性的问题?运算符<、>已经被废弃，请用min、max代替（代码仓库中的代码已更新，
g++ 4.6.2下编译通过）
重大错误?p24. 最后一行，“然后让max=INF,而min=-INF”应该是“然后让max=-INF, 而
min=INF”。
(感谢imxivid）
p43. 最后，判断s[i..j]是否为回文串的方法也不难写出：int ok = 1; for(k = i; i<=j;
i++)应该为for(k = i; k<=j; k++)
(感谢imxivid）
p45. 第七行和第九行i-j+1应为i+j+1。修改后：
1. {
2. for (j = 0; i - j >= 0 && i + j < m; j++)
3. {
4. if (s[i - j] != s[i + j]) break;
5. if
(j*2+1 > max) { max = j*2+1; x = p[i - j]; y = p[i + j];} 6. } 7.
for (j = 0; i - j >= 0 && i + j + 1 < m; j++) 8. { 9. if
(s[i - j] != s[i + j + 1]) break; 10. if (j*2+2 > max) 11. {max = j*2+2; x = p[i - j]; y = p[i + j + 1]; } 12. }
13. }p53. 例题4-1. 组合数. 输入非负整数n和m，这里的n和m写反了。应是“输
入非负整数m和n”。
p54. 举例中的m和n也写反了（真是个悲剧），且C(20,1)=20。
p71. 《周期串》代码的第8行，j++应为i++。
p72. 代码的第7行，“return”改为“break”以和其他地方一致。
p81. k为奇数和偶数的时候，分子和分母的顺序是不一样的。正确代码为：
#include<> int main() { int n; while(scanf("%d", &n) == 1) { int k = 1, s
= 0; for(;;) { s += k; if(s >= n) { if(k % 2 == 1) printf("%d/%d\n", s-n+1, k-s+n); else printf("%d/%d\n", k-s+n,
s-n+1); break; } k++; } } return 0; }以及：
#include<> #include<> int main() { int n; while(scanf("%d", &n) == 1) { int
k = (int)floor((sqrt*n+1)-1)/2 - 1e-9)+1; int s = k*(k+1)/2; if(k % 2 ==
1) printf("%d/%d\n", s-n+1, k-s+n); else printf("%d/%d\n", k-s+n,
s-n+1); } return 0; }上述代码已经更新到代码仓库中。
p83. 应为am * an = am+n。
(感谢
p85. 两张插图下面的文字“顺时针”、“逆时针”反了。
(感谢
p107. dfs函数有误，应为：
void dfs(int x, int y) { if(!mat[x][y] || vis[x][y]) return; 图7-5最右边
的有两个结点(3,1,*,*)，应该只有一个。下面一段第一行的“它只有18个结点”也应该为
17个
(感谢, imxivid)
p134. 代码部分,vis36288应为vis362880。
（感谢lizhiwei）
P142 表格下面第一行的最后，应该是2^n
(感谢imxivid）
p152. 【分析】情况2的“由贪心策略，k比j轻”应为“由贪心策略，j比k轻”。
(感谢
p159.【分析】一个n层数字三角形的完整路线有2n条。改为2n-1条。
（感谢imxivid）
p160. 160页的方法3
int d(int i, int j) { ....会产生一个重定义错误，因为函数和数组共用了一个标识符。随便换一个数组名即可。
(感谢)
p171. 最上面，状态转移方程第二项应为f(k+1, j)。
（感谢imxivid）
p181. 例10-2的代码段会导致无穷递归。改为：
int pow_mod(int a, int n, int m) { if(n == 0) return 1; int x = pow_mod(a, n/2, m); long long ans = (long long)x * x % m; if (n%2 == 1) ans = ans * a % m; return (int) ans; }(感谢
p181. 例10-1的代码有误，改为：
#include
p188. 中间的边乘边除，(n-i)/n前面应加上(double)强制类型转换，不然结果会变成0. （感谢imxivid）
p200. 情况2第2行，“则T'+(u, v)”应为“则T+(u, v)”。
（感谢imxivid）
p204. 中间代码的下面第二行，因此可以用“……”应为priority_queue
（感谢imxivid）
p205. 下面的程序的第一个注释，应该是迭代n-1次。
（感谢imxivid）
p207. 最大流问题上面，图11-4(b)的方案并不是最优的。可以找到增广路：从s到v2到
v3到t，残量分别是5(13)，4(9)，5(20)，由此可以得到一条由s到t的增广路，所以最
大的运送量应该是23而不是19
(感谢东北师大附中王玉。我还欠你一本书)
p214. 第三行，Skenia应该是Skiena
小错误?包括比较明显的笔误或者排版问题。
p2.“实验4”下方的“3+4”应为“3-4”。
(感谢
p4. 例1-1【分析】中“平面几何”改成“几何”比较妥当，因为底面积算是立体几何中的
概念 :)
(感谢
p5. 页脚. “不信的话用gcc-ansi编译试试。”这里的gcc和减号之间应有一个空格，即
gcc -ansi
p20. 程序2-4倒数第三行. printfA，多了一个A，应该是printf
p70. 样例输出中的后双引号格式有问题。
p107. 两个程序的排版都有点小问题。上面的程序，倒数第三行的最后一个dfs应和它上面那一行的最后一个dfs对齐，这样整齐一些；第二个程序最后一个右花括号}应该和上一个左花括号{对齐。
p116. 的【分析】中“从n+1开始”应为“从S+1开始”。
(感谢
p124. 插图7-4 “a)皇后的攻击范围”没有画出范围。原稿中是有的，不知怎么没印出来... (感谢
p180. 最上面，例1最后一句，“即X=-6，Y=3是6x+15y=9”，“是”应为“时”。
（感谢imxivid）
p187. 最后一段“不管是C36523还是36523都无法……”应为“不管是P36523还是……”。(感谢
p190. 提示10-7上面一段，1,1,2,3,5,8……这行的下一行，“第n个兔子”应为“第n个月的兔子”。
（感谢imxivid）
p201. 图11-3的标题“路经”应为“路径”。
（感谢imxivid）
p207 最大流问题的第一段最后一行，“最多可以用9个物品”应为“最多可以有9个物品”。（感谢imxivid）
其他?p39页提到sprintf和strchr，但是只讲了sprintf。strchr的作用是在一个字符串中找一个子串，参见：
Comment by, Aug 25, 2011
1、160页的方法3
int d(int i, int j) {
if (dij >= 0) ....这里会产生一个重定义错误，因为函数和数组共用了一个标识符
2、162页，dp函数里面有一个运算符是" >= " 这种复合了条件表达式和赋值表达式的运算符，我没有看过他的用法，也没有成功使用过
3、107页那个深搜算法，(x - 1, y)这个方向被搜索了两次。
Comment by, Oct 6, 2012
第2页“实验4”下方的“3+4”应为“3-4”。
第4页例1-1【分析】中“平面几何”应为“立体几何”（或“几何”）。
第39页提到sprintf和strchr，但是只讲了sprintf。
第83页指数式am * an = am{{{*}}}n错误，应为am * an = am+n。
第85页两张插图下面的文字“顺时针”、“逆时针”反了。
第116页7.1.4的【分析】中“从n+1开始”应为“从S+1开始”。
第124页插图7-4 “a)皇后的攻击范围”没有画出范围
第124页图7-5最右边的叶子结点(3, 1, *, *)多了一个。
第152页8.4.3【分析】情况2的“由贪心策略，k比j轻”似乎应为“由贪心策略，j比k 轻”。
第181页例10-2的代码段
int pow_mod(int a, int n, int m) { int x = pow_mod(a, n/2, m); ... ...似乎显然会导致无穷递归。
第187页的最后一段“不管是C36523还是36523都无法……”似乎应为“不管是P36523)还是……”。
Comment by, Oct 6, 2012
第181页例10-1的代码没有定义n和m。并且n是作为字符串读取的，代码第8行的n[i]似乎应为n[i] - '0'。
Comment by project member, Oct 6, 2012
谢谢的回复！第4页的“底面积公式”实际上就是圆面积公式，说平面几何也是合理的。不过严密起见，改成“几何”确实更妥 :) 第124页有些意外，我的原稿是用灰色格子表示攻击范围的，不知为何印刷出来却没有。其他问题我都同意。第181页的两处代码错误很不应该，我得自我反省一下...
Comment by, Oct 19, 2012
P142 表格下面第一行的最后，应该是2^n。
P124 解答树修改以后，下面一段第一行的“它只有18个结点”也应该为17个。
P72 代码的第7行，“return”似乎改为“break”更好。
P71 代码的第8行，j++应为i++。
P70 样例输出的最后一个双引号格式似乎应和'not to be'后面的双引号一样。
P54 第二行，“很不幸……-19.手算不难得到……是1。”很不幸，这两个结果我都没能得到。C(N,M)=C(1，20)显然无意义。
P48 最后一行，sscanf、sprintf和sstream的功能似乎不是很相似。用sscanf读字符串时，（多条语句）每用一个sscanf都会从字符串开头开始读取，但用sstream，会接上次结束部分继续读。
P47 中间的代码，if(si == 1)应为if(si == '1')。
P43 最后，判断s[i..j]是否为回文串的方法也不难写出： int ok = 1; for(k = i; i<=j; i++)应该为for(k = i; k<=j; k++)
P24 最后一行，“然后让max=INF,而min=-INF”应该是“然后让max=-INF, 而min=INF”。
P21 小注：“如果将两次操作一起做，可以在一定程度上缓解这个问题。”我试了一下，似乎对缓解问题没有任何效果。不知道作者在这里说的是什么意思。
Comment by, Oct 27, 2012
代码在那里下载
Comment by, Oct 29, 2012
P21 现在好像看明白了，作者好像是让我们用double试一下两次操作一起做。
Comment by, Oct 29, 2012
P190 提示10-7上面一段，1,1,2,3,5,8……这行的下一行，“第n个兔子”应为“第n个月的兔子”。
P180 最上面，例1最后一句，“即X=-6，Y=3是6x+15y=9”，“是”应为“时”。
P171 最上面，状态转移方程第二项应为f(k+1, j)。
P159 【分析】一个n层数字三角形的完整路线有2n条，好像应该是2(n-1)条。
P156 分两步证明算法的正确性，我没看懂在说什么，不知道设的函数f(x)是什么意义。但是结论2第二行的“f(z)=f(x)+f(z)”似乎应为f(z)=f(x)+f(y)。
P152 乘船问题，情况2，改成j比k轻以后依然看不懂，哪个哪个不会超重，不知道到底怎么推出来的。
Comment by, Oct 29, 2012
P178 下面的代码，prime[c++] = i; 这句放到循环体内好像只能统计出1~m（根号n）范围内的素数吧……
Comment by, Oct 31, 2012
P211 “限于篇幅”上边，“我们规定capvu=0”是怎么回事虽然我没大看懂，但是觉得好像应该是capvv=0。
P207 最大流问题的第一段最后一行，“最多可以用9个物品”似乎应为“最多可以有9个物品”。
P205 下面的程序的第一个注释，好像应该是迭代n-1次。
P204 中间代码的下面第二行，因此可以用“……”应为priority_queue
P201 图11-3的标题“路经”应为“路径”。
P200 情况2第2行，“则T'+(u, v)”似乎应为“则T+(u, v)”。
P177的gcd函数我觉得写成return bgcd(b, a%b):a;更简单，不知道对不对……
终于把这本书看完了，感觉选这本书真是选对了，这是我看过的最明白好懂的OI书！感谢作者！如果不是这本书，好多东西我自己在别处都看不懂！找出这些错误就当是报答作者吧~为这本书做点贡献……我很快会把书正文部分所有例题和算法都写成程序然后发出来！Comment by, Nov 2, 2012
P183 中间的杨辉三角递推，C[i-1][j-1]和C[i-1]j会有负数下标的危险，外层循环应该为i=1，然后在外面加一句C00=1。内层虽然没有错误，但是我觉得改成j <= i比较好。 P173~174最优配对问题的代码好像有误。直接照着书上打进去，答案是不正确的。
Comment by, Nov 2, 2012
P188中间的边乘边除，(n-i)/n前面应加上(double)强制类型转换，不然结果会变成0. Comment by project member, Nov 3, 2012
感谢imxivid！你说的绝大多数都是对的，我会尽快写在勘误中。有几个代码错误之前已经在googlecode中改正了，但是忘记在勘误里写了，呵呵。其他几个需要说明的：P54是m 和n写反了，P48的sscanf/sstream的用法以及几个贪心问题的证明我稍后详细叙述；P47是故意的，也就是“实验2”里会发现这个函数得不到正确的结果，然后“改正”。P21就是说的用double。P211没问题。cap[v][u]=0是为了允许反向增广
Comment by, Nov 4, 2012
训练指南 p80 Uva 11627 翻译错误输出不是数量应是速度能通过的速度最大的滑雪板的速度（坑死了）
Comment by project member, Nov 4, 2012
回复Tankchen：啊，真是抱歉。另外请在训练指南的相应章节后汇报勘误哈，这里是《入门经典》的勘误页。还有，下载代码的方法是使用git。我会不定期打包放在downloads里面的，目前还没有...
Comment by, Dec 13, 2012
p77 貌似把冒泡排序和选择排序弄错了吧
Comment by, Jan 23, 2013
P38 最后一行可以用scanf("%s",si)读取第i个字符串这里有问题吧，什么意思啊Comment by, Feb 22, 2013
P31 习题2-2 水仙花数若3位数ABC满足ABC=A2+B2+C2 应为ABC=A3+B3+C3
Comment by, Mar 11, 2013
p50. 单词pig的输入方式写错了