Lightoj1140——How Many Zeroes?（数位dp）-白红宇

Lightoj1140——How Many Zeroes?（数位dp）

阅读量：2343 次

发布时间：2019-05-10

本文共 1660 字，大约阅读时间需要 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

10 11

100 200

0 500

1234567890 2345678901

0 4294967295

Output for Sample Input

Case 1: 1

Case 2: 22

Case 3: 92

Case 4: 987654304

Case 5: 3825876150

求m到n的数共有多少个0

要注意会出现01,001,0001这些前导0的情况，用first判断首位是否是0

lightoj的64位输入输出差点把我又坑一次

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define INF 0x3f3f3f3f#define MAXN 10000005#define Mod 10001using namespace std;int dight[30];long long dp[20][20];long long dfs(int pos,int s,bool limit,int first){ if(pos==0) { if(first) return 1; return s; } if(!limit&&dp[pos][s]!=-1&&!first) return dp[pos][s]; int end; long long ret=0; if(limit) end=dight[pos]; else end=9; for(int d=0; d<=end; ++d) { if(first) ret+=dfs(pos-1,0,limit&&d==end,first&&d==0); else { if(d==0) ret+=dfs(pos-1,s+1,limit&&d==end,0); else ret+=dfs(pos-1,s,limit&&d==end,0); } } if(!limit&&!first) dp[pos][s]=ret; return ret;}long long solve(long long a){ memset(dight,0,sizeof(dight)); int cnt=1; while(a!=0) { dight[cnt++]=a%10; a/=10; } return dfs(cnt-1,0,1,1);}int main(){ memset(dp,-1,sizeof(dp)); int t,cnt=1; scanf("%d",&t); while(t--) { long long x,y; scanf("%lld%lld",&x,&y); printf("Case %d: %lld\n",cnt++,solve(y)-solve(x-1)); } return 0;}