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

510 11100 2000 5001234567890 23456789010 4294967295

?

Sample Output

Case 1: 1Case 2: 22Case 3: 92Case 4: 987654304Case 5: 3825876150

?

給出區(qū)間[m,n]，求區(qū)間內(nèi)的所有數(shù)共有多少個0。

?

設(shè)dp[i][j]表示處理到第i位時，它前面共有j個0（除了前導(dǎo)零）。

1 // 110,101,100,011,010,001,000 2 #pragma comment(linker, "/STACK:1024000000,1024000000") 3 #include<iostream> 4 #include<cstdio> 5 #include<cstring> 6 #include<cmath> 7 #include<math.h> 8 #include<algorithm> 9 #include<queue> 10 #include<set> 11 #include<bitset> 12 #include<map> 13 #include<vector> 14 #include<stdlib.h> 15 using namespace std; 16 #define ll long long 17 #define eps 1e-10 18 #define MOD 1000000007 19 #define N 1000000 20 #define inf 1e12 21 ll a,b; 22 ll dp[26][26]; 23 int dig[26]; 24 ll dfs(int len,/*轉(zhuǎn)化為二進制數(shù)的位數(shù)*/ int first,/*1表示目前前導(dǎo)都為0*/ int sta,/*sta表示前面有幾個0*/ int up/*up來判斷每一位的取值，1的時候只能取原定值，0的時候取0~9的任意值*/){ 25 if(len==0){//當(dāng)算到最后一位的時候 26 if(first){ 27 return (ll)1; 28 }else{ 29 return (ll)sta; 30 } 31 } 32 if(!up && dp[len][sta]!=-1 && !first){//記憶化，之前算過的直接返回值，不再繼續(xù)算 33 return dp[len][sta]; 34 } 35 36 int n=up?dig[len]:9;//如果up的值為1，只能取dig[len]，比如值為123，up值為1即第一位為1了，那么n的值最大為2，而不能為9 37 ll res=0; 38 for(int i=0;i<=n;i++){ 39 if(first){//如果前導(dǎo)都為0時，sta=0，up值的確定取決于是否是n 40 res+=dfs(len-1,first&&i==0,0,up&&i==n); 41 }else{ 42 if(i==0){// 這里判斷的是如果i=0，前面的0的個數(shù)+1 43 res+=dfs(len-1,0,sta+1,up&&i==n); 44 }else{ 45 res+=dfs(len-1,0,sta,up&&i==n); 46 } 47 48 } 49 } 50 if(!up && !first){ 51 dp[len][sta]=res; 52 } 53 return res; 54 } 55 ll cal(ll num){ 56 int len=0; 57 if(num == 0){//如果值為0,則只有一位數(shù)0 58 dig[++len] = 0; 59 } 60 while(num){ 61 dig[++len] = num % 10; 62 num/=10; 63 } 64 return dfs(len,1,0,1); 65 } 66 int main() 67 { 68 int t; 69 int ac=0; 70 scanf("%d",&t); 71 while(t--){ 72 scanf("%lld%lld",&a,&b); 73 memset(dp,-1,sizeof(dp)); 74 printf("Case %d: ",++ac); 75 printf("%lld\n",cal(b)-cal(a-1)); 76 77 } 78 return 0; 79 } View Code

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/UniqueColor/p/5156444.html

總結(jié)

以上是生活随笔為你收集整理的LightOJ - 1140 How Many Zeroes?的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。