首页 > 代码库 > count 数字计数(bzoj 1833)
count 数字计数(bzoj 1833)
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。
/* 令f[i]为i位数(算前导零)中每个数出现的次数(一定是相同的,所以只记录一个就行了) 有f[i]=f[i-1]*10+10^(i-1) */ #include<cstdio> #include<iostream> #define lon long long using namespace std; lon ans[20],f[20]; void resolve(lon x,lon pos){ while(x) ans[x%10]+=pos,x/=10; } void DP(lon x,lon flag){ int i,j;lon pos,now; for(i=1,pos=10;pos<x;i++,pos*=10){//“整数”部分 for(j=0;j<=9;j++) ans[j]+=f[i-1]*9*flag; for(j=1;j<=9;j++) ans[j]+=pos/10*flag; } now=pos/=10;i--; while(now<x){//“小数”部分 while(now+pos<=x) { lon temp=now/pos; resolve(temp,pos*flag); for(j=0;j<=9;j++) ans[j]+=f[i]*flag; now+=pos; } pos/=10;i--; } } int main(){ lon a,b,pos;int i; f[1]=1; for(i=2,pos=10;i<=12;i++,pos*=10) f[i]=f[i-1]*10+pos; cin>>a>>b; DP(b+1,1);DP(a,-1);//差分一下 for(int i=0;i<=9;i++) printf("%lld%c",ans[i],i==9?‘\n‘:‘ ‘); return 0; }
count 数字计数(bzoj 1833)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。