BZOJ_1833_[ZJOI2010]_数字计数_(数位dp)

描述


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。

Source

上一篇:Delphi 中 COM 实现研究手记(一)


下一篇:maven 聚合工程的创建和打包