《算法竞赛入门经典》习题源码 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;
}
}
}
}