題意：給出一個區間[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]賦了一個實際上并不正确的值。