算法竞赛（紫书）第三章习题题解
今天来发一波题解
3-1
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <stdlib.h>
#define maxn 1000000 + 10
using namespace std;
char s[maxn];
int main()
{
int n;
cin>>n;
while(n--){
cin>>s;
int len = strlen(s);
int ans = 0;
int count = 0;
for(int i = 0;i < len;i++){
if(s[i] == 'O') {ans++;count += ans;}
if(s[i] == 'X') ans = 0;
}
cout<<count<<endl;
}
return 0;
}
3-2
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define maxn 100000 + 5
char s[maxn];
int main()
{
int n;
cin>>n;
while(n--){
cin>>s;
int len = strlen(s);
double count = 0;
int ans = 0;
for(int i = 0;i < len;i++){
bool flagc=false,flagh=false,flago=false,flagn=false;
if(s[i] == 'C') flagc = true;
if(s[i] == 'H') flagh = true;
if(s[i] == 'O') flago = true;
if(s[i] == 'N') flagn = true;
ans = 0;
for(int j = i+1;j < len;j++){
if(s[j] >= '0' && s[j] <= '9'){
ans *= 10;
ans += int(s[j] - '0');
//cout<<"ans: ---"<<ans<<endl;
}
if(s[j] < '0' || s[j] > '9')
break;
}
//cout<<"ans: "<<ans<<endl;
//cout<<"flagc: "<<flagc<<endl;
//cout<<"flagh: "<<flagh<<endl;
//cout<<"flago: "<<flago<<endl;
//cout<<"flagn: "<<flagn<<endl;
if(ans == 0) ans = 1;
if(flagc)
count += 12.01 * ans;
if(flagh)
count += 1.008 * ans;
if(flago)
count += 16.00 * ans;
if(flagn)
count += 14.01 * ans;
}
printf("%.3f\n",count);
}
return 0;
}
3-3
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define maxn 10000 + 5
char str[maxn];
int c[maxn][10];
int main()
{
int n,t;
cin>>t;
while(t--){
memset(c,0,sizeof(c));
cin>>n;
for(int i = 1;i <= n;i++){
int a = i;
while(a > 0){
c[i][a%10]++;
a /= 10;
}
for(int j = 0;j < 10;j++){
c[i][j] += c[i-1][j];
}
}
cout<<c[n][0];
for(int i = 1;i < 10;i++)
cout<<" "<<c[n][i];
cout<<endl;
}
return 0;
}
3-4
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define maxn 10000 + 5
char s[maxn];
int main()
{
int t;
cin>>t;
while(t--){
cin>>s;
int k;
int len = strlen(s);
for(int i = 1;i <= len;i++){
if(len % i == 0){
for(k = i;k < len;k++){
if(s[k] != s[k%i])
break;
}
if(k == len) {
cout<<i<<endl;
break;
}
}
}
if(t) cout<<endl;
}
return 0;
}
3-5
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define maxn 10000 + 5
char s[10][10];
char c[101];
int main()
{
int kase = 0;
bool ff = true;
while(cin.getline(s[0],6)){
if(s[0][0] == 'Z') {ff = false;break;}
cin.getline(s[1],6);
cin.getline(s[2],6);
cin.getline(s[3],6);
cin.getline(s[4],6);
int x = 0,y = 0;
for(int i = 0;i < 5;i++){
for(int j = 0;j < 5;j++){
if(s[i][j] == ' ' || s[i][j] == 0){x = i;y = j;break;}
}
}
//cout<<"x: "<<x<<" y: "<<y<<endl;
int count = 0;
while(1){
scanf("\n%c",&c[count]);
if(c[count] == '0') break;
else count++;
}
//cout<<"count: "<<count<<endl;
getchar();c[count] = '0';
int flag = 0;
for(int i = 0;i < count;i++){
flag = 0;
if(c[i] == 'A') {
if(x == 0) {flag = 1;break;}
else {s[x][y] = s[x-1][y];s[x-1][y] = ' ';x--;continue;}
}
if(c[i] == 'B') {
if(x == 4) {flag = 1;break;}
else {s[x][y] = s[x+1][y];s[x+1][y] = ' ';x++;continue;}
}
if(c[i] == 'L') {
if(y == 0) {flag = 1;break;}
else {s[x][y] = s[x][y-1];s[x][y-1] = ' ';y--;continue;}
}
if(c[i] == 'R') {
if(y == 4) {flag = 1;break;}
else {s[x][y] = s[x][y+1];s[x][y+1] = ' ';y++;continue;}
}
}
if(++kase > 1)
printf("\n");
cout<<"Puzzle #"<<kase<<":"<<endl;
if(flag == 1) cout<<"This puzzle has no final configuration."<<endl;
else {
for(int i=0; i<5; i++)
printf("%c %c %c %c %c\n", s[i][0], s[i][1], s[i][2], s[i][3], s[i][4]);
}
//cout<<endl;
}
return 0;
}
3- 6
#include <stdio.h>
#include <string.h>
#include <string>
using namespace std;
int main()
{
char buf[12][12];
int num[12][12];
int r,c;
int p=0;
while(scanf("%d",&r) && r!=0)
{
scanf("%d",&c);
memset(num,0,sizeof(num));
for(int i=0;i<r;++i)
scanf("%s",buf[i]);
int m=1;
for(int i=0;i<r;++i)
{
for(int j=0;j<c;++j)
{
if(buf[i][j]=='*')
continue;
if((j-1)<0 || buf[i][j-1]=='*' || (i-1)<0 || buf[i-1][j]=='*')
{
num[i][j]=m++;
}
}
}
if(++p > 1)
printf("\n");
printf("puzzle #%d:\n",p);
printf("Across\n");
for(int i=0;i<r;++i)
{
int j=0;
while(j<c)
{
if(num[i][j] == 0 || buf[i][j] =='*')
{
j++;
continue;
}
printf("%3d.%c",num[i][j],buf[i][j]);
j++;
while(j<c && buf[i][j]!='*')
{
printf("%c",buf[i][j]);
j++;
}
printf("\n");
}
}
printf("Down\n");
for(int i=0;i<r;++i)
{
for(int j=0;j<c;++j)
{
if(num[i][j] == 0 || buf[i][j]=='*')
continue;
printf("%3d.%c",num[i][j],buf[i][j]);
num[i][j]=0;
int k=i+1;
while(k<r && buf[k][j]!='*')
{
printf("%c",buf[k][j]);
num[k][j]=0;
k++;
}
printf("\n");
}
}
}
return 0;
}
3-7
#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;
char grid[1005];
struct node {
int a,c,g,t;
}N[1005];
int main() {
int n,m;
int T;
scanf("%d",&T);
while(T--) {
scanf("%d %d",&n,&m);
for(int i = 0 ; i < m; i++)
N[i].a = N[i].c = N[i].g = N[i].t = 0;
for(int i = 0; i < n; i++) {
scanf("%s",grid);
for(int j = 0; j < m; j++) {
if(grid[j] == 'A') N[j].a++;
else if(grid[j] == 'C') N[j].c++;
else if(grid[j] == 'G') N[j].g++;
else if(grid[j] == 'T') N[j].t++;
}
}
char s[1005];
int maxx,ans = 0;
for(int i = 0; i < m; i++) {
s[i] = 'A';
maxx = N[i].a;
if(N[i].c > maxx) {
s[i] = 'C';
maxx = N[i].c;
}
if(N[i].g > maxx) {
s[i] = 'G';
maxx =N[i].g;
}
if(N[i].t > maxx) {
s[i] = 'T';
maxx = N[i].t;
}
ans += n - maxx;
}
s[m] = '\0';
printf("%s\n%d\n",s,ans);
}
return 0;
}
3-8
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
const int maxn = 10000 + 5;
int chu[maxn];
int yu[maxn];
int main()
{
int a,b;
while(scanf("%d %d",&a,&b) == 2 && b){
int c = a;
memset(chu,0,sizeof(chu));
memset(yu,0,sizeof(yu));
int m = 0,n = 0;
for(int i = 0;;i++){
bool flag = false;
yu[i] = a%b;
chu[i] = a/b;
a = a % b *10;
for(int k = 1;k < i;k++){
if(chu[i] == chu[k] && yu[i] == yu[k]){m = i;n = k;flag = true;break;}
}
if(flag) break;
}
printf("%d/%d = %d.",c,b,chu[0]);
for(int i = 1;i < n && i <= 50;i++)
printf("%d",chu[i]);
printf("(");
for(int i = n;i < m && i <= 50;i++)
printf("%d",chu[i]);
if(m>50) printf("...");
printf(")\n %d = number of digits in repeating cycle\n\n",m-n);
}
return 0;
}
3-9
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
const int maxn = 1000000 + 5;
char s[maxn],t[maxn];
int main()
{
while(cin>>s>>t){
int len = strlen(t);
int le = strlen(s);
int k = 0;
for(int i = 0;i < len;i++){
if(t[i] == s[k]) k++;
}
if(k == le) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
3-10
#include<bits/stdc++.h>
using namespace std;
struct box{
int x,y;
}a[6];
bool cmp(const box a,const box b)
{
return a.x==b.x?a.y>b.y:a.x>b.x;
}
int main()
{
while(cin>>a[0].x>>a[0].y)
{
int ans=1;
if(a[0].x<a[0].y) swap(a[0].x,a[0].y);
for(int i=1;i<6;i++)
{
cin>>a[i].x>>a[i].y;
if(a[i].x<a[i].y) swap(a[i].x,a[i].y);
}
sort(a,a+6,cmp);
if(memcmp(a,a+1,sizeof(box))||memcmp(a+2,a+3,sizeof(box))||memcmp(a+4,a+5,sizeof(box)))
ans=0;
if(a[0].x!=a[2].x||a[2].y!=a[4].y||a[0].y!=a[4].x)
ans=0;
if(ans) cout<<"POSSIBLE"<<endl;
else cout<<"IMPOSSIBLE"<<endl;
}
return 0;
}
3-11
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
char a[105];
char b[105];
int n1,n2;
int solve(char *a,char *b,int n){
int sumn = n1 + n2;
int minn = min(n1,n2);
int len = sumn;
for(int i = 0;i < n;i++){
int flag = 1;
int fix = min(n-i,minn);
for(int j = 0;j < fix;j++){
if(a[i+j] == '2' && b[j] == '2') {flag = 0;break;}
}
if(flag && len > sumn-fix) len = sumn - fix;
}
return len;
}
int main()
{
while(cin>>a>>b){
n1 = strlen(a);
n2 = strlen(b);
cout<<min(solve(a,b,n1),solve(b,a,n2))<<endl;;
}
return 0;
}
3-12
#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;
}
}
}
}
