2 条题解
-
0
较难的解法：
/* 本题有许多做法，这里提供一种较通常的做法*/ #include<bits/stdc++.h> //by: hansang.Daisy&Cornflower using namespace std ; typedef long long LL; const int N=30; LL f[N], d[N], ans1[N], ans2[N], a[N]; //f[i]表示i位数中每个数字出现的次数（因为所有数字出现的概率是一样的，所以用一个数组就可以 //（注意f[i]含前导零），d[i]表示10的幂次方，也可表示前导零的个数 //d数组:比如当前第4位，那么含前导零的数就有0 000, 0 001, ..., 0 998, 0 999，共d[4-1]个 void work(LL x, LL ans[]){ LL sum=x; int len=0; while(x>0) a[++len]=x%10, x/=10; for(int i=len; i>=1; i--){ //第i个都是建立在len~i+1的基础上的 for(int j=0; j<=9; j++) ans[j]+=f[i-1]*a[i]; //当前第i位可以填0~a[i]-1，共a[i]个，再乘上f[i-1] //如果当前是第len个，这里填0也是合法的，因为要算[0～(a[len]-1)*10^(i-1)] //注意算的数据都含前导零，第len个没有减掉的前导零会在后面循环减掉 for(int j=0; j<a[i]; j++) ans[j]+=d[i-1]; //比如当前第i位我选x,那后面i-1位都建立在当前x的基础上 //例:x _ _ _ 就要加上1000个(0~999) sum-=d[i-1]*a[i]; //sum消去当前位，比如:345->45 ans[a[i]]+=sum+1; //前面统计了第i位选0~a[i]-1的，现在如果选a[i] //那么就只能加上sum+1，例:345如果选3，则加上46(0~45 //下面这行和上面分开看 ans[0]-=d[i-1]; //去掉前导零，其实是减掉len位算的[0～(a[len]-1)*10^(i-1)]里的0 //每一循环都减掉当前位的零，例如:len为4时一开始[0000,0001,...,0xxx,...,xxxx] //全减完时为[1,...,xxx,...,xxxx] } } //题外话:其实这个代码x=0时统计0的个数也是0个，不过题目范围不包含0~ int main(){ //freopen("a.in", "r", stdin); d[0]=1; for(int i=1; i<=25; i++) d[i]=d[i-1]*10; f[0]=0; for(int i=1; i<=25; i++) f[i]=f[i-1]*10+d[i-1]; //假设1~i-1位已经处理好了，那我们第i位可以填0~9，所以是f[i-1]*10 //我们也可以在第i位填x，后面i-1位怎么填都可以，所以加上d[i-1] //注意:计算重复的数代表里面有不止一个x(都被计算进去了，最后答案并没有错 LL a, b; scanf("%lld%lld", &a, &b); work(b, ans1); work(a-1, ans2); for(int i=0; i<=9; i++) printf("%lld ", ans1[i]-ans2[i]); printf("\n"); return 0; }暴力dp法(简单点：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=30; struct node{ LL a[15], d; node() {memset(a, 0, sizeof(a)); d=0;} } f[N][15]; LL a[N]; node operator+(node n1, node n2){ for(int i=0; i<=9; i++) n1.a[i]+=n2.a[i]; n1.d+=n2.d; return n1; } node operator-(node n1, node n2){ for(int i=0; i<=9; i++) n1.a[i]-=n2.a[i]; n1.d-=n2.d; return n1; } node operator*(node n1, LL x){ for(int i=0; i<=9; i++) n1.a[i]*=x; n1.d*=x; return n1; } node calc(LL x){ int len=0; node ans, sum; sum.d=1; if(x<10) return f[1][x]; while(x>0) a[++len]=x%10, x/=10; for(int i=len; i>=1; i--){ for(int j=(i==len)? 1: 0; j<=a[i]-1; j++){ ans=ans+f[i][j]; ans=ans+sum*f[i][j].d; ans.d+=f[i][j].d; } sum.a[a[i]]++; if(i==1) ans=ans+sum; } for(int i=len-1; i>=1; i--) for(int j=1; j<=9; j++) ans=ans+f[i][j]; ans.a[0]++; ans.d++; return ans; } int main(){ //freopen("a.in", "r", stdin); for(int i=0; i<=9; i++) f[1][i].a[i]=i==0?0:1, f[1][i].d=1; for(int t=2; t<=25; t++) for(int j=0; j<=9; j++) for(int i=0; i<=9; i++){ f[t][j]=f[t][j]+f[t-1][j]; f[t][j].a[i]+=f[t-1][j].d; } LL a, b; scanf("%lld%lld", &a, &b); node n1=calc(b), n2=calc(a-1), no=n1-n2; for(int i=0; i<=9; i++) printf("%lld ", no.a[i]); printf("\n"); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:04:37
较难的解法：
/* 本题有许多做法，这里提供一种较通常的做法*/ #include<bits/stdc++.h> //by: hansang.Daisy&Cornflower using namespace std ; typedef long long LL; const int N=30; LL f[N], d[N], ans1[N], ans2[N], a[N]; //f[i]表示i位数中每个数字出现的次数（因为所有数字出现的概率是一样的，所以用一个数组就可以 //（注意f[i]含前导零），d[i]表示10的幂次方，也可表示前导零的个数 //d数组：比如当前第4位，那么含前导零的数就有0 000, 0 001, ..., 0 998, 0 999，共d[4-1]个 void work(LL x, LL ans[]){ LL sum=x; int len=0; while(x>0) a[++len]=x%10, x/=10; for(int i=len; i>=1; i--){ //第i个都是建立在len~i+1的基础上的 for(int j=0; j<=9; j++) ans[j]+=f[i-1]*a[i]; //当前第i位可以填0~a[i]-1，共a[i]个，再乘上f[i-1] //如果当前是第len个，这里填0也是合法的，因为要算[0～(a[len]-1)*10^(i-1)] //注意算的数都含前导零，第len个没有减掉的前导零会在后面循环减掉 for(int j=0; j<a[i]; j++) ans[j]+=d[i-1]; //比如当前第i位我选x，那后面i-1位都建立在当前x的基础上 //例：x _ _ _ 就要加上1000个（0～999 sum-=d[i-1]*a[i]; //sum消去当前位，比如：345->45 ans[a[i]]+=sum+1; //前面统计了第i位选0~a[i]-1的，现在如果选a[i] //那么就只能加上sum+1，例：345如果选3，则加上46（0~45 //下面这行和上面分开看 ans[0]-=d[i-1]; //去掉前导零，其实是减掉len位算的[0～(a[len]-1)*10^(i-1)]里的0 //每一循环都减掉当前位的零，例如：len为4时一开始[0000,0001,...,0xxx,...,xxxx] //全减完时为[1,...,xxx,...,xxxx] } } //题外话：其实这个代码x=0时统计0的个数也是0个，不过题目范围不包含0～ int main(){ //freopen("a.in", "r", stdin); d[0]=1; for(int i=1; i<=25; i++) d[i]=d[i-1]*10; f[0]=0; for(int i=1; i<=25; i++) f[i]=f[i-1]*10+d[i-1]; //假设1～i-1位已经处理好了，那我们第i位可以填0～9，所以是f[i-1]*10 //我们也可以在第i位填x，后面i-1位怎么填都可以，所以加上d[i-1] //注意：计算重复的数代表里面有不止一个x（都被计算进去了，最后答案并没有错 LL a, b; scanf("%lld%lld", &a, &b); work(b, ans1); work(a-1, ans2); for(int i=0; i<=9; i++) printf("%lld ", ans1[i]-ans2[i]); printf("\n"); return 0; }
暴力dp法（简单点：#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=30; struct node{ LL a[15], d; node() {memset(a, 0, sizeof(a)); d=0;} } f[N][15]; LL a[N]; node operator+(node n1, node n2){ for(int i=0; i<=9; i++) n1.a[i]+=n2.a[i]; n1.d+=n2.d; return n1; } node operator-(node n1, node n2){ for(int i=0; i<=9; i++) n1.a[i]-=n2.a[i]; n1.d-=n2.d; return n1; } node operator*(node n1, LL x){ for(int i=0; i<=9; i++) n1.a[i]*=x; n1.d*=x; return n1; } node calc(LL x){ int len=0; node ans, sum; sum.d=1; if(x<10) return f[1][x]; while(x>0) a[++len]=x%10, x/=10; for(int i=len; i>=1; i--){ for(int j=(i==len)? 1: 0; j<=a[i]-1; j++){ ans=ans+f[i][j]; ans=ans+sum*f[i][j].d; ans.d+=f[i][j].d; } sum.a[a[i]]++; if(i==1) ans=ans+sum; } for(int i=len-1; i>=1; i--) for(int j=1; j<=9; j++) ans=ans+f[i][j]; ans.a[0]++; ans.d++; return ans; } int main(){ //freopen("a.in", "r", stdin); for(int i=0; i<=9; i++) f[1][i].a[i]=1, f[1][i].d=1; for(int t=2; t<=25; t++) for(int j=0; j<=9; j++) for(int i=0; i<=9; i++){ f[t][j]=f[t][j]+f[t-1][j]; f[t][j].a[i]+=f[t-1][j].d; } LL a, b; scanf("%lld%lld", &a, &b); node n1=calc(b), n2=calc(a-1), no=n1-n2; for(int i=0; i<=9; i++) printf("%lld ", no.a[i]); printf("\n"); return 0; }
- 1
