Jimmy writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down?
Input
Input starts with an integer T (≤ 11000), denoting the number of test cases.
Each case contains two unsigned 32-bit integers m and n, (m ≤ n).
Output
For each case, print the case number and the number of zeroes written down by Jimmy.
Sample Input
5
10 11
100 200
0 500
1234567890 2345678901
0 4294967295
Sample Output
Case 1: 1
Case 2: 22
Case 3: 92
Case 4: 987654304
Case 5: 3825876150
问 l 到 r 出现了几个0
记一下出现了几个0，有没有前导零就好
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<deque> 9 #include<set> 10 #include<map> 11 #include<ctime> 12 #define LL long long 13 #define inf 0x7ffffff 14 #define pa pair<int,int> 15 #define mkp(a,b) make_pair(a,b) 16 #define pi 3.1415926535897932384626433832795028841971 17 using namespace std; 18 inline LL read() 19 { 20 LL x=0,f=1;char ch=getchar(); 21 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 22 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 23 return x*f; 24 } 25 LL n,len,l,r; 26 LL f[20][20][20][2]; 27 int d[110]; 28 int zhan[20],top; 29 inline LL dfs(int now,int dat,int tot,int lead,int fp) 30 { 31 if (now==1)return tot; 32 if (!fp&&f[now][dat][tot][lead]!=-1)return f[now][dat][tot][lead]; 33 LL ans=0,mx=fp?d[now-1]:9; 34 for (int i=0;i<=mx;i++) 35 { 36 int nexlead=lead&&i==0&&now-1!=1; 37 ans+=dfs(now-1,i,tot+(i==0&&!nexlead),nexlead,fp&&i==d[now-1]); 38 } 39 if (!fp)f[now][dat][tot][lead]=ans; 40 return ans; 41 } 42 inline LL calc(LL x) 43 { 44 if (x<=0)return x+1; 45 LL xxx=x; 46 len=0; 47 while (xxx) 48 { 49 d[++len]=xxx%10; 50 xxx/=10; 51 } 52 LL sum=0; 53 for (int i=0;i<=d[len];i++) 54 { 55 if (i)sum+=dfs(len,i,0,0,i==d[len]); 56 else sum+=dfs(len,0,len==1,1,!d[len]); 57 } 58 return sum; 59 } 60 main() 61 { 62 int T=read(),cnt=0; 63 while (T--) 64 { 65 l=read();r=read(); 66 if (r<l)swap(l,r); 67 memset(f,-1,sizeof(f)); 68 printf("Case %d: %lld ",++cnt,calc(r)-calc(l-1)); 69 } 70 }