算法
闫氏DP分析法(数位DP)
若统计x在1 ~ n之间出现的次数,则可以统计x在每一位出现的次数。然后相加即可。
可以先把n的每一位保存起来,然后依次从最高位进行枚举,假如第i位为ai那么第i位为x的情况数量就是第i位前面的数字与10^i相乘即可,然后再判断ai与x大小,若ai>x则再次加上10^i若ai==x则加上ai后面的数字再加1.
如果x为0的话那么就从次高位进行判断,且判断0~ai的时候不能从零开始了要从1开始。
时间复杂度
参考文献
C++ 代码
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int front(vector<int> a, int l, int r)
{
int res = 0;
for(int i = l; i >= r; i --)
res = res * 10 + a[i];
return res;
}
int pow_10(int x)
{
int res = 1;
while(x -- )res *= 10;
return res;
}
int dp(int n, int x)
{
vector<int> c;
while(n)c.push_back(n % 10), n /= 10;
int res = 0;
for(int i = c.size() - 1 - (x == 0); i >= 0; i --)
{
if(i != c.size() - 1){
res += front(c, c.size() - 1, i + 1) * pow_10(i);
if(!x) res -= pow_10(i);
}
if(c[i] == x) res += front(c, i - 1, 0) + 1;
else if(c[i] > x)res += pow_10(i);
}
return res;
}
int main()
{
int a, b;
while(cin >> a >> b, a || b)
{
if(a > b)swap(a, b);
for(int i = 0; i < 10; i ++)
cout << dp(b, i) - dp(a - 1, i) << ' ';
puts("");
}
return 0;
}