《算法竞赛入门经典（第2版）》第三章习题题解

《算法竞赛入门经典》习题源码 Github开源：https://github.com/RyanHe123/Classic-Introduction-to-Algorithmic-Competition
本文中的习题题解为本人完成，如果存在错误或可以改进的地方，欢迎在评论区提出，谢谢！

习题3-1 得分（ACM/ICPC Seoul 2005，UVa1585）

给出一个由O和X组成的串（长度为1~80），统计得分。每个O的得分为目前连续出现的O的个数，X的得分为0。例如：OOXXOXXOOO的得分为1+2+0+0+1+0+0+1+2+3。

#include<stdio.h>
int main()
{
	int n;
	scanf("%d", &n);
	int i = 0;
	getchar();
	for (; i < n; i++)
	{
		char ch; int sum = 0;
		int state = 0;
		while ((ch = getchar()) !='\n')
		{
			if (ch == 'O')
			{
				state++;
				sum += state;
			}
			else
			{
				state = 0;
			}
		}
		printf("%d\n", sum);
	}
}

习题3-2 分子量（ACM/ICPC Seoul 2007，UVa1586）

给出一种物质的分子式（不带括号），求分子量。本题中的分子式只包含4种原子，分别为 C，H，O，N，原子量分别为12.01，1.008，16.00，14.01（单位：g/mol）。例如：C6H5OH的分子量为94.108g/mol。

#include<stdio.h>
#include<ctype.h>
#include<string.h>
char s[90];
int main()
{
	int n;
	scanf("%d",&n);
	int i=0;
	for(;i<n;i++)
	{
		double atom;
		int count=1;
		scanf("%s",s);
		int j;
		double sum=0;
		for(j=0;j<strlen(s);j++)
		{
			switch(s[j])
			{
				case 'C':atom=12.01;break;
				case 'H':atom=1.008;break;
				case 'O':atom=16.00;break;
				case 'N':atom=14.01;break;
			}
			if(isdigit(s[j+1])!=0)
				count=s[++j];
			while(isdigit(s[j+1])!=0)
				count=count*10+s[++j];
			sum+=count*atom;
		}
		printf("%.3f\n",sum);
	}
}

习题3-3 数数字（ACM/ICPC Danang 2007，UVa1225）

把前n（n≤10000）个整数顺次写在一起：123456789101112…数一数0~9各出现多少次（输出10个整数，分别是0，1，…，9出现的次数）。

#include<stdio.h>
#include<math.h> 
int main()
{
	int t;
	scanf("%d", &t);
	int i;
	for (i = 0; i < t; i++)
	{
		int a[10] = { 0 };
		int n;
		scanf("%d", &n);
		int j;
		for (j = 1; j <= n; j++)
		{
			int num = j;
			while (num != 0)
			{
				a[num % 10]++;
				num /= 10;
			}
		}
		for (j = 0; j < 9; j++)
			printf("%d ", a[j]);
		printf("%d\n", a[9]);
	}
}	

习题3-4 周期串（UVa 455）

如果一个字符串可以由某个长度为k的字符串重复多次得到，则称该串以k为周期。例如，abcabcabcabc以3为周期（注意，它也以6和12为周期）。
输入一个长度不超过80的字符串，输出其最小周期。

#include<stdio.h>
#include<string.h>
int main()
{
	int n;
	scanf("%d",&n);
	int i;
	for(i=0;i<n;i++)
	{
		char s[100];
		scanf("%s",s);
		int t;
		for(t=1;t<=strlen(s);t++)
		{
			//一开始忽略了结尾不是完整周期结束的情况 
			if(strlen(s)%t!=0)
				continue;
			int j=0,state=1;
			for(;j<strlen(s);j++)
			{
				if(s[j]!=s[j%t])
				{
					state=0;
					break;
				}
			}
			if(state==1)
				{
					if(i!=0)printf("\n");
				printf("%d\n",t);break;
				}
		}
	}
}

习题3-5 谜题（ACM/ICPC World Finals 1993，UVa227）

有一个5*5的网络，恰好有一个格子是空的，其他格子各有一个字母，一共四种指令，A,B,L,R，分别表示把空格的上下左右的相邻字幕移到空格中。输入初始网络和指令序列(以0结束)，输出指令执行完毕后的网络，如果有非法指令，应输出，“This puzzle has no final configuration.”

//这道题的输出格式有很多坑，PE了无数次 
#include<stdio.h>
int main()
{
	 //输入矩阵
	int kase=1,state;
	int i,j;
	for(;;)
	{
	state=1;
	int x,y;
	char p[5][6],ch;
	for(i=0;i<5;i++)
	{
		fgets(p[i],7,stdin);
		if(p[0][0]=='Z'&&p[0][1]=='\n')
			return 0;
 	}
 	//搜索空格位置 
	for(i=0;i<5;i++)
	{
		for(j=0;j<5;j++)
		{
			if(p[i][j]==' ')
			{x=i;y=j;}
		}
	} 	
 	while((ch=getchar())!='0')
 	{
 		switch(ch)
 		{
 			case'A':if(x==0)state=0;
			 else{p[x][y]=p[x-1][y];p[x-1][y]=' ';x--;}break;	//边界判断和移动
 			case'B':if(x==4)state=0;
			 else{p[x][y]=p[x+1][y];p[x+1][y]=' ';x++;}break;
 			case'L':if(y==0)state=0;
			 else{p[x][y]=p[x][y-1];p[x][y-1]=' ';y--;}break;
 			case'R':if(y==4)state=0;
			 else{p[x][y]=p[x][y+1];p[x][y+1]=' ';y++;}break;
		}
	}
	//输出 
	if(kase!=1)
	printf("\n");
	printf("Puzzle #%d:\n",kase++);
	if(state==0)
	printf("This puzzle has no final configuration.\n");
	else
	{
	for(i=0;i<5;i++)
	{
		for(j=0;j<5;j++)
		{
			printf("%c",p[i][j]);
			if(j!=4)printf(" "); 
		}
		printf("\n");
	} 	
	}
	 getchar();
	}
}

习题3-6 纵横字谜的答案（ACM/ICPC World Finals 1994，UVa232）

输入一个r行c列的网格，，黑格用‘*’表示，每个白格都填有一个字母。如果一个白格的左边相邻位置或者上边相邻位置没有白格（可能是黑格，也可能出了网格边界），则称这个白格是一个起始格。首先把所有的起始格从上到下，从左到右的顺序编号为1，2，3…

#include<stdio.h>
int main()
{
	int a,b;
	int kase=1;
	while(scanf("%d",&a)&&a!=0)
	{
		scanf("%d",&b);
		if(kase!=1)
		printf("\n"); 
		char p[a][b+1];int n[a][b];
		int i,j;
		getchar();//用这行吞掉输入a和b时产生的\n 
		for(i=0;i<a;i++)
			for(j=0;j<b;j++)n[i][j]=0;//给n数组初始化0 
		//读取行列式
		for(i=0;i<a;i++)
			fgets(p[i],b+2,stdin);
		//标记起始格
		int count=1;
		for(i=0;i<b;i++)
		if(p[0][i]!='*')n[0][i]=count++;		//标记第一行 
		for(i=1;i<a;i++)
		{
			if(p[i][0]!='*')n[i][0]=count++;
			for(j=1;j<b;j++)
			if((p[i][j-1]=='*'||p[i-1][j]=='*')&&p[i][j]!='*') n[i][j]=count++;
		}
		/*for(i=0;i<a;i++)
		for(j=0;j<b;j++)
		{
			printf("%d ",n[i][j]);d
			if(j==b-1)printf("\n");
		}*/
		//寻找符合条件单词 
		printf("puzzle #%d:\nAcross\n",kase++);
		//横向 
		for(i=0;i<a;i++)
		for(j=0;j<b;j++)
		{
			if(j==0&&p[i][0]!='*')
			{
				printf("%3d.",n[i][0]);
				while(p[i][j]!='*'&&j<b)
				putchar(p[i][j++]);
				printf("\n");
			}
			while(p[i][j]=='*'&&j<b){
				j++;
			}
			if(j>=b)break;
			printf("%3d.",n[i][j]);
			while(p[i][j]!='*'&&j<b)
				putchar(p[i][j++]);
				printf("\n");
		 } 
		//纵向 还是要按照横向顺序搜索，比横向复杂 
		printf("Down\n");
		int temp; 
		for(i=0;i<a;i++)
		for(j=0;j<b;j++)
		{
			if(i==0&&p[0][j]!='*')
			{
				printf("%3d.",n[0][j]);
				temp=i;
				while(p[temp][j]!='*'&&temp<a)
				putchar(p[temp++][j]);
				printf("\n");
			}
			if(i>0&&p[i][j]!='*'&&p[i-1][j]=='*')
			{
				printf("%3d.",n[i][j]);
				temp=i;
				while(p[temp][j]!='*'&&temp<a)
				putchar(p[temp++][j]);
				printf("\n");
			}

		 } 
		 
	} 
	
 } 

习题3-7 DNA序列（ACM/ICPC Seoul 2006，UVa1368）

输入m个长度均为n的DNA序列，求一个DNA序列，到所有序列的总Hamming距离尽量小。两个等长字符串的Hamming距离等于字符不同的位置个数，例如，ACGT和GCGA的Hamming距离为2（左数第1, 4个字符不同）。
输入整数m和n（4≤m≤50, 4≤n≤1000），以及m个长度为n的DNA序列（只包含字母A，C，G，T），输出到m个序列的Hamming距离和最小的DNA序列和对应的距离。如有多解，要求为字典序最小的解。例如，对于下面5个DNA序列，最优解为TAAGATAC。
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

#include<stdio.h>
int main()
{
	int n;
	scanf("%d", &n);
	int t;
	for (t = 0; t < n; t++)
	{
		int m, n;
		scanf("%d %d", &m, &n);
		char s[50][1100];
		int i,j;
		for (j = 0; j < m; j++)
			scanf("%s", s[j]);
		//读取字符串，二维数组 
		
		int sum = 0;
		for (j = 0; j < n; j++)
		{
			int a[4] = { 0 };
			for (i = 0; i < m; i++)
			{
				
				//逐位读取出现次数 
				switch (s[i][j])
				{
				case'A':a[0]++; break;
				case'C':a[1]++; break;
				case'G':a[2]++; break;
				case'T':a[3]++; break;
				}
			}
			int max = 0, index = 0;
			int z;
			//找到出现次数最多的字母 
			for (z = 0; z < 4; z++){
				if(a[z]==max)
				{
					if(z<index)
					index=z;
				}
				if (a[z] > max)
				{
					index=z;
					max = a[z];  // 如果出现次数相同输出字典序小的解 
				}
			}
			sum += m - max;	
			switch (index)
			{
			case 0:putchar('A'); break;
			case 1:putchar('C'); break;
			case 2:putchar('G'); break;
			case 3:putchar('T'); break;
			}
		}
		printf("\n%d\n", sum);
	}

}

习题3-8 循环小数（ACM/ICPC World Finals 1990，UVa202）

输入整数a和b a大于等于0小于等于3000,b大于等于1小于等于3000,输出a/b的循环小数表示以及循环节长度。如果循环周期大于50,只显示50位，之后的全部用…表示

#include<stdio.h>
#include<string.h>
struct combine
{
	int x, y;
};// 记录除数和余数 
combine c[2000] = { 0 }; int yu[3000] = { 0 };//记录余数 ，数组一定要开在main外面，不然会出问题 
int main()
{
	int a, b;
	while (EOF != scanf("%d", &a))
	{
		scanf("%d", &b);
		int n = a;
		int d = a / b;
		c[0].y = a % b;
		yu[a%b]++;
		a = a % b * 10;
		int i;
		for (i = 1;; i++)//当有相同余数时，停止循环 
		{
			c[i].x = a / b; c[i].y = a % b;
			if (yu[a%b] == 1)
				break;
			else
				yu[a%b]++;
			a = a % b * 10;
		}
		int j, l;
		for (j = 0;; j++)//寻找前一次出现相同余数的位置 
		{
			if (c[j].y == a % b)
			{
				l = i - j;
				break;
			}
		}
			printf("%d/%d = %d.", n, b, d);
			int t;
			for (t = 1; t <= j; t++)
				printf("%d", c[t].x);
			printf("(");
			for (; t <= i; t++)
			{
				if (t == 51)
				{
					printf("..."); break;
				}
				printf("%d", c[t].x);
			}
			printf(")\n   %d = number of digits in repeating cycle\n\n",l);//此题的输出格式给的很模糊，需要在每个output之间加一个blank line 
		memset(c, 0, sizeof(c));
		memset(yu, 0, sizeof(yu));
	}
}

习题3-9 子序列（UVa10340）

输入两个字符串s和t，判断是否可以从t中删除0个或多个字符（其它字符顺序不变），得到字符串s.
例如：abcde可以得到bce，但无法得到dc.

#include<stdio.h>
#include<string.h>
//字符串一定要开大一些，刚开始开的比较小，就RE了 
char s[1000000],t[1000000];
int main()
{
	//读取字符串
	while((s[0]=getchar())!=EOF)
	{
		int i=1;
		while((s[i]=getchar())!=' ')
			i++;
		s[i]='\0';
		i=0;
		while((t[i]=getchar())!='\n')
			i++;
		int index=0; 
		for(i=0;i<strlen(t);i++)
	{
		if(s[index]==t[i])
			index++;
		
	}
		if(index==strlen(s))
		printf("Yes\n");
		else
		printf("No\n");
		//初始化数组，防止上一次实验对下一次有影响 
		memset(s,0,sizeof(s));
		memset(t,0,sizeof(t));
	 } 
}

习题3-10 盒子（ACM/ICPC NEERC 2004，UVa1587）

多实例测试。给出6个矩形的长和宽，判断这6个面是不是可以围成一个长方体，若可以围成，则输出“POSSIBLE”（不包含引号），否则输出“IMPOSSIBLE”（不包含引号），每个输出占一行。

struct rectangle
{
	int x, y;
};
void internal_swap(struct rectangle &r1)
{
	if (r1.x > r1.y)
	{
		int temp;
		temp = r1.x;
		r1.x = r1.y;
		r1.y = temp;
	}
}
void external_swap(rectangle &r1, rectangle &r2)
{
	if (r1.x > r2.x)
	{
		rectangle temp;
		temp = r1;
		r1 = r2;
		r2 = temp;
	}
	if (r1.x == r2.x&&r1.y > r2.y)
	{
		rectangle temp;
		temp = r1;
		r1 = r2;
		r2 = temp;
	}
}
#include<stdio.h>
int main()
{
	rectangle rec[6];
	while (scanf("%d %d", &rec[0].x,&rec[0].y)!=EOF)
	{
		internal_swap(rec[0]);
		int i;
		for (i = 1; i < 6; i++)
		{
			scanf("%d %d", &rec[i].x,&rec[i].y);
			internal_swap(rec[i]);
		}
		int j;
		for (i = 0; i < 5; i++)
		{
			for (j = 0; j < 5 - i; j++)
			{
				external_swap(rec[j], rec[j + 1]);
			}
		}
		int state = 1;
		for (i = 0; i < 6; i += 2)
		{
			if (rec[i].x != rec[i + 1].x || rec[i].y != rec[i + 1].y)
				state = 0;
		}
		if (rec[0].x != rec[2].x || rec[0].y != rec[4].x || rec[2].y != rec[4].y)
			state = 0;
		if (state == 1)
			printf("POSSIBLE\n");
		else
			printf("IMPOSSIBLE\n");
	}
}

习题3-11 换低档装置（ACM/ICPC NEERC 2006，UVa1588）

//a在前和b在前都尝试进行插入，对两个方向的最小长度进行比较，输出最小的长度
#include<stdio.h>
#include<string.h> 
int main()
{
	char a[200], b[200];
	while (EOF != scanf("%s", a))
	{
		scanf("%s", b);
		int la = strlen(a), lb = strlen(b), s1, s2, s;
		int i, j; int state_2 = 0;
		//a在前 
		for (i = 0; i < la; i++)
		{
			int state = 1;
			for (j = 0; j < lb; j++)
			{
				if (a[i + j] + b[j] - '0' - '0' > 3)
				{
					state = 0;
					break;
				}
			}
			if (state == 1) {
				//输出上和下中最长的那一个
				state_2 = 1;
				s1 =( (i + lb)>la? (i + lb):la); break;
			}
			if (state_2 == 0)
				s1 = la + lb;
		}
		state_2 = 0;
		//b在前 
		for (i = 0; i < lb); i++)
		{
			int state = 1;
			for (j = 0; j < la; j++)
			{
				if (b[i + j] + a[j] - '0' - '0' > 3)
				{
					state = 0;
					break;
				}
			}
			if (state == 1)
			{
				state_2 = 1;
				s2 = ((i + la) > lb ? (i + la) : lb);
				break;
			}
			if (state_2 == 0)
			{
				s2 = la + lb;
			}
		}
		if (s1 > s2)s = s2;
		else s = s1;
		printf("%d\n", s);
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
	}
	return 0;
}

习题3-12 浮点数（UVa11809）

这道题笔者想了很久都没想出来（是我太菜了），于是在网上找了大神的题解，贴在这里。链接：https://blog.csdn.net/crazysillynerd/article/details/43339157

//非原创，链接：https://blog.csdn.net/crazysillynerd/article/details/43339157 
#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
 
using namespace std;
 
int main() {
    double M[20][40];
    long long E[20][40];
 
    // 打表
    for(int i = 0; i <= 9; ++i) for(int j = 1; j <= 30; ++j) {
        double m = 1 - pow(2, -1 - i), e = pow(2, j) - 1;
        double t = log10(m) + e * log10(2);
        E[i][j] = t, M[i][j] = pow(10, t - E[i][j]);
    }
 
    // 输入并输出结果
    string in;
    while(cin >> in && in != "0e0") {
        // 处理输入
        for(string::iterator i = in.begin(); i != in.end(); ++i) if(*i == 'e') *i = ' ';
        istringstream ss(in);
        double A; int B;
        ss >> A >> B;
        while(A < 1) A *= 10, B -= 1;
        // 在打好的表中寻找答案
        for(int i = 0; i <= 9; ++i) for(int j = 1; j <= 30; ++j) {
            if(B == E[i][j] && (fabs(A - M[i][j]) < 1e-4 || fabs(A / 10 - M[i][j]) < 1e-4)) {
                cout << i << ' ' << j << endl;
                break;
            }
        }
    }
}