数学。
比较不擅长的题目类型，虽然一直以来都挺喜欢数学的 ；）
问的是输入unsigned int m和n，问[m, n]的所有数字打印出来后，总共包含多少个0。
题意非常明确的，其实就是要推出函数calc(d)，能返回0到d所有0的个数，那么calc(n)-calc(m-1)就是结果。
对于某个具体的d，这里基本的思路是将其包含的数按范围划分，例如d=109250时，首先拆成[0, 100000]，[100001, 109000]，[109001, 109200]和[109201, 109250]。那么就可以分情况讨论各个范围内数字所含0的总数，最后累加起来即可。
这里采用的方式是从高位开始拆数。例如，将[0, 109250]包括的0拆成三部分：（1）[0, 100000]，（2）[0, 9250]，（3）以”10″为前缀导致[0, 9250]额外引入的0。那么就可以对[0, 9250]迭代地计算其中包含的0了。也即，此时算法复杂度是和d的位数线性相关的，基本上是O(1)。下面分别讨论三部分含0数目的计算方法。
（1）这里可以预处理，例如a[i]=10^i时，分别计算[1, a[i]]以及[a[i]+1, a[i]*2]范围内所含0的总数，设为b[i]和c[i]。例如a[2]=10^2=100时，b[i]为[1, 100]内0的总数，c[i]为[101, 200]内0的总数。这样处理的原因是，（1）中每次都是拆最高位的，这样当最高位为k时，即为b[i]+(k-1)*c[i]。这里b[i]和c[i]有递推关系，当然其实暴力打表也可以的。
（2）这部分是迭代的，和原本的d处理方法相同；
（3）这部分比较麻烦。首先要记录前缀中含0的个数，然后由d去除最高位后剩余的dd计算需要增加多少个0。这里分情况讨论一下即可。如果前缀有j个0，那么最前面的0包括dd*j个，然后再额外处理后面每一位的情况。
看了别人的基本思路，自己推起来也还是磕磕绊绊。表达起来就更是觉得繁琐了……
|
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 |
#include<cstdio> #define ll long long ll a[11],b[11],c[11]; ll m,n; void init() { ll i,j,k,l; a[0]=1; for(i=1,k=l=0;i<11;i++,l=l*10+9,k+=l) { a[i]=a[i-1]*10; b[i]=b[i-1]+c[i-1]*9+1; c[i]=b[i]+k; } } ll calc(ll d) { if(!d) return 0; ll i,j,k,dd,sum=0; for(i=0;i<11&&a[i]<=d;i++); i--; dd=d-a[i]; sum=b[i]; while(dd>=a[i]) { dd-=a[i]; sum+=c[i]; } if(dd) { for(i--,j=0;i>0&&a[i]>dd;i--,j++); sum+=dd*j; while(i) { sum+=a[i]-1; i--; } } return sum+calc(dd); } void solve() { if(m==0) printf("%lld\n",calc(n)+1); else printf("%lld\n",calc(n)-calc(m-1)); } int main() { init(); while(~scanf("%lld%lld",&m,&n)&&m!=-1) solve(); return 0; } |