f[len][tv][u]表示长度为len,最高位topV = tv, 数字中含有u的个数
C++ 代码
# include <bits/stdc++.h>
# include <cmath>
using namespace std;
const int N = 11;
int f[N][10][10];
void init() {
for (int tv = 0; tv <= 9; tv++) f[1][tv][tv] = 1;
for (int len = 2; len < N; len++) {
for (int tv = 0; tv <= 9; tv++) {
for (int u = 0; u <= 9; u++) {
if (tv == u) f[len][tv][u] += pow(10, len - 1);
for (int nv = 0; nv <= 9; nv++) {
f[len][tv][u] += f[len - 1][nv][u];
}
}
}
}
}
int dp(int n, int u) { // 计算从0到n的整数中数字u出现多少次
if (n == 0) return u == 0 ? 1 : 0;
vector<int> a;
while (n) a.push_back(n % 10), n /= 10;
int res = 0, last = 0;
for (int i = a.size() - 1; i >= 0; i--) {
int tv = a[i];
for (int lv = (i == a.size() - 1); lv < tv; lv++) { // lv : left value
res += f[i + 1][lv][u];
}
// 之前出现u的个数为last,例如3350,统计数为3,当便利到5时,3出现2次,那么以33开头,后两位以0,1,
// 2,3,4开头的数(一共50个),高位都有2个3, 3300 - 3349高位(tv之前的位)里面,共有 2 *5 * pow(10, 1) == 100个3
res += last * tv*pow(10, i);
if (tv == u) {
last++;
}
if (i == 0) res += last;
}
for (int len = 1; len < a.size(); len++) {
for (int tv = len!=1; tv <= 9; tv++) {
res += f[len][tv][u];
}
}
return res;
}
int main() {
int a, b;
init();
while (cin >> a >> b , a) {
if (a > b) swap(a, b);
for (int i = 0; i <= 9; ++ i) cout << dp(b, i) - dp(a - 1, i) << ' ';
cout << endl;
}
return 0;
}
有一个疑问
if( nums.size() == 1 && k == 0 ) //为什么要加这个判断呢
return 1;
少这个判断会出错
感谢,代码超级清晰!
请问 dp 里最后那两个循环是在算啥啊 为啥我感觉前面就已经算完了呀
那个循环实际上是在算所有0 - n-1位数中的答案个数,上面的那个大循环其实只是在算n位数上的情况
我怎么感觉这么写比原来还要复杂 =-= 。。。
想不出
f[len][tv][u]
这个状态岂不是 gg 了