优雅数

优雅枚举

给定两个数 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
#include<iostream>
using namespace std;

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;
}