计数问题——题解

Myth丶恋晨 2022-09-12 08:52 147阅读 0赞

记录一下，写代码10分钟，改 Bug 3小时~

给定两个整数 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

PS：counnt 和 counmt 函数用于计算 1~n中第 x 位置出现 nu 数字的个数，利用了前缀和的思想，所求的结果 = counnt(m) - counmt(n-1)

#include<bits/stdc++.h>
    
    using namespace std;
    int a[15],b[15];
    char n[20],m[20];
    int len,lem;
    
    int counnt(int x,int nu){ 
        int num=0,y=0;
        for(int i=0;i<x;i++){ 
            num=num*10+(n[i]-'0');
        }
        if(nu==0) num--;
        num*=pow(10,len-x-1);
        for(int i=x+1;i<len;i++)  y=y*10+(n[i]-'0');
    
    
        if(n[x]==nu+'0') num+=y+1;
        if(n[x]>nu+'0') num+=pow(10,len-x-1);
    
        if(nu==0&&x==0) num=0;
    
        return num;
    }
    
    int counmt(int x,int nu){ 
        int num=0,y=0;
        for(int i=0;i<x;i++){ 
            num=num*10+(m[i]-'0');
        }
        if(nu==0) num--;
        num*=pow(10,lem-x-1);
        for(int i=x+1;i<lem;i++)  y=y*10+(m[i]-'0');
    
        if(m[x]==nu+'0') num+=y+1;
        if(m[x]>nu+'0') num+=pow(10,lem-x-1);
    
        if(nu==0&&x==0) num=0;
    
        return num;
    }
    
    int main(){ 
        int nn,mm;
        while(cin>>nn>>mm){ 
            if(nn==0&&mm==0) break;
            if(nn>mm) swap(nn,mm);
    
            int k=0;          //将最小的数转换成字符串
            nn=nn-1;
            if(nn==0){ 
                n[0]='0';
                k=1;
            }
            while(nn){ 
                n[k]=nn%10+'0';
                k++;
                nn/=10;
            }
            len=k;
            for(int i=0;i<len/2;i++){ 
                swap(n[i],n[len-i-1]);
            }
    
            k=0;          //将最大的数转换成字符串
            if(mm==0){ 
                m[0]='0';
                k=1;
            }
            while(mm){ 
                m[k]=mm%10+'0';
                k++;
                mm/=10;
            }
            lem=k;
            for(int i=0;i<lem/2;i++)
                swap(m[i],m[lem-i-1]);
    
    
            for(int i=0;i<10;i++){ 
                a[i]=0;
                for(int j=0;j<len;j++){ 
                    a[i]+=counnt(j,i);
                }
                //cout<<"a[]="<<a[i]<<endl;
            }
    
            for(int i=0;i<10;i++){ 
                b[i]=0;
                for(int j=0;j<lem;j++){ 
                    b[i]+=counmt(j,i);
                    //cout<<j<<" "<<i<<" b[]="<<counmt(j,i)<<endl;
                }
                //cout<<"b[]="<<b[i]<<endl;
            }
    
            for(int i=0;i<10;i++){ 
                cout<<b[i]-a[i]<<" ";
            }
            cout<<endl;
    
        }
    
    
        return 0;
    }