light oj 1140 数位dp - c++编程基础

LightOJ - 1140 How Many Zeroes

Time Limit: 2000MS

Memory Limit: 32768KB

64bit IO Format: %lld & %llu

[Submit] [Go Back] [Status]

Description

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

Sample Output

Case 1: 1

Case 2: 22

Case 3: 92

Case 4: 987654304

Case 5: 3825876150

Source

Special Thanks: Jane Alam Jan (Description, Solution, Dataset)

[Submit] [Go Back] [Status]

题意给定两个数a，b，求a到b所有数的0的个数。

数位dp，加一个标志前导零的标志。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-7 19:02:36
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
                using namespace std; #define INF 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; ll dp[20][21],num[30]; ll dfs(ll pos,ll cnt,ll pre,bool flag){ if(pos==0)return cnt; if(flag&&pre&&dp[pos][cnt]!=-1)return dp[pos][cnt]; ll ans=0,u=flag 9:num[pos]; for(ll d=0;d<=u;d++) ans+=dfs(pos-1,cnt+(pre&&d==0),pre||d,flag||d
                
                 >T; for(t=1;t<=T;t++){ cin>>i>>j; ll ans=0; if(i==0)i++,ans++; ans+=solve(j)-solve(i-1); cout<<"Case "<