习题3-1 得分（Score, 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>
#include<string.h> 
#define maxn 1000 + 10
char s[maxn];
int main() {
	scanf("%s", s);
	int oc=0,score=0;
	for(int i = 0; i < strlen(s); i++){
		if(s[i] == 'X') {
			oc=0;
			continue;
		}
		else{
			oc++;
			score+=oc; 
		}	
	}	
	printf("%d\n", score);
}

习题3-2 分子量（Molar Mass, 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<string.h>
#define maxn 1000 + 10
char a[maxn];
int main() {
	scanf("%s",a);
	double mass=0;
	for(int i = 0; i < strlen(a); i++){
		if(a[i+1] >='1' && a[i+1]<='9'){
			int x;
			x=a[i+1]-'0';//转为数值 
			switch(a[i]) {
			case 'C':mass+=12.01*x;break;
			case 'H':mass+=1.008*x;break;
			case 'O':mass+=16.00*x;break;
			case 'N':mass+=14.01*x;break;
			}
			i++;
		}
		else{
			switch(a[i]) {
			case 'C':mass+=12.01;break;
			case 'H':mass+=1.008;break;
			case 'O':mass+=16.00;break;
			case 'N':mass+=14.01;break;
			}
		}	
	}	
	printf("%.3fg/mol\n", mass);
}

习题3-3 数数字（Digit Counting , ACM/ICPC Danang 2007, UVa1225）

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

#include<stdio.h>
#include<string.h>
#define maxn 100000 + 10
char buf[maxn];
int main() {
	int n;
	scanf("%d",&n);
	int num[20];
	memset(num,0,sizeof(num));
	for(int i=1;i<=n;i++){
		sprintf(buf,"%d",i);
		for(int i=0;i<strlen(buf);i++) {
			int n2;
			n2=buf[i]-'0';
			num[n2]++;
			}
	}
	for(int i=0;i<9;i++){
		printf("%d ",num[i]);
	} 
	printf("%d\n",num[9]);
}

习题3-4 周期串（Periodic Strings, UVa455）

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

#include<stdio.h>
#include<string.h>
#define maxn 10000+10
char s[maxn];
int main(){
	scanf("%s",s);
	int len=strlen(s),tf=0;
	for(int i=2;i<len;i++){
		int state=1;
		if(len%i!=0)continue;
		for(int j=0;j<len;j++){
			if(s[j]!=s[j%i]){
				state=0;
				break;
			}
		}
		if(state){
			printf("%d\n",i);
			tf++;
			break;
		}
	}
	if(!tf)printf("No\n");	
	return 0;
}

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

有一个5*5的网格，其中恰好有一个格子是空的，其他格子各有一个字母。一共有4种指令：A, B, L, R，分别表示把空格上、下、左、右的相邻字母移到空格中。输入初始网格和指令序列（以数字0结束），输出指令执行完毕后的网格。如果有非法指令，应输出“This puzzle has no final configuration.”，例如，图3-5中执行ARRBBL0后，效果如图3-6所示。

#include<stdio.h>
#include<string.h>
#define maxn 10000+10
char s[maxn];
int main(){
	char a[5][5]={
	{'T','R','G','S','J'},
	{'X','D','O','K','I'},
	{'M',' ','V','L','N'},
	{'W','P','A','B','E'},
	{'U','Q','H','C','F'}};
	/*
	//手动输入
	char a[5][5];
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			scanf("%c",&a[i][j]);
	*/
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++){
			printf("%c",a[i][j]);
			if(j<4)printf(" ");
		}
		printf("\n");
	}
	scanf("%s",s);
	int x=2,y=1;
	char f[]="This puzzle has no final configuration.\n"; 
	for(int i=0;s[i]!='0';i++){
		switch(s[i]){
			case 'A': 
				if(x-1<0)printf("%s",f);
				else {
					a[x][y]=a[x-1][y];a[--x][y]=' ';
				}
				break;
			case 'B': 
				if(x+1>4)printf("%s",f);
				else {
					a[x][y]=a[x+1][y];a[++x][y]=' ';
				}
				break;
			case 'L': 
				if(y-1<0)printf("%s",f);
				else {
					a[x][y]=a[x][y-1];a[x][--y]=' ';
				}
				break;
			case 'R': 
				if(y+1>4)printf("%s",f);
				else {
					a[x][y]=a[x][y+1];a[x][++y]=' ';
				}
				break;
		}
	}
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++){
			printf("%c",a[i][j]);
			if(j<4)printf(" ");
		}
		printf("\n");
	}	
	return 0;
}

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

输入一个r行c列（1≤r，c≤10）的网格，黑格用“*”表示，每个白格都填有一个字母。如果一个白格的左边相邻位置或者上边相邻位置没有白格（可能是黑格，也可能出了网格边界），则称这个白格是一个起始格。
首先把所有起始格按照从上到下、从左到右的顺序编号为1, 2, 3,…，如图3-7所示。
接下来要找出所有横向单词（Across）。这些单词必须从一个起始格开始，向右延伸到一个黑格的左边或者整个网格的最右列。最后找出所有竖向单词（Down）。这些单词必须从一个起始格开始，向下延伸到一个黑格的上边或者整个网格的最下行。输入输出格式和样例请参考原题。

#include<stdio.h>
#include<string.h>
#define m 105
char s[m][m];
int sta[m][m];
int main(){
	int r,c,kase=0;
	while(scanf("%d%d\n",&r,&c)==2&&r){
		memset(sta,0,sizeof(sta));
		int pos=1;
		for(int i=0;i<r;i++){
			for(int j=0;j<c;j++){
				scanf("%c",&s[i][j]);
				if(s[i][j]=='*')continue;
				if(j<1||s[i][j-1]=='*'||i<1||s[i-1][j]=='*'){
					sta[i][j]=pos;
					pos++;
				}
			}
			getchar();
		}
		kase++;
		if(kase>1)printf("\n");
		printf("puzzle #%d:\n",kase);
		printf("Across\n");
		for(int i=0;i<r;i++){
			int j=0;
			while(j<c){
				if(s[i][j]=='*'||sta[i][j]==0){
					j++;
					continue;
					
				}
				printf("%3d.%c",sta[i][j],s[i][j]);
				j++;
				while(s[i][j]!='*'&&j<c){
					printf("%c",s[i][j]);
					j++;
				}
				printf("\n");
			}
		}
		printf("Down\n");
		for(int i=0;i<r;i++){
			for(int j=0;j<c;j++){
					if(s[i][j]=='*'||sta[i][j]==0)continue;
					printf("%3d.%c",sta[i][j],s[i][j]);
					sta[i][j]=0;
					int k=i+1;
					while(k<r&&s[k][j]!='*'){
						printf("%c",s[k][j]);
						sta[k][j]=0;
						k++;
					}
					printf("\n");	
				}
			}	
	}
	return 0;
}