题目描述

给定两个整数 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
输出样例：
1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247

题目分析

• 假设求1~n所有数中1出现的次数，设n=abcdefg

求出1在任意一位上出现的次数，累加起来就是1出现的所有次数。
假设求1在第4位出现的次数：
即求在n中d对应的位1出现的次数，即求在1~n中有多少个形如 xxx1yyy的数。 1 <= xxx1yyy <= abcdefg
这时就要分情况讨论了：
1. xxx=000~abc-1，此时xxx1yyy已经明显[HTML_REMOVED]abcdefg， 不存在
（2.2） 若d=1，那么 abc1000~abc1efg都满足情况，yyy能取000~efg，共 efg+1种可能
（2.3） 若d>1，那么 abc1yyy一定 <abcdefg， 即yyy能取000~999，共 1000种可能

• 边界问题：

1. 当求1在最高位出现的次数时，上述第一种情况有些不同。此时要求在1~n中有多少个形如 1xxxxxx的数。

讨论：①若a<1，那么1xxxxxx一定> abcdefg， 不存在
②若a=1，1000000~1bcdefg都满足情况，xxxxxx能取000000~bcdefg，共 bcdefg+1种可能
③若a>1，那么1xxxxxx一定 < abcdefg， 即xxxxxx能取000000~999999，共1000000种可能
即没有了上述的第一种情况。

2. 当求0在某一位出现的次数时：

上述的第一种情况出现了问题，求0在第4位出现的次数，在xxx0yyy中，当xxx=000，0000yyy不是一种合法的表示。所以应该xxx的范围应该是001~abc-1。即共 （abc-1）1000种可能 (（abc-1）10i) 比其他情况少了10i个。
同时，0不可能出现在最高位上，即不可能求0在最高位出现的次数，所以枚举n时，从n的第二位开始。

（n的最高位对应的下标最大）
同理，可求其他数出现的次数。

• 在求解过程中需要做的准备工作：

位 6 5 4 3 2 1 0
n a b c d e f g
1. 在求各种情况对应的次数时，假设 d 是第 i 位，那么首先需要得到i之前的数 abc 的大小，下面代码中 get 函数就是来求 abc 的。
2. 还需要得到 10i ，下面代码中 power10 函数就是来求 10i 的。
3. 另外还要求 x 在 n 中出现的次数，下面代码中 count 函数就是来求 x 在 n 中出现的次数的。count（b,x）- count（a-1,x）表示 x 在a~b中出现的次数。

C++ 代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int get(vector<int>num,int l,int r) //求num的l到r位表示的十进制数
{
    int res=0;
    for(int i=l;i>=r;i--)
        res=res*10+num[i];
    return res;    
}

int power10(int x)  //求10^x的值
{
    int res=1;
    while(x--)   res*=10;
    return res;
}

int count(int n,int x) //x在n里出现的次数
{
    if(!n) return 0;
    vector<int>num; //num来存n
    while(n)
    {
        num.push_back(n%10); //把n的每一位存进容器里
        n/=10;
    }
    n=num.size();   //求出容器里数的位数，并赋给n
    int res=0;
    for(int i=n-1-!x;i>=0;i--) //从高位到低位遍历n. x=0的时候，不可能出现在最高位，所以从第二位开始遍历
    {
        if(i<n-1)   //当x在最高位（i=n-1）出现时,分析得没有讨论的第一种情况
        {
            res+=get(num,n-1,i+1)*power10(i); //1.第一种情况：数量等于i之前的数也就是abc乘上，以i之后的位数为10的指数
            if(!x) res-=power10(i);//x=0的时候，abc从001开始，数量比其他情况少power10(i)个
        }
        if(num[i]==x) res+=get(num,i-1,0)+1;//2.2 第二种情况里的第二种情况：数量等于i之后的数也就是efg加1
        else if(num[i]>x) res+=power10(i);   //2.3 第二种情况里的第三种情况：数量等于以i之后的位数为10的指数
    }
    return res;
}

int main()
{
    int a,b;
    while(cin>>a>>b,a||b)
    {
        if(a>b) swap(a,b); //有输入a>b的情况，交换a，b
        for(int i=0;i<10;i++)  //循环1~9
            cout<<count(b,i)-count(a-1,i)<<' '; //count(b,i)表示b里i出现的次数，减法表示从a到bi出现的次数
        cout<<endl;
    }
    return 0;
}