《蓝书刘汝佳算法竞赛入门经典勘误》由会员分享，可在线阅读，更多相关《蓝书刘汝佳算法竞赛入门经典勘误（6页珍藏版）》请在金锄头文库上搜索。
1、#算法竞赛入门经典勘误 关于勘误下面的勘误很多来自于热心读者，再次向他们表示衷心的感谢！我并不清楚这些错误实际是在哪个版本中改正过来的，所以麻烦大家都看一下。 有发现新错误的欢迎大家在留言中指出，谢谢！ 一些一般性的问题运算符?已经被废弃，请用 min、max 代替（代码仓库中的代码已更新，g+ 4.6.2 下编译通过） 重大错误p24. 最后一行， “然后让 max=INF,而 min=-INF”应该是“然后让 max=-INF, 而min=INF”。 (感谢 imxivid） p43. 最后，判断 si.j是否为回文串的方法也不难写出：int ok = 1; for(k = i; i= 0
2、 j+) 3. 4. if (si - j != si + j) break; 5. if (j*2+1 max) max = j*2+1; x = pi - j; y = pi + j; 6. 7. for (j = 0; i - j = 0 j+) 8. 9. if (si - j != si + j + 1) break; 10. if (j*2+2 max) 11. max = j*2+2; x = pi - j; y = pi + j + 1; 12. 13. p53. 例题 4-1. 组合数. 输入非负整数 n 和 m，这里的 n 和 m 写反了。应是“输入非负整数 m 和 n”。
3、 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, for(;) s += k; if(s = n) if(k % 2 = 1) printf(%d/%dn, s-n+1, k-s+n); else printf(%d/%dn, k-s+n, s-n+1); bre
4、ak; k+; return 0; 以及： #include #include int main() int n; while(scanf(%d, &n) = 1) int k = (int)floor(sqrt(8.0*n+1)-1)/2 - 1e-9)+1; int s = k*(k+1)/2; if(k % 2 = 1) printf(%d/%dn, s-n+1, k-s+n); else printf(%d/%dn, k-s+n, s-n+1); return 0; 上述代码已经更新到代码仓库中。 p83. 应为 am * an = am+n。 (感谢 zr95.vip) p85. 两
5、张插图下面的文字“顺时针” 、 “逆时针”反了。 (感谢 zr95.vip) p107. dfs 函数有误，应为： void dfs(int x, int y) if(!matxy | visxy) return; / 曾经访问过这个格子，或者当前格子是白色 visxy = 1; / 标记(x,y) 已访问过 dfs(x-1,y-1); dfs(x-1,y); dfs(x-1,y+1); dfs(x ,y-1); dfs(x ,y+1); dfs(x+1,y-1); dfs(x+1,y); dfs(x+1,y+1); / 递归访问周围的八个格子 (感谢 ) p124. 图 7-5 最右边的有两
6、个结点(3,1,*,*)，应该只有一个。下面一段第一行的“它只有 18个结点”也应该为 17 个 (感谢 zr95.vip, imxivid) p134. 代码部分,vis36288 应为 vis362880。 （感谢 lizhiwei） P142 表格下面第一行的最后，应该是 2n (感谢 imxivid） p152. 8.4.3【分析】情况 2 的“由贪心策略，k 比 j 轻”应为“由贪心策略，j 比 k 轻” 。 (感谢 zr95.vip) p159.【分析】一个 n 层数字三角形的完整路线有 2n 条。改为 2n-1 条。 （感谢 imxivid） p160. 160 页的方法 3 i
7、nt 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 (i
8、nt) ans; (感谢zr95.vip) p181. 例 10-1 的代码有误，改为： #include #include const int maxn = 100 + 10; int main() char nmaxn; int m; scanf(%s%d, n, i+) ans = (int)(long long)ans * 10 + ni - 0) % m); printf(%dn, ans); return 0; (感谢zr95.vip) p188. 中间的边乘边除，(n-i)/n 前面应加上(double)强制类型转换，不然结果会变成 0. （感谢 imxivid） p200. 情
9、况 2 第 2 行， “则 T+(u, v)”应为“则 T+(u, v)”。 （感谢 imxivid） p204. 中间代码的下面第二行，因此可以用“”应为 priority_queue, greater q。原文多写了个 vector。 （感谢 imxivid） p205. 下面的程序的第一个注释，应该是迭代 n-1 次。 （感谢 imxivid） p207. 最大流问题上面，图 11-4(b)的方案并不是最优的。可以找到增广路：从 s 到 v2 到v3 到 t，残量分别是 5(13)，4(9)，5(20)，由此可以得到一条由 s 到 t 的增广路，所以最大的运送量应该是 23 而不是 19
10、 (感谢东北师大附中王玉。我还欠你一本书) p214. 第三行，Skenia 应该是 Skiena 小错误包括比较明显的笔误或者排版问题。 p2.“实验 4”下方的“3+4”应为“3-4 ”。 (感谢 zr95.vip) p4. 例 1-1【分析】中“平面几何”改成“几何”比较妥当，因为底面积算是立体几何中的概念 :) (感谢 zr95.vip) p5. 页脚. “不信的话用 gcc-ansi 编译试试。 ”这里的 gcc 和减号之间应有一个空格，即 gcc -ansi p20. 程序 2-4 倒数第三行. printfA，多了一个 A，应该是 printf p70. 样例输出中的后双引号格式
11、有问题。 p107. 两个程序的排版都有点小问题。上面的程序，倒数第三行的最后一个 dfs 应和它上面那一行的最后一个 dfs 对齐，这样整齐一些；第二个程序最后一个右花括号 应该和上一个左花括号对齐。 p116. 7.1.4 的【分析】中“从 n+1 开始”应为“从 S+1 开始 ”。 (感谢 zr95.vip) p124. 插图 7-4 “a)皇后的攻击范围 ”没有画出范围。原稿中是有的，不知怎么没印出来. (感谢 zr95.vip) p180. 最上面，例 1 最后一句， “即 X=-6，Y=3 是 6x+15y=9”， “是”应为“时” 。 （感谢 imxivid） p187. 最后一
12、段“不管是 C36523 还是 36523 都无法”应为“不管是 P36523 还是” 。(感谢 zr95.vip) 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 的作用是在一个字符串中
13、找一个子串，参见： http:/ Comment by , Aug 25, 2011 1、160 页的方法 3 int d(int i, int j) if (di?j? = 0) .这里会产生一个重定义错误，因为函数和数组共用了一个标识符 2、162 页，dp 函数里面有一个运算符是 ?= ?这种复合了条件表达式和赋值表达式的运算符，我没有看过他的用法，也没有成功使用过 3、107 页那个深搜算法，(x - 1, y)这个方向被搜索了两次。 Comment by , Oct 6, 2012 第 2 页“实验 4”下方的“3+4”应为“3-4 ”。 第 4 页例 1-1【分析】中“平面几何 ”
14、应为“立体几何” （或“几何” ） 。 第 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); .
