比例简化

在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有 1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为 1498:902

不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。

现给出支持人数 A，反对人数 B，以及一个上限 L，请你将 A 比 B 化简为 A’ 比 B’，

  • 要求在 A’ 和 B’ 均不大于L，且 A’ 和 B’ 互质的前提下，
  • A’ / B’ ≥ A / B
  • 且 A’ / B’ − A / B的值尽可能小

输入：

共一行三个整数 A, B, L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限

输出：

共一行两个整数 A’，B’，中间用一个空格隔开，表示化简后的比例

样例：

1
1498 902 10
1
5 3

参考代码

==思路==：

若从1开始枚举，

如果枚举出一个答案 A’，B’（互质），当在继续枚举出一个新的答案 A’，B’（不互质），必然存在一个原来就有的A’，B’（互质）

并且新的答案与原来的答案，比例应该是一样的。

  • 即使用两个暴力for循环遍历，保证答案满足A’ / B’ ≥ A / B ，且A’ / B’ − A / B的值尽可能小即可。
1

3.OnlineJ516：奶牛碑文

约翰和他的奶牛在大草原漫游，在一块石头上发现了一些有趣的碑文。碑文似乎是一个神秘古老的语言，只包括三个大写字母 C,O,W。

尽管约翰看不懂，但是令他高兴的是，C,O,W的顺序形式构成了一句他最喜欢的奶牛单词 “COW”。

现在，他想知道有多少次 COW出现在文本中。

如果 COW内穿插了其他字符，只要COW字符出现在正确的顺序，约翰也不介意。

他也不介意出现不同的COW共享一些字母。例如CWOW出现了1次COW，CCOW算出现了2次COW，CCOOWW算出现了8次COW。

输入：

第一行一个整数 N。（1≤N≤105）

第二行为含有 N 个字符的字符串，字符只可能是 C,O,W。

输出：

输出 COW 作为输入字符串的子串出现的次数（不一定是连续的），答案可能会很大。

1
2
6
COOWWW
1
6

参考代码

==思路==：

  1. 暴力法：三重for循环分别对C,O,W进行遍历，可能会导致超时。
  2. 利用前缀和思想：空间复杂度换时间复杂度，
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
#include<iostream>
using namespace std;

char str[100005];
int numc[100005], numw[100005], n;
long long ans;

int main() {
	cin >> n >> str;
	for (int i = 0; str[i]; ++i) {//从前向后遍历 计算有多少个C（前缀和C）
		if (i == 0) {
			numc[i] = (str[i] == 'C');
		} else {
			numc[i] = numc[i - 1] + (str[i] == 'C');
		}
	}
	for (int i = n - 1; i >= 0; --i) {//从后向前遍历 计算有多少个W（后缀和W）
		if (i == n - 1) {
			numw[i] = (str[i] == 'W');
		} else {
			numw[i] = numw[i + 1] + (str[i] == 'W');
		}
	}
	for (int i = 0; str[i]; ++i) {//计算经过第i个O时的答案
		if (str[i] == 'O') ans += (long long)numc[i] * numw[i];
	}
	cout << ans << endl;
	return 0;
}

4.OnlineJ517：三角形个数

输入一根木棒的长度 n，将其分成三段，每段的长度是正整数，输出由这三小段木棒组成的不一样的三角形个数。

输入：

第一行一个整数 n。（1 ≤ n ≤ 104）

输出：

输出组成的不一样的三角形的个数。

1
10
1
2

样例说明：

两个能组成的三角形边长分别为 2,4,4 和 3,3,4。

参考代码

==思路==：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;

int main() {
	int ans = 0;
	int n; cin >> n;
	//注意枚举范围
	for (int i = 1; i <= n / 3; ++i) {//枚举最小边
		for (int j = i; j <= (n - i) / 2; ++j) {//枚举次小边
			if ((i + j) > (n - i - j)) {//判断最长边的合法性
				ans++;
				//cout << i << " " << j << " " << n - i - j << endl;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

5.OnlineJ519：优雅数（优雅枚举）

给定两个数 L,R 求 L,R 之间（含）有多少个“优雅数”。

优雅数的定义：把一个数看做一个长度为 n 的字符串，n 个字符中 n−1 个全相同，有且仅有一个字符不同。例如 33323,119 都是优雅的，99999, 2332 都是不优雅的。

输入：

输入一行两个整数 L, R。（100 ≤ L ≤ R ≤ 1016）

输出：

输出两数间优雅数的个数。

1
110 133
1
13

样例说明：

1
110,112,113,114,115,116,117,118,119,121,122,131,133

参考代码

==思路==：

  1. 思路1：暴力法，遍历两数区间，直接对优雅数进行判定。
  2. 思路2：构造优雅数，将区间之内的所有优雅数直接构造出来，判定是否构造的优雅数是否在给定区间范围内。
  • 单独的数字是几
  • 多个的数字是几
  • 优雅数的长度
  • 单独的数字在优雅数中的位置（构造优雅数）
    • 若一堆数为0的话，单独的数字必须要在优雅数的首位（不允许前导零）
    • 若一个数为0的话，单独的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
#include<iostream>
using namespace std;

// 1. 构造优雅数，将区间之内的所有优雅数直接构造出来，判定是否构造的优雅数是否在给定区间范围内。
// - 单独的数字是几
// - 多个的数字是几
// - 优雅数的长度
// - 单独的数字在优雅数中的位置（构造优雅数）
//     - 若一个数为0的话，单独的0数字必须不能在首位（不允许前导零）
//     - 若一堆数为0的话，单独的数字必须要在优雅数的首位（不允许前导零）

int main() {
	long long ans = 0;
	long long a, b;
	cin >> a >> b;
	for (int i = 0; i < 10; ++i) {//枚举单个的数字
		for (int j = 0; j < 10; ++j) {//枚举多个的数字
			if (i == j) continue;
			for (int k = 3; k < 18; ++k) {//枚举优雅数的数字长度
				for (int l = 1; l <= k; ++l) {//枚举单独的数字在优雅数中的位置
					if (i == 0 && l == 1) continue;
					if (j == 0 && l != 1) break;
					long long temp = 0;
					for (int n = 1; n <= k; ++n) {//构造优雅数
						if (n == l) temp = temp * 10 + i;//将第n位数置为 i
						else temp = temp * 10 + j;//将第n位数置为 j
					}
					if (temp >= a && temp <= b) {
						ans++;
						//cout << temp << endl;
					}
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}