首页 > 代码库 > POJ 3286 How many 0's?
POJ 3286 How many 0's?
题目链接
题意 ：写下m到n之间所有的数，会写多少个0。
思路 ：先算0到m的，再算0到n的，最后相减。
网上有位大神是这么推的，看下面。。。。
首先转化成求 [0, x] 中所有数中，含有的 0 的个数
那么对于一个数 x，怎么求出从 0 到 x 中所有数含有 0 的个数的和呢？
我们可以限制每一位是 0，然后再来计算。举个例子，假设 x 是 21035
首先 0 肯定是一个，sum 赋初值为 1
个位数是 0
个位数前面的数不能是 0，能够取的数就是 [1, 2103]，个位后面没有了
那么 sum+=2103*1
十位数是 0
十位数前面的数不能是 0，能够取的数就是 [1, 210]，由于 0 比 3 小，十位后面可以取 [0, 9]
那么 sum+=210*10
百位数是 0
百位数前面的数不能是 0，能够取的数就是 [1, 21]，由于 0 是等于 0 的，这里就要特殊处理下了：
百位数前面的数如果是在 [1, 20] 中的，百位数后面的数可以取的就是 [0, 99]
百位数前面的数如果取的是 21，百位数后面的数就只能取 [0, 35]
那么，sum+=20*100+36
1 //3286 2 #include <stdio.h> 3 #include <string.h> 4 #include <iostream> 5 6 using namespace std ; 7 8 void ji(long long s,long long &cnt ,long long t) 9 {10 if(s <= 0) return ;11 long long x = s /10,y = s %10,z = s / 10 ;12 for( ; x != 0 ; x /= 10)13 if(x % 10 == 0)14 cnt += (y+1)*t ;15 cnt += z*t ;16 ji(z-1,cnt,t*10) ;17 }18 int main()19 {20 long long m,n ;21 while(~scanf("%I64d %I64d",&m,&n))22 {23 if(m == -1 && n == -1) break ;24 long long summ = 0,sumn = 0 ;25 ji(m-1,summ,1ll) ;26 ji(n,sumn,1ll) ;27 if(m == 0) sumn++ ;28 printf("%I64d\n",sumn-summ) ;29 }30 return 0 ;31 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。