「BZOJ1833」[ZJOI2010] count 数字计数
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。
题解
裸的数位dp
大概只有我这种逗比不会做
递推出f[i][j][k]表示长度为i开头j的所有数字中k的个数
然后乱搞
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct data{ll a[10];}; ll a,b,t[25]; data f[25][10]; data operator+(data a,data b) { data t; for(int k=0;k<=9;k++) t.a[k]=a.a[k]+b.a[k]; return t; } data cal(ll x) { data ans;for(int i=0;i<=9;i++)ans.a[i]=0; if(!x) { ans.a[0]=1; return ans; } int len=15; while(t[len]>x)len--; for(int i=1;i<len;i++) for(int j=1;j<=9;j++) ans=ans+f[i][j]; ans.a[0]++; int cur=x/t[len]; for(int i=1;i<cur;i++) ans=ans+f[len][i]; x%=t[len]; ans.a[cur]+=x+1; for(int i=len-1;i;i--) { cur=x/t[i]; for(int j=0;j<cur;j++) ans=ans+f[i][j]; x%=t[i]; ans.a[cur]+=x+1; } return ans; } int main() { t[1]=1;for(int i=2;i<=15;i++)t[i]=t[i-1]*10; for(int i=0;i<=9;i++)f[1][i].a[i]=1; for(int i=2;i<=12;i++) for(int x=0;x<=9;x++) for(int y=0;y<=9;y++) { f[i][y]=f[i][y]+f[i-1][x]; f[i][y].a[y]+=t[i-1]; } a=read();b=read(); data t1=cal(b),t2=cal(a-1); for(int i=0;i<=9;i++) { printf("%lld",t1.a[i]-t2.a[i]); if(i!=9)printf(" "); } return 0; } |
Subscribe