1140

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	Output for Sample Input
5 10 11 100 200 0 500 1234567890 2345678901 0 4294967295	Case 1: 1 Case 2: 22 Case 3: 92 Case 4: 987654304 Case 5: 3825876150

一道基本的数位dp的题，我在上一题找1的基础上改进了一下，然后在学长的指导下改对了。。。又是想的多了。。和细节问题。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<math.h>
#include<string>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define N 106
#define Lson rood<<1
#define Rson rood<<1|1
LL dp[20][20][20][2],d[20];///加了一个p之后维度上升了
LL dfs(int now,int w,int tot,int fp,int p)
{
    if(now==1) return tot;
    if(!fp&&dp[now][w][tot][p]!=-1) return dp[now][w][tot][p];
    int ma=(fp?d[now-1]:9);
    LL ans=0;
    
    for(int i=0;i<=ma;i++)
    {
        if(!p&&i!=0) p=1;///判断前导零
        ans+=dfs(now-1,i,tot+(i==0&&p==1),fp&&i==ma,p);
    }
    
    if(!fp&&dp[now][w][tot][p]==-1) dp[now][w][tot][p]=ans;
    return ans;
}
LL calc(LL x)
{
    if(x==0) return 1;
    if(x==-1) return 0;///特判0

    LL xxx=x,sum=0;
    int len=0;
    while(xxx)
    {
        d[++len]=xxx%10;
        xxx/=10;
    }
    for(int i=0;i<=d[len];i++)
        sum+=dfs(len,i,0,i==d[len],i!=0);///加了一个判断前导零的标志p
    return sum+1;///计算0（+1）
}
int main()
{
    LL n,m;
    int T,t=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        memset(dp,-1,sizeof(dp));
        printf("Case %d: %lld
",t++,calc(m)-calc(n-1));
    }
    return 0;
}