描述
http://www.lydsy.com/JudgeOnline/problem.php?id=1833
统计\(a~b\)中数字\(0,1,2,...,9\)分别出现了多少次.
分析
数位dp真是细节又多又容易出错,我都懒得看题解,所以也就懒得写题解了...
注意细节吧还是...
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
ll a,b;
ll A[],B[],num[];
ll f[][][]; void solve(ll x,ll *a){
if(x==) return;
if(x<){
for(int i=;i<=x;i++) a[i]=;
return;
}
int cnt=;
ll t=;
while(x) num[++cnt]=x%, x/=;
for(int i=;i<cnt;i++)for(int j=;j<=;j++)for(int k=;k<=;k++) a[k]+=f[i][j][k];
for(int i=;i<cnt;i++){
for(int j=;j<num[i];j++)for(int k=;k<=;k++) a[k]+=f[i][j][k];
a[num[i]]+=t+; t=t+num[i]*(ll)pow(,i-);
}
for(int j=;j<num[cnt];j++)for(int k=;k<=;k++) a[k]+=f[cnt][j][k];
a[num[cnt]]+=t+;
}
int main(){
scanf("%lld%lld",&a,&b);
for(int i=;i<=;i++) f[][i][i]=;
for(int i=;i<=;i++){
for(int j=;j<=;j++)for(int k=;k<=;k++) f[i][][k]+=f[i-][j][k];
for(int j=;j<=;j++)for(int k=;k<=;k++) f[i][j][k]=f[i][][k];
for(int j=;j<=;j++) f[i][j][j]+=(ll)pow(,i-);
}
solve(b,B); solve(a-,A);
for(int k=;k<;k++) printf("%lld ",B[k]-A[k]);
printf("%lld\n",B[]-A[]);
return ;
}
1833: [ZJOI2010]count 数字计数
Time Limit: 3 Sec Memory Limit: 64 MB
Submit: 2569 Solved: 1132
[Submit][Status][Discuss]
Description
给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次。
Input
输入文件中仅包含一行两个整数a、b,含义如上所述。
Output
输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次。
Sample Input
1 99
Sample Output
9 20 20 20 20 20 20 20 20 20
HINT
30%的数据中,a<=b<=10^6;
100%的数据中,a<=b<=10^12。