题目链接：http://codeforces.com/contest/1277/problem/A
题目大意：
求区间 ([1,n]) 范围内有多少只包含一个数字的数。
比如：(1,77,777,44,999999) 都是只包含一个数字的数，而 (12,11110,6969,987654321) 这些不是。
解题思路：
本题可以采用枚举和数位DP解法来解决（当然，数位DP相对来说有些杀鸡用牛刀的感觉）。
枚举解法
首先，我们要确定，去除 (0) 以外，一个 (i) 位数最多有 (9) 个这样的数：
- (1)位数中总共有 (9) 个符合要求的数：(1,2,3,4,5,6,7,8,9)；
- (2)位数中总共有 (9) 个符合要求的数：(11,22,33,44,55,66,77,88,99)；
- (3)位数中总共有 (9) 个符合要求的数：(111,222,333,444,555,666,777,888,999)；
- ……
因为告诉我们 (1 le n le 10^9) ，所以我们最多考虑 (9) 位数即可。
也就是说，所有满足要求的数只有 (9 imes 9 = 81) 个，我们只需要枚举这 (81) 个数，然后判断有多少个 (le n) 即可。
实现代码如下：
#include<bits/stdc++.h>
using namespace std;
int T, n;
int solve() {
int cnt = 0;
for (int i = 1; i <= 9; i ++) {
int s = 0;
for (int j = 0; j < 9; j ++) {
s = s * 10 + i;
if (s > n) break;
cnt ++;
}
}
return cnt;
}
int main() {
cin >> T;
while (T --) {
cin >> n;
cout << solve() << endl;
}
return 0;
}
数位DP解法
我们定义状态 (f[pos][pre]) 表示当
- 点前所在的数位为第 (pos) 位，
- 前一位放置的元素是 (pre)（如果前一位没有放置任何元素则 (pre=0)）
时的方案总数。
并且开函数 dfs(int pos, int pre, bool limit) 用于求解：
- 点前所在的数位为第 (pos) 位；
- 前一位放置的元素是 (pre)（如果前一位没有放置任何元素则 (pre=0)）；
- (limit) 用于表示当前是否处于闲置转态
时的方案总数。
但是最终答案因为包含 (0) 这个方案，所以要减去 (1) 。
实现代码如下：
#include<bits/stdc++.h>
using namespace std;
int f[11][11], T, n, a[11];
void init() {
memset(f, -1, sizeof(f));
}
int dfs(int pos, int pre, bool limit) {
if (pos < 0) return 1;
if (!limit && f[pos][pre] != -1) return f[pos][pre];
int up = limit ? a[pos] : 9;
int tmp = 0;
for (int i = 0; i <= up; i ++) {
if (pre == 0) {
if (i == 0) tmp += dfs(pos-1, i, limit && i==up);
else tmp += dfs(pos-1, i, limit && i==up);
}
else if (i == pre) tmp += dfs(pos-1, i, limit && i==up);
}
if (!limit) f[pos][pre] = tmp;
return tmp;
}
int get_num(int x) {
int pos = 0;
while (x) {
a[pos++] = x%10;
x /= 10;
}
return dfs(pos-1, 0, true);
}
int main() {
init();
cin >> T;
while (T --) {
cin >> n;
cout << get_num(n)-1 << endl;
}
return 0;
}