| Time Limit: 2000MS | Memory Limit: 32768KB | 64bit IO Format: %lld & %llu |
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
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
Source
题意给定两个数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 <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
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<u);
if(pre&&flag)dp[pos][cnt]=ans;
return ans;
}
ll solve(ll x){
memset(dp,-1,sizeof(dp));
int len=0;
while(x){
num[++len]=x%10;
x/=10;
}
return dfs(len,0,0,0);
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
ll i,j,k,m,n,T,t;
cin>>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 "<<t<<": ";
//if(i==0)cout<<solve(solve(j)+1)<<endl;
cout<<ans<<endl;
}
return 0;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/18970379