题目描述

给定两个整数 a 和 b，求 a 和 b 之间的所有数字中0~9的出现次数。

例如，a=1024，b=1032，则 a 和 b 之间共有9个数如下：

1024 1025 1026 1027 1028 1029 1030 1031 1032

其中‘0’出现10次，‘1’出现10次，‘2’出现7次，‘3’出现3次等等…

输入格式

输入包含多组测试数据。

每组测试数据占一行，包含两个整数 a 和 b。

当读入一行为0 0时，表示输入终止，且该行不作处理。

输出格式

每组数据输出一个结果，每个结果占一行。

每个结果包含十个用空格隔开的数字，第一个数字表示‘0’出现的次数，第二个数字表示‘1’出现的次数，以此类推。

数据范围

0<a，b<100000000

样例

1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0

先统计出所有n位以内的数共出现0~9多少次，例如n=3时，统计1~999中0~9分别出现了多少次，统计方法如下：

0 0 0
0 0 1
0 0 2
. . .
9 9 9

为了统计方便，先给不足3位的数字补上前导0，对于个位上的0~9，十位和百位上的数有00~99共100种情况，每种情况都会使个位上的0~9增加一次；对于百位，千位类似，统计每一位后得到0~9共出现了300次。然后统计一下多加了几个前导0，
对于个位，只有000时出现一次前导0，对于十位，001~009出现10次，对于百位000~099出现了100次，所以共出现了111次前导0。

然后推广到n位数的情况，容易得到 0~9的个数为n*pow(10，n)，其中多了(111…11)(n个1)个0，

所以先预处理出cnt、cnt_0数组，cnt[i]存放i位的数字0~9，cnt_0[i]表示i为的数字多算了多少个0，初始化方式如下：

p[0]=1;
for(int i=1;i<=9;i++) p[i]=p[i-1]*10;
for(int i=1;i<=9;i++) cnt[i]=i*p[i-1];
for(int i=1;i<=9;i++) cnt_0[i]=p[i-1];
for(int i=1;i<=9;i++) cnt_0[i]+=cnt_0[i-1];

然后实现一个slove(int x)的函数，返回1~x分别需要多少个0~9。
假设x有t位，则先算出所有t位数需要多少个0~9，再减去从x+1~t个9的0~9的个数。
例如 当x=554时，先算出1~999需要0~9的个数，再算出555~999的个数。

1、计算1~999中0~9出现的次数：

这个比较简单，1~9出现的次数就是cnt[3]，0的个数是cnt[3]-cnt_0[3]，
即1~9位为：cnt[位数]，0为：cnt[位数]-cnt_0[位数]

2、计算555~999中0~9出现的次数：

将这里的555的每一位存到数组中（高位存在高地址），实现一个函数
get(vector <int> x)，返回从x到999，0~9中每个数出现的次数。

先将555~999拆分成如下几个部分

555->599
600->699
700->799
800->899
900->999

观察可以发现，5在百位上出现了100-55=45次，6~9在百位数都出现了100次，55~99出现了1次，0~99出现了4次，
所以5的次数直接加45，6~9的次数加100，55~99中0~9的次数可以将55递归传入
get(vector <int> x)得到，0~99中0~9出现的次数就是4*cnt[2]。

也就是将最高位取出记做h，然后h加上pow(10，位数+1)-取出最高位后的数，h+1~9都加上
pow(10，取出最高位后的位数)然后0~9都加上(9-h)*cnt[取出最高位后的位数]
再递归的算出get(取出最高位之后的数)加到答案里去。

因为get函数每次都将数字的最高位取出，然后把后面的数字再递归计算，所以当个位也被取出之后就终止了，
所以当传入的数组长度为0的时候就return

这样这道题就完美得解决了~

C++ 代码

#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=10;

int cnt[N]，p[N];
int cnt_0[N];
int a，b;

vector<int> get(vector<int> x)
{
    vector<int> ans(10，0);

    if(x.size()==0) return ans;

    int h=x.back();x.pop_back();
    int t=9-h;
    int w=x.size();

    for(int i=0;i<=9;i++) ans[i]+=t*cnt[w];
    for(int i=h+1;i<=9;i++) ans[i]+=p[w];

    int s=0;
    for(int i=x.size()-1;i>=0;i--) s=s*10+x[i];
    int s1=p[x.size()];
    ans[h]+=s1-s;

    auto ans2=get(x);

    for(int i=0;i<=9;i++) ans[i]+=ans2[i];

    return ans;
}

vector<int> slove(int x)
{
    vector<int> ans(10，0);

    if(x==0) return ans;

    vector<int> t;

    while(x)
    {
        t.push_back(x%10);
        x/=10;
    }

    t[0]++;
    int r=0;
    for(int i=0;i<t.size();i++)
    {
        t[i]+=r;
        r=t[i]/10;
        t[i]%=10;
    }
    if(r) t.push_back(r);

    auto s=get(t);

    for(int i=0;i<=9;i++) ans[i]=cnt[t.size()]-s[i];
    ans[0]-=cnt_0[t.size()];

    return ans;
}

int main()
{
    p[0]=1;
    for(int i=1;i<=9;i++) p[i]=p[i-1]*10;
    for(int i=1;i<=9;i++) cnt[i]=i*p[i-1];
    for(int i=1;i<=9;i++) cnt_0[i]=p[i-1];
    for(int i=1;i<=9;i++) cnt_0[i]+=cnt_0[i-1];

    while(cin>>a>>b，a||b)
    {
        if(a>b) swap(a，b);

        auto fa=slove(a-1);
        auto fb=slove(b);

        for(int i=0;i<=9;i++) printf("%d "，fb[i]-fa[i]);
        puts("");
    }

    return 0;
}