计数问题

题目描述

给定两个整数 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<1000000000<a,b<100000000

由于本人能力有限，只能将大佬的思路稍加详细的说明一下 :cry:，如有没说清楚的地方希望大家指正谢谢~~​ :call_me_hand:

要求 A~B 之间所有数字中 0~9出现的次数，可以分别求取 0~A 中 0~9出现的个数，以及 0~B-1 中 0~9 出现的个数，然后把两者相减即可得到结果。

求 0~n 之间的所有数字中 0~9 出现的 次数

思路分析

以下我们将根据 数字n 的特征来分类讨论，构造并求出在d位上为x的数字的个数。

假设当前n = abcdefg,此时我们枚举到d位，且此时正在求d位上为x的数字的个数。

(x ∈ 0~9 )

1. 若此时存在数字n1 = asdxfgh ，当 asd∈ 000~abc-1时：

此时显然不管x和后面的fgh取什么样的数字都会比n小，所以此时 d位上为x的数字 有 abc × 1000 个。（1000是因为任取fgh，n1都会比n小，所以即可取 000~999 范围的数字，因此有 1000 个）

1. 若此时存在数字n1 = asdxfgh ，当asd = abc时：

2. 当 d<x 时，显然由于n1 > n，因此超出了范围，因此有 0 个；

3. 当 d=x 时，显然fgh只能取值为 000~efg,因此有 efg+1 个;
4. 当 d>x 时，显然此时不论怎样n都会大于n1，所以n1的后缀fgh可任意取值，范围为000~999，有 1000 个。

——————————————————————————

上述分析还未考虑需特判的条件，如本题，由于数字是不含前导0的，诸如00123这样的数字，实际上会被电脑把前面的前导0去掉，如这样00123,即就认为是123。

因此对于0的话我们需要做特殊的处理，假如此时还是考察d位，那么d的前方的abc就不能从000开始取值了，会出现前导0！

假设此时枚举的x是0的话那么对于上述的情况1我们需要进行相应的更改：

1. 若此时存在数字n1 = asdxfgh ，当 asd∈ 001~abc-1 时：

此时显然不管x和后面的fgh取什么样的数字都会比n小，所以此时 d位上为x的数字 有

**` (abc-1) × 1000`** 个。（从001开始的）

1. 情况2和上面的情况2一样。

:+1:==当然还有一些细枝末节的边界问题体现在了yxc大佬的精美代码中。==:+1:

代码及注释

#include<iostream>
#include<vector>

using namespace std;

typedef long long LL;

//把vector里的一段数字组合成一个整数
int get(vector<int> a,int l,int r){
    int res=0;
    for(int i=r;i>=l;i--) res=res*10+a[i];
    return res;
}

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

//直接通过考察m的特征来进行分类讨论统计出其相应位上x的个数,从而避免了一个个的去枚举0~m的数字
LL count(int m,int x){
    if(m==0) return 0;//从main函数传值进来的时候，a-1可能会把0传进来

    vector<int> v;
    //把x的每一位数字拆下来保存到v中
    while(m){
        v.push_back(m%10);
        m/=10;
    }
    int n=v.size();
    LL res=0;
    //考察m的每一位，统计有多少个数字在这些位上是x
    //n-1为是最高位    之所以-!x,是因为不管是哪个数字你统计它的最高位肯定是不可能为0的，
    //因此加入你要统计0出现的个数时，应该从次高位开始
    for(int i=n-1-!x;i>=0;i--){//我们这里采用从高位到低位的考虑方式
        if(i<n-1){//000~abc / 001~abc
            res+=(get(v,i+1,n-1)-!x)*pow10(i);//当前考察的是0的话得减去1
        }
        if(v[i]==x)   res+=get(v,0,i-1)+1;//d=x的情况  000~efg
        else if(v[i]>x) res+=pow10(i);//d<x的情况  0~999
    }
    return res;

}

int main(){
    int a,b;
    while(cin>>a>>b,a||b){
        if(a>b) swap(a,b); //注意保证a<b

        for(int i=0;i<=9;i++){
           printf("%ld ",count(b,i)-count(a-1,i));
        }
        puts("");
    }

    return 0;
}