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

各位读者:

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

第三部,P66 队列的封闭面积问题,更好的代码如下:

//封闭面积问题

#include<bits/stdc++.h>

using namespace std;

int Map[11][11];

int dx[4]= {1,0,-1,0};                               //建立方向偏移数组

int dy[4]= {0,-1,0,1};

 void BFS(int x, int y)

{  queue <int> X,Y;                                   //此处使用STL里的queue

  Map[x][y] = 1;

  X.push(x);

  Y.push(y);

  while(!X.empty())

  {

    for(int i=0; i<=3; ++i)                          //寻找相邻的区域

    {

      int xx=X.front()+dx[i];

      int yy=Y.front()+dy[i];

      if(!Map[xx][yy] && xx>0 && xx<=10 && yy>0 && yy<=10)

      {

        Map[xx][yy]=1;

        X.push(xx);

        Y.push(yy);

      }

    }

    X.pop();

    Y.pop();

  }

}

 

int main()

{

  for(int i = 1; i <= 10; ++i)

    for(int j = 1; j <= 10; ++j)

      scanf("%d", &Map[i][j]);

  for(int i = 1; i <= 10; ++i)            //最外面一圈每个点都要搜索

  {

    if(!Map[i][1])  BFS(i, 1);            //虽然有多个BFS,但因为标记过的不会重走

    if(!Map[i][10]) BFS(i, 10);           //所以时间复杂度和单个BFS是一样的

    if(!Map[1][i])  BFS(1, i);

    if(!Map[10][i]) BFS(10, i);

  }

  int ans=0;

  for(int i = 1; i <= 10; ++i)

    for(int j = 1; j <= 10; ++j)

      if(!Map[i][j])

        ans++;

  printf("%d\n", ans);

  return 0;

}

第三部227页,完整代码应改为:

//太空堡垒
#include <bits/stdc++.h>
using namespace std;

struct
{
int a,b,sum;
} t[140000];
int people[50010]; //people[50010]存放每个点上的船数

void BuildTree(int x,int y,int num) //构造线段树
{
t[num].a=x; //确定左端点为x
t[num].b=y; //确定右端点为y
if(x==y) //如果x==y,说明已经是叶子结点了
t[num].sum=people[y]; //则人数为单个的堡垒飞船数
else
{
BuildTree(x,((x+y)>>1),num+num); //递归构造左儿子树
BuildTree(((x+y)>>1)+1,y,num+num+1); //递归构造右儿子树
t[num].sum=t[num+num].sum+t[num+num+1].sum;//父结点等于左右子结点的和
}
}

int Query(int L,int R,int num) //初始num为1,即从根结点开始查找
{
if(L <= t[num].a && R >= t[num].b) //如果在包含区间内,则返回值
return t[num].sum;
int min = (t[num].a+t[num].b)>>1; //取左右端点的中间
int ans = 0;
if(L <= min)
ans += Query(L, R, num+num); //递归左子树
if(R > min)
ans += Query(L, R, num+num+1); //递归右子树
return ans;
}

void Update(int i,int j,int num) //第i个堡垒增加或减少j个飞船
{
t[num].sum+=j;
if(t[num].a==i && t[num].b==i) //如果找到i的叶子结点,则停止
return;
if(i>(t[num].a+(t[num].b)>>1)) //如果点i在该线段的右边
Update(i,j,num+num+1); //则递归进入右子结点
else
Update(i,j,num+num); //否则递归进入左子结点
}

int main()
{
int a,b,n,t,Case=0;
cin>>t;
while(t--)
{
scanf("%d",&n); //注意读写要加速,否则会超时
people[0]=0;
for(int i=1; i<=n; i++)
scanf("%d",&people[i]);
BuildTree(1,n,1); //从根结点t[1]开始建线段树
printf("Case %d:\n",++Case);
getchar(); //用于忽略换行符
string command;
while(cin>>command)
{
if(command=="End")
break;
cin>>a>>b;
if(command=="Query")
printf("%d\n",Query(a,b,1)); //从根结点t[1]开始
if(command=="Add")
Update(a,b,1); //从根结点t[1]开始
if(command=="Sub")
Update(a,-b,1); //从根结点t[1]开始
}
}
return 0;
}

第二部 604页,邮局问题输出应该是距离总和的最小值。

第二部 600页,机器分配输入第一个数应该是小组数N,第二个数是设备台数M

第二部 52页,图1.26及后面算法分析有误,应为:

第二部 428页   原书代码有错误,参考代码改为STL应为

//楼兰宝藏
#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;
}

第二部 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

Last modified: Thursday, 3 January 2019, 2:57 am