1的个数 南阳acm514

2018-12-04 07:13:33来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

1的个数

时间限制:1000 ms  |  内存限制:65535 KB
难度:3
 
描述
给你两个数a和b,你的任务是计算出1在a和b之间出现的次数,比如说,如果a=1024,b=1032,那么a和b之间的数就是:
1024 1025 1026 1027 1028 1029 1030 1031 1032
则有10个1出现在这些数中。
 
输入
输入不会超过500行。每一行有两个数a和b,a和b的范围是0 <= a, b <= 100000000。输入两个0时程序结束,两个0不作为输入样例。
输出
对于每一对输入的a和b,输出一个数,代表1出现的个数。
样例输入
1 10
44 497
346 542
0 0
样例输出
2
185
40
来源
heroj
上传者
rihkddd
算法思想:首先,a不一定比b小,要判断一下,如果我们直接暴力从a到b每个值都判断肯定是会超时的,因为a和b的范围是0 <= a, b <= 100000000。什么??不信,那我们来看一下吧。
超时代码:
 1 #include<stdio.h>
 2 int main()
 3 {
 4     int a,b,i,cut;
 5     while(scanf("%d%d",&a,&b)!=EOF,(a||b))
 6     {
 7         if(a > b)
 8         {
 9             int t = a;
10             a = b;
11             b = t;
12         }
13         cut = 0;
14         for(i=a; i<=b; i++)
15         {
16             int ans = i;
17             while(ans > 0)
18             {
19                 if(ans%10 == 1)
20                     cut++;
21                 ans/=10;
22             }
23         }
24         printf("%d\n",cut);
25     }
26     return 0;
27 }

  

我没骗你吧!下面我们来讲这题怎么做吧

算法思想:我们先求1~b 1的个数,在求1~(a-1)1的个数,然后再相减就等于a~b 1的个数了。求1~n 1的个数可以参考一下这个博客:https://blog.csdn.net/yi_afly/article/details/52012593  很详细!不说了,附上代码:

ac代码:

 

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int f(int n)
 5 {
 6     if(n < 1) return 0;
 7     int ans = 0;
 8     int base = 1;
 9     int round = n;
10     while(round > 0)
11     {
12         int weight = round%10;
13         round/=10;
14         ans+=round*base;
15         if(weight == 1)
16             ans+=(n%base)+1;
17         else if(weight > 1)
18             ans+=base;
19         base*=10;
20     }
21     return ans;
22 }
23 int main()
24 {
25     int a,b;
26     while(scanf("%d%d",&a,&b)!=EOF,(a||b))
27     {
28         if(a > b)
29         {
30             int t = a;
31             a = b;
32             b = t;
33         }
34         printf("%d\n",f(b)-f(a-1));
35     }
36     return 0;
37 }

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:【leetcode 简单】 第六十题 反转链表

下一篇:char[] 转换string时的自动截断问题