AcWing 338. 计数问题
原题链接
中等
作者:
杨某
,
2022-02-17 21:35:04
,
所有人可见
,
阅读 131
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int js(int x){//获取x的位数
int res=0;
while(x){
res++;
x/=10;
}
return res;
}
int cnt(int n,int i){
int res=0,d=js(n);//总个数(结果)与n的位数
for(int j=1;j<=d;j++){//枚举i在每一位上面的个数
//p为i在j位时,j左边一共有多少种可能
//比如j在第四位即1000,那么p就是1000,代表000~999
//l是j左边的数,r是j右边的数
//dj是第j位数
int p=pow(10,j-1),l=n/p/10,r=n%p,dj=n/p%10;
//i不为0,加上所有个数
//例abc d efg 当d不为1时,个数有abc*1000(000~abc-1,0~999)
if(i) res+=l*p;
//当i为0,第j位前面的数(即l)不为0,删去一个000的方案
if(!i&&l) res+=(l-1)*p;
//计算第j位数前面相同时,即l=abc时;
//第j位数大于i时,后面可以任意,所以有p种
if((dj>i)&&(i||l)) res+=p;
//第j位数等于i时,后面不能大于r,所以有r+1种(0~r)
if((dj==i)&&(i||l)) res+=r+1;
//第j位数小于i时,不用计算
}
return res;
}
int main(){
int a,b;
while(cin>>a>>b,a){
if(a>b) swap(a,b);
for(int i=0;i<10;i++) cout<<cnt(b,i)-cnt(a-1,i)<<" ";
//枚举每一个数字出现的次数
//次数用前缀和实现
cout<<endl;
}
return 0;
}