《算法竞赛入门经典》第三章习题
《算法竞赛入门经典》（第二版）第三章习题
得分（Score）UVa1585
问题描述
如何计算你们的得分呢？，如“OOXXOXXOOO”。 “O”表示问题的正确答案，“X”表示错误的答案。那么它得分是由它自己和它刚刚以前连续的'O'只有当答案是正确的。
例如，第10个问题的分数是由其自身和它的两个先前连续的“0”获得的3。
因此，“OOXXOXXOOO”的得分是通过“1 + 2 + 0 + 0 + 1 + 0 + 0 + 1 + 2 + 3”计算的10。你要编写一个计算测试结果分数的程序。
题解代码
#include<iostream>
using namespace std;
int main()
{
char c[100];
int n,score,tot;
bool TR = false;
scanf("%d",&n);
while(n--)
{
cin>>c;
score=tot=0;
for(int i=0;c[i]!='\0';i++)
{
if(c[i]=='O')
{
TR=true;
score+=(++tot);
}
else if(c[i]=='X')
{
TR=false;
tot=0;
}
}
cout<<score<<endl;
}
return 0;
}
分子量（Molar Mass）UVa1586
问题描述
HJL是一个从不讽刺人的品学兼优的好孩子，她最近沉迷学习化学而不能自拔。然而计算一个分子的相对分子质量使她烦不胜烦，因此她决定请你写一个程序来帮助她计算这种麻烦的事情。
已知：
①C代表的碳元素的相对原子质量为12.01，H代表的氢元素的相对原子质量为1.008，O代表的氧元素的相对原子质量为16.00，N代表的氮元素的相对原子质量为14.01。
②一个分子的相对分子质量等于组成这个分子的所有原子的相对原子质量的和：例如，分子式为C6H5OH的分子的相对分子质量为：12.016+1.0085+16.00+1.008=94.108。
题解代码
#include<stdio.h>
#include<string.h>
int main()
{
int n;
char s[100];
scanf("%d",&n);
while(n--)
{
double add = 0,sum = 0;
int num=0;
memset(s,0,sizeof(s));
scanf("%s",s);
for(int i=0;i<strlen(s);i++)
{
num=1;
if(s[i]>='0' && s[i]<='9') continue;
if(s[i]=='C') add=12.01;
if(s[i]=='H') add=1.008;
if(s[i]=='O') add=16.00;
if(s[i]=='N') add=14.01;
if(s[i+1]>='0' && s[i+1]<='9')
{
num=s[i+1]-'0';
if(s[i+2]>='0' && s[i+2]<='9') num=num*10+s[i+2]-'0';
}
sum+=add*num;
}
printf("%.3f\n",sum);
}
return 0;
}
数数字（Digit Counting）UVa1225
问题描述
Trung is bored with his mathematics homeworks. He takes a piece of chalk and starts writing a sequence of consecutive integers starting with 1 to N (1 < N < 10000) . After that, he counts the number of times each digit (0 to 9) appears in the sequence. For example, with N = 13 , the sequence is:
12345678910111213
In this sequence, 0 appears once, 1 appears 6 times, 2 appears 2 times, 3 appears 3 times, and each digit from 4 to 9 appears once. After playing for a while, Trung gets bored again. He now wants to write a program to do this for him. Your task is to help him with writing this program.
题解代码
#include<iostream>
#include<cstring>
int num[10];
using namespace std;
int main()
{
memset(num,0,sizeof(num));
int n;
cin>>n;
while(n--)
{
memset(num,0,sizeof(num));
int w;
cin>>w;
for(int i=1;i<=w;i++)
{
int j=i;
while(j)
{
num[j%10]++;
j=j/10;
}
}
for(int i=0;i<9;i++)
cout<<num[i]<<" ";
cout<<num[9];
cout<<endl;
}
return 0;
}
周期串（Periodic Strings）UVa455
问题描述
如果一个字符串可以被某个长度为k的字符串重复多次得到，则称这个字符串的周期为k。例如，字符串“abcabcabcabc”以3为周期（当然，他也以6、12等等为周期）。
现在请你编写一个程序，求出任一长度不超过80的字符串的最小周期。
题解代码
谜题（Puzzle）UVa227
问题代码
A children's puzzle that was popular 30 years ago consisted of a 5X5 frame which contained 24 small
squares of equal size. A unique letter of the alphabet was printed on each small square. Since there
were only 24 squares within the frame, the frame also contained an empty position which was the same
size as a small square. A square could be moved into that empty position if it were immediately to the
right, to the left, above, or below the empty position. The object of the puzzle was to slide squares
into the empty position so that the frame displayed the letters in alphabetical order.
The illustration below represents a puzzle in its original con guration and in its con guration after
the following sequence of 6 moves:
- The square above the empty position moves.
- The square to the right of the empty position moves.
- The square to the right of the empty position moves.
- The square below the empty position moves.
- The square below the empty position moves.
- The square to the left of the empty position moves.
题解代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char map[6][6];
char order[100];
int main()
{
int fx,fy;
bool valid;
char temp;
int count=1;
while(cin.getline(map[0],6))
{
if (strcmp (map[0],"Z") == 0) return 0;
if(count>1) cout<<endl;
for(int i=1;i<5;i++) cin.getline(map[i],6);
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
{
if(map[i][j]==' ')
{
fx=i;
fy=j;
}
}
int w=0;
while(cin>>temp)
{
order[w++]=temp;
if(temp=='0') break;
}
getchar();
//cout<<order<<endl;
valid = true;
for(int i=0;order[i]!='0';i++)
{
if(order[i]=='A' && fx>=1) {map[fx][fy]=map[fx-1][fy]; map[fx-1][fy]=' '; fx--;}
else if(order[i]=='A' && fx==0) {valid = false; break;}
else if(order[i]=='B' && fx<=3) {map[fx][fy]=map[fx+1][fy]; map[fx+1][fy]=' '; fx++;}
else if(order[i]=='B' && fx==4) {valid = false; break;}
else if(order[i]=='L' && fy>=1) {map[fx][fy]=map[fx][fy-1]; map[fx][fy-1]=' '; fy--;}
else if(order[i]=='L' && fy==0) {valid = false; break;}
else if(order[i]=='R' && fy<=3) {map[fx][fy]=map[fx][fy+1]; map[fx][fy+1]=' '; fy++;}
else if(order[i]=='R' && fy==4) {valid = false; break;}
}
if(valid)
{
cout<<"Puzzle #"<<count++<<":"<<endl;
for(int i=0;i<5;i++)
{
for(int j=0;j<4;j++)
cout<<map[i][j]<<" ";
cout<<map[i][4]<<endl;
}
//cout<<endl;
}
else
{
cout<<"Puzzle #"<<count++<<":"<<endl;
cout<<"This puzzle has no final configuration."<<endl;
}
memset(map,0,sizeof(map));
memset(order,0,sizeof(order));
}
return 0;
}
