题目链接：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 \times 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;
}