1140 - How Many Zeroes?

阅读量：7117 次

发布时间：2019-06-28

本文共 1756 字，大约阅读时间需要 5 分钟。

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

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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              using namespace std;#define INF 0x3f3f3f3f#define LL long long#define N 106#define Lson rood<<1#define Rson rood<<1|1LL 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\n",t++,calc(m)-calc(n-1)); } return 0;}

转载于:https://www.cnblogs.com/zct994861943/p/8379939.html

你可能感兴趣的文章