题意：给你整数a、b,问你[a,b]间每个数字分解成单个数字后，0、1、2、3、4、5、6、7、8、9，分别有多少个
题解：首先找到[0,b]与[0,a-1]进行区间减法,接着就只是求[0,x]
对于x首先求出他有几位、接着从高位到低位求每个区间
例如x=15602，则依次求出[1,9],[10,99],[100,999],[1000,9999]，这个注意因为没有前导0，所以1-9是一样多的0要少一些
接着再求[10000,10999],[11000,11999],[12000,12999],[13000,13999],[14000,14999],[15000,15099]..........[15500,15599]
注意在这儿需求前导0，最后对于个位数的几个进行遍历就好了
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const ll INF=1LL<<60; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=200010; int Dig[10]= {1,9,90,900,9000,90000,900000,9000000,90000000,900000000}; //1-9 10-99 100-999的总个数 int makeup[10]= {0,1,10,100,1000,10000,100000,1000000,10000000,100000000}; //补全1-9并减去0 int dp1[10];//[0,a-1]中0到9的个数 int dp2[10];//[0,b]中0到9的个数 void Everyno(int k,int *dp)//计算有k位的dp，例如k=2就是 10-99,不补前导0 { int num=Dig[k-1]*k; for(int i=0; i<10; ++i) { if(!i) dp[i]=dp[i]+num-makeup[k-1]*9;//减去一些0不可能出现的地方 else dp[i]=dp[i]+num+makeup[k-1]; } } void Everyyes(int k,int *dp) { int num=makeup[k]*k; for(int i=0;i<10;++i) { dp[i]+=num; } } void Solve(int a,int* dp)//[0,a]中0到9的个数 { for(int i=0; i<10; ++i) dp[i]=0; int enn=9; int dig=1;//位数 while(enn<=a)//计算 1-9 10-99 100-999...除开0以外，每位个数都相同且平分差值 { Everyno(dig,dp); dig++; enn=enn*10+9; } enn=enn/10+1; while(enn<=a)//剩下的数 { dig=0; while(enn+Dig[dig+1]<=a)//例如求1899时 现在为1000，则需要使enn=1099 { dig++; enn+=Dig[dig]; } if(!dig) break; Everyyes(dig,dp); int temp=enn,temp2=dig; while(temp2--) temp/=10; while(temp)//补上前面的数，例如求1899在使用1000-1099时需要补上1与0的100个 { dp[temp%10]+=makeup[dig+1]; temp/=10; } enn++; } if(enn==1) enn--; while(enn<=a)//剩下个位几个 { int temp=enn; if(temp==0) dp[0]++; while(temp) { dp[temp%10]++; temp/=10; } enn++; } return ; } int main() { int a,b; while(~scanf("%d %d",&a,&b)&&(a+b)) { if(a>b) swap(a,b); Solve(a-1,dp1); Solve(b,dp2); for(int i=0; i<10; ++i) printf("%d%c",dp2[i]-dp1[i],i==9?' ':' '); } return 0; }
其实还有更简单的方法：从后到前枚举每一个位置可能出现没一个值的个数，这儿可以通过打表找到一些规律
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<stdlib.h> #include<string> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; const int Inf=0x3f3f3f3f; const double Pi=acos(-1.0); const int Max=10; ll Dp(ll n,int m) { ll num=0,k,l; if(!m)//0出现的次数是特殊的 { k=0,l=1; while(l<n) { num+=((n-k)/(l*10)*l); //printf("%lld %lld %lld ",num,l,n); k=k*10+9; if((n-k)%(l*10)<=(k/10)&&(n-k)%(l*10)>0) num+=((n-k)%(l*10)); l*=10; } } else//1-9出现的次数求法一致 { k=1; l=m; while(n>=l)//从低到高枚举每一位 { num+=(n-l)/(k*10)*k+min(k,(n-l)%(k*10)+1); k*=10; l*=10; } } return num; } int main() { ll n,m; while(~scanf("%lld %lld",&n,&m)&&(n+m)) { if(n>m) swap(n,m); for(int i=0;i<10;i++) { printf("%lld%c",Dp(m,i)-Dp(n-1,i),i==9?' ':' ');//枚举每个数 } } return 0; }