蓝书刘汝佳算法竞赛入门经典勘误

《蓝书刘汝佳算法竞赛入门经典勘误》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#《算法竞赛入门经典》勘误关于勘误¶下面的勘误很多来自于热心读者，再次向他们表示衷心的感谢！我并不清楚这些错误实际是在哪个版本中改正过来的，所以麻烦大家都看一下。有发现新错误的欢迎大家在留言中指出，谢谢！一些一般性的问题¶运算符?已经被废弃，请用min、max代替（代码仓库中的代码已更新，g++4.6.2下编译通过）重大错误¶p24.最后一行，“然后让max=INF,而min=-INF”应该是“然后让max=-INF,而min=INF”。(感谢imxivid）p43.最后，判断s[i..j]是否为回文串的方法也不难写出：intok=1;for(k=i;i<=j;i++

2、)应该为for(k=i;k<=j;k++)(感谢imxivid）p45.第七行和第九行i-j+1应为i+j+1。修改后：1.{2.for(j=0;i-j>=0&&i+jmax){max=j*2+1;x=p[i-j];y=p[i+j];}6.}7.for(j=0;i-j>=0&&i+j+1max)11.{max=j*2+2;x=p[i-j];y=p[i+j+1];}12.}13.}p53

3、.例题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为奇数和偶数的时候，分子和分母的顺序是不一样的。正确代码为：#includeintmain(){intn;while(scanf("%d",&n)==1){intk=1,s=0;for(;;){s+=k;if(s>=n){if(k%2==1)printf("%d/%d

4、n",s-n+1,k-s+n);elseprintf("%d/%d",k-s+n,s-n+1);break;}k++;}}return0;}以及：#include#includeintmain(){intn;while(scanf("%d",&n)==1){intk=(int)floor((sqrt(8.0*n+1)-1)/2-1e-9)+1;ints=k*(k+1)/2;if(k%2==1)printf("%d/%d",s-n+1,k-s+n);elseprintf("%d/%d",k-s+n,s-n+1);}return0;}

5、上述代码已经更新到代码仓库中。p83.应为am*an=am+n。(感谢zr95.vip)p85.两张插图下面的文字“顺时针”、“逆时针”反了。(感谢zr95.vip)p107.dfs函数有误，应为：voiddfs(intx,inty){if(!mat[x][y]

6、

7、vis[x][y])return;//曾经访问过这个格子，或者当前格子是白色vis[x][y]=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)

8、;//递归访问周围的八个格子}(感谢zhongying822@163.com)p124.图7-5最右边的有两个结点(3,1,*,*)，应该只有一个。下面一段第一行的“它只有18个结点”也应该为17个(感谢zr95.vip,imxivid)p134.代码部分,vis36288应为vis362880。（感谢lizhiwei）P142表格下面第一行的最后，应该是2^n(感谢imxivid）p152.8.4.3【分析】情况2的“由贪心策略，k比j轻”应为“由贪心策略，j比k轻”。(感谢zr95.vip)p159.【分析】一个n层数字三角形的完整路线有2n条。改为2n-1条。（感谢im

9、xivid）p160.160页的方法3intd(inti,intj){....会产生一个重定义错误，因为函数和数组共用了一个标识符。随便换一个数组名即可。(感谢zhongying822@163.com)p171.最上面，状态转移方程第二项应为f(k+1,j)。（感谢imxivid）p181.例10-2的代码段会导致无穷递归。改为：intpow_mod(inta,intn,intm){if(n==0)return1;intx=pow_mod(a,n/2,m);longlongans=(longlong)x