题意：给出一个区间[a,b]，求里面的数中共出现多少个0。
最初我和小T讨论的结果是逐位计算，先算个位，再算十位……不过TLE了。后来参考扯男的思路，在此基础上又改进了一下。代码中pow[]就是10的次方，g[i]表示所有 i 位数中含有多少个0（不过这个数组被我砍掉了），s[i]就是g[]的前 i 项和。f[i]不好讲解，例：f[2]表示从00、01……到99中有多少个0，f[3]表示从000、001、……到999中有多少个0。
说到思路嘛，拿35017做例子吧。在cal()中，首先计算的是[0,9999]、[10000,29999]两部分，根据已经打好表的数组可直接求。然后再从次高位到最低位循环，如果该位不为0，如5，就加上[31000,34999]（后面位的0）、[30001,30999]（当前位的0）两部分；如果为0，只需加上[35000,35017]（当前位的0）一部分。
1 #include <cstdio> 2 #define N 19 3 typedef long long llg; 4 llg pow[N],f[N],s[N]; 5 int d[N]; 6 void init() 7 { 8 pow[0] = 1; 9 pow[1] = 10; 10 s[0] = 1; 11 f[1] = s[1] = 1; 12 for(int i = 2; i < 13; i++) 13 { 14 pow[i] = 10*pow[i-1]; 15 f[i] = i * pow[i-1]; 16 s[i] = s[i-1]+9*f[i-1]; 17 } 18 } 19 int dvid(llg n) 20 { 21 int f; 22 if(!n) 23 { 24 d[0] = 0; 25 return 1; 26 } 27 for(f = 0; n; n/=10) 28 d[f++] = n%10; 29 return f; 30 } 31 llg cal(llg n) 32 { 33 if(n < 0) return 0; 34 llg ans; 35 int len = dvid(n); 36 ans = s[len-1]+(d[len-1]-1)*f[len-1]; 37 n %= pow[--len]; 38 for(; len; len--) 39 { 40 if(d[len-1]) 41 ans = ans + d[len-1]*f[len-1] + pow[len-1]; 42 else ans += n+1; 43 n %= pow[len-1]; 44 } 45 return ans; 46 } 47 int main() 48 { 49 llg m,n; 50 init(); 51 while(scanf("%I64d%I64d",&m,&n),m>=0) 52 { 53 printf("%I64d\n",cal(n)-cal(m-1)); 54 } 55 return 0; 56 }
做这题时遇到两个问题，一个是dvid(0)时出错，不过很好纠正；另一个是cal一位数时出错，为了纠正它，只好给s[0]赋了一个实际上并不正确的值。