算法竞赛入门经典（第2版）紫书 第三章数组和字符串 习题_紫书入门经典

习题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。

样例输入
5
OOXXOXXOOO
OOXXOOXXOO
OXOXOXOXOXOXOX
OOOOOOOOOO
OOOOXOOOOXOOOOX

样例输出
10
9
7
55
30

问题分析

直接判断OX串，若为O，则累加器++；当累加器遇到X时，重置为零。

代码

#include <iostream>
#include <cstring>

using namespace std;

int main(){
   
	int T;
	cin >> T;
	
	while(T--){
   
		char str[85];
		int sum = 0, count = 0;
		cin >> str;
		int len = strlen(str);
		
		for(int i=0; i<len; i++){
   
			if(str[i] == 'O'){
   
				count ++;
				sum += count;
			}
			else count = 0;
		}
		cout << sum << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

习题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。

样例输入
4
C
C6H5OH
NH2CH2COOH
C12H22O11

样例输入
12.010
94.108
75.070
342.296

问题分析

分子式中的分子有两种情况：
1、原子后无数字，直接判断是什么原子，加入原子量
2、原子后有数字，判断数字为多少、原子是什么，计算此原子总原子量

代码

#include <iostream>
#include <cstring>
#include <ctype.h>
#include <cstdio>

using namespace std;

int mol(char* s, int l, int k){
   
	int t = 0;
	while(k<l){
   
		if(isdigit(s[k+1])){
   
			t = t*10 + (s[k+1]-'0');
			k++;
		}
		else break;
	}
	return t;
}
 
int main(){
   
	int T;
	cin >> T;
	
	while(T--){
   
		double sum = 0.0;
		char s[105];
		cin >> s;
		int len = strlen(s);
		
		for(int i=0; i<len; i++){
   
			if(isalpha(s[i]) && isdigit(s[i+1])){
   
				int t = mol(s, len, i);
				switch(s[i]) {
   
					case 'C':sum += 12.01*t; break;
					case 'H':sum += 1.008*t; break;
					case 'O':sum += 16.00*t; break;
					case 'N':sum += 14.01*t; break;
				}
			}
			else{
   
				switch(s[i]) {
   
					case 'C':sum += 12.01; break;
					case 'H':sum += 1.008; break;
					case 'O':sum += 16.00; break;
					case 'N':sum += 14.01; break;
				}
			}
			
		}
		printf("%.3f",sum);
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

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

题目描述

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

问题分析

从1遍历到n，用一个数组a存放0~9各出现的数字

代码

#include <iostream>
#include <cstring>

using namespace std;

int main(){
   
	int T, n;
	int a[11];
	
	cin >> T;
	memset(a, 0, sizeof(a));
	
	while(T--){
   
		cin >> n;
		for(int i=1; i<=n; i++){
   
			int t=i;
			while(t){
   
				a[t%10]++;
				t /= 10;
			}
		}
		
		for(int i=0; i<10; i++){
   
			cout << a[i] << " ";
		}
		cout << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

题目描述

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

样例输入
1
HoHoHo

样例输出
2

问题分析

要求出最小周期，首先遍历字符串，当遍历到的字符与首位字符s[0]不相同则周期n++，当与s[0]相同，则开始验证n是否为最小周期。
首先，若n确实是周期，则一定能被字符串长度整除，若不能整除，则肯定不是周期，那么则继续遍历；
但是若n能被字符串长度整除，也不能确定就一定是周期，要进一步判断，在这里设一个循环，循环次数为（字符串长度/n）-1，这个个数就是后面的字符串重复第一个周期的次数，每次都进入函数判断，是否子串与首个周期相同，若每次都相同。则找到了最小周期。

代码

#include <iostream>
#include <cstring>

using namespace std;

//判断子串与首个周期是否相同
int f(int res, int j, char* s){
   
	int i, a = 0;
	for(i = j*res+0; i<j*res+res; i++){
   
		if(s[i] != s[a]) 
			return 0;
		a++;
	}
	return 1;
}

int main(){
   
	int T;
	cin >> T;
	
	while(T--){
   
		int res = 1, flag = 0;
		char 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26