XieNaoban's Blog
0%

算法竞赛入门经典 3-1UVa1585 3-2UVa1586 3-3UVa1225

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 2.6k 阅读时长 ≈ 2 分钟

书上具体所有题目：http://pan.baidu.com/s/1hssH0KO（我也是在网上找到的pdf，但不记得是从哪里搜刮到的了，就重新上传了一遍）

PS：第一次写博客分享我的代码，不知道我对csdn的使用姿势对不对。想不出来要说些什么哈o(▽)o，那就直接开工，先写一篇试试。

题目：算法竞赛入门经典 3-1/UVa1585：Score

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#define MAX 83

int main()
{
	int num;
	std::cin >> num;
	while (num--) {
		char str[MAX], *ch = str;
		int score = 0, sum = 0;
		std::cin >> str;
		while (*ch != '\0')
			sum += (*(ch++) == 'X' ? score = 0 : ++score);
		std::cout << sum << '\n';
	}
	return 0;
}

分析：MAX定为83而不是题目限制的80是为了传说中的鲁棒性，其他好像没什么好说的。。。下一题。。

题目：算法竞赛入门经典 3-2/UVa1586：Molar Mass 代码：

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
#include<iostream>
#include<iomanip>

inline float f(char c)//得到分子量
{
	switch (c) {
	case 'C':return 12.01;
	case 'H':return 1.008;
	case 'O':return 16.00;
	case 'N':return 14.01;
	default:std::cerr << "error!\n";
	}
	std::cout << '\'' << c << '\'';
	exit(0);
}
inline bool g(char c)//判断char的内容是不是数字
{
	if (c >= '0'&&c <= '9') return 1;return 0;
}

int main()
{
	int num;//判断输入个数
	std::cin >> num;
	std::cout << std::fixed << std::setprecision(3);
	while (num--) {
		float sum = 0;
		char str[83], *ch = str;
		std::cin>>str;
		while (*ch != '\0') {//此情况下不是'\0'就是字母
			int n = 0;
			char c = *ch;
			while (g(*++ch))//是数字
				n = n * 10 + *ch - '0';
			if (!n) n = 1;
			sum += f(c)*n;//若不是字母则报错结束程序
		}
		std::cout << sum << '\n';
	}
	return 0;
}

分析：这次写了注释，好像也没什么好说的了。。不过对于inline，我知道编译器如果觉得这个函数不够小巧，会忽略inline，但我一直不知道要多小才能编译器不忽略inline。然后因为程序比较小，所以没有给两个函数取名字，直接叫f和g。

题目：算法竞赛入门经典 3-3/UVa1225：Digit Counting 代码：

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
#include<iostream>
#include<cmath>

int main()
{
	int num;
	std::cin >> num;
	while (num--) {
		int n, n2,d=1, times[10] = { 0 };//n:输入的数字,n2:备份n,times:保存各数字出现的次数
		do std::cin >> n;while (n >= 10000);
		n2 = n;
		while (n2 /= 10) ++d;//d为位数
		n2 = n;
		int t = 1, sum = 0;//t不断乘以10,sum代表所有数字一样多的部分
		while (d--) {//f代表某一位
			int f = n2 % 10;
			n2 /= 10;
			sum += n2*t;
			times[0] += (n2 - 1)*t;//0太奇葩，总比别人少一个，单独算
			for (int i = 0;i < f;++i) times[i] += t;
			times[f] += 1 + n%t;//当前位最大数字分开算
			t *= 10;
		}
		std::cout << times[0];
		for (int i = 1;i < 10;++i)
			std::cout << ' ' << (times[i] += sum);
		std::cout << '\n';
	}
	return 0;
}

分析：这题我看过网上其他人的做法，他们竟然真的把这个长长的数字串写进了字符数组，然后再遍历数组数一遍。总感觉这字符数组长度得爆炸而且慢。

这题的规律是：（划横线的是具体的那个数字）（以123为例）

第一列也就是121的那列，代表（除了零）所有数共有的部分（就比如123的前100中每个数字出现的一样多），在代码里用sum表示，比如对于十位上的每个数字，都出现了123/(10^2)10次

第二列 也就是XXX各+1那列，代表特殊的那几个地方，就比如十位上数字是2，那么那超过100的23（准确说是20，个位上3不算在里面的原因在最后一列）就在此计算，但此计算不包括2

而最后一列又是最特殊的，比如十位上的2的与别人不同的地方在此计算，十位2开头的数120、121、122、123，十位上的2出现（123%10+1）=4次

零我是分开单独算的，因为它比较奇葩，就比如1、2、3而不是01、02、03，十位上的0是不写的，其实规律一样的。

嗯、工科男表达能力太差了。。感觉我越说越复杂。。。果然多写写博客练练表达是有好处的。

这次就上传这几题，看题目难度和代码长度来判断每次上传多少题目。