解题思路
利用前缀和的思想,要想算出x~y的答案,可以算出从1~y的数据 减去 1~y的数据
那么问题就是如何快速算出1~n的数据呢
需要分情况来讨论
到这别急着去写
有一个重要的问题是0需要特殊判断
因为不能有前导零,所以第一位不可能是0,当判断0有几次的时候一定要从第二位开始判断
而且在处理第一种情况的时候,由于不能存在前导零,所以这一位前面不可能是0,也就是说abc的范围是001 – abc-1 , 别忘记特判
代码
#include<bits/stdc++.h>
using namespace std;
int power10(int o)
{
int res = 1;
while (o--){
res *= 10;
}
return res;
}
int get(vector<int> num, int l ,int r)
{
int res = 0;
for(int i=l;i>=r;i--){
res = res * 10 + num[i];
}
return res;
}
int count(int n, int d)
{
if(!n) return 0;
vector<int> v;
do{
v.push_back(n%10);
n/=10;
}while (n);
int m = v.size(), res = 0;
for(int i=m-1-!d;i>=0;i--){
if(i < m-1){
res += get(v,m-1,i+1) * power10(i);
if(!d) res -= power10(i);
}
if(v[i] > d){
res += power10(i);
}else if(v[i] == d){
res += get(v,i-1,0) + 1;
}
}
return res;
}
int main()
{
int x,y;
while (cin >> x >> y , x||y){
if(x > y) swap(x,y);
for(int i=0;i<=9;i++){
cout << count(y,i) - count(x-1,i) << " \n"[i == 9];
}
}
}