《算法竞赛宝典》勘误专用页

各位读者:

  大家好,因为本人水平有限,加之出版过程中的各个环节因素的影响,第一版不可避免地会有很多的错误出现,敬请大家发现错误后,请及时与本人联系(QQ:110289732),以便再版时更正,谢谢!本页面将不定期的更新勘误。

第二部 P517页唱片问题的方法一代码应为:

//唱片录制 ─方法1
#include <bits/stdc++.h>
using namespace std;

int g[21][21][21],l[21];

int main()
{
freopen("record.in","r",stdin);
freopen("record.out","w",stdout);
int n,m,t;
scanf("%d%d%d",&n,&m,&t);
for (int i=1; i<=n; i++)
scanf("%d",&l[i]);
for (int i=1; i<=n; i++)
for (int j=0;j<=m;j++)
for (int k=0; k<=t; k++)//k不超过唱片长度
{
if (k>=l[i])
g[i][j][k]=max(g[i-1][j][k],g[i-1][j][k-l[i]]+1);
else if(t-l[i]>=0 && j>0)
g[i][j][k]=max(g[i-1][j][k],g[i-1][j-1][t-l[i]]+1);
else
g[i][j][k]=g[i-1][j][k];
}
printf("%d\n",g[n][m][0]);
return 0;
}

第三部 P225页

若L>1,则[a,(a+b)/2]为T的左儿子;[(a+b)/2,b]为T的右儿子。
若L=1,则T为叶子结点。

应该是:
若L>0,则[a,(a+b)/2]为T的左儿子;[(a+b)/2+1,b]为T的右儿子。
若L=0,则T为叶子结点。

第三部 P226页,第二行:则其左儿子[1,5]和右儿子[5,10]应该是则其左儿子[1,5]和右儿子[6,10]

第一部 195页  第一个满足 n%p×p=0 改为第一个满足 n%(p×p)=0

 第一部 234页的表 10.3  第9行,第3列  X&~(1shl(k-1))应该是x&~(1<<(k-1))

第二部 动态规划中的楼兰宝藏测试数据有误(已更改),代码有误,正确代码如下:

//楼兰宝藏
#include <bits/stdc++.h>
using namespace std;

struct node
{
int x, y;
}s[100005];

int cmp(node a, node b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}

int main()
{
freopen("Treasure_map.in","r",stdin);
freopen("Treasure_map.out","w",stdout);
int n,m,p;
scanf("%d%d%d", &n, &m, &p);
vector <int> v;//此处vector当堆栈使用
for(int i = 0; i < p; i++)
scanf("%d%d", &s[i].x, &s[i].y);
sort(s, s+p, cmp);//按x值排序
for(int i = 0; i < p; i++)
{
//it为迭代器,upper_bound在vector里找到大于s[i].y的第一个位置
//upper_bound和lower_bound必须在有序的序列里使用,使用二分查找
vector<int>::iterator it=upper_bound(v.begin(),v.end(),s[i].y);
if(it != v.begin())//如果不是头元素
{
it--;
*it = s[i].y;//把该位置的值替换为point[i].y
}
else//如果s[i].y>头元素,则直接插入
v.insert(v.begin(), s[i].y);
}
printf("%d\n", v.size());
return 0;
}

第二部,逃亡,数学方法2

第一部,11页,5%2应改为5%3

第一部,41页,当grade的值为C,D时改为当grade非A,B,C值时

第一部,46页,coutinue改为continue

第一部,54页,已算法的值改为已算好的值

第一部,88页,j=j/2应改为n=n/2

第一部,100页,第三次隔3个按钮改为第四次隔3个按钮

第一部,134页,类似于100/5×5的算式改为100/(5×5)

第一部,154页,产生一个随机数(-90~32767)改为产生一个随机数(0~32767)

第一部,221页,代码第35行i<3改为i<N

第一部,保留字、类型名......都要首字母大写改为自定义类型名和重要变量名都要首字母大写

第二部 30页,输入样例6 76应为6 7 6

第二部,33页,两数和不大于k,则该轮中比k值小的.....此处的k全改为mid

第二部,120页,m=0改为n=0,且121页程序输出结果为由大到小

第二部 151页,代码21行,j<=1改为j<=i

第二部 212页,希尔排序的平均时间复杂度应为O(nlog2n)

第二部 204页,图5.7中的39应在最后一格

第二部,351页,代码18行和代码19行要注释掉。

第二部,359页,a[i]表示第i位数改为a[i]为当前未出现的元素中是排在第几个(从0开始)。

第二部,362页,代码42行cin>>n>>num改为cin>>num>>n

第二部, 387页, 算式应为  44445509678,且388页应改为:很显然,我们只要让ABCD分别代表0347

第二部    p443 表11.11中坐标(1,1)的数字不是3,是0  (感谢南外沈泽屹)

第二部,488页,每块魔法石应改为每堆魔法石

第二部,560页,第23、24行代码会因编译器版本不同而无法运行,改成:

                     f[i]=max(f[i],f[i-1]*a[i]);
                     f[i]=max(f[i],g[i-1]*a[i]);

                     g[i]=a[i];
                     g[i]=min(g[i],f[i-1]*a[i]);
                     g[i]=min(g[i],g[i-1]*a[i]);

第二部,660页,62行代码,将int i=1改为int i=0;63行代码将int j=1改成int j=0;

第三部,29页,图2.1中,d,c入栈应改为d,c出栈

第三部,105页,图4.31有错误

第三部 157页,heap[i]=map[1][i]改为heap[i]=map[i]

第三部,176页,代码见相关电子资源包

第三部,208页,多少中改为多少种

第三部,245页 图9.2的下标

第三部  248页  link[2]=2改为link[2]=1

最后修改: 2018年07月9日 星期一 11:30