1的个数 南阳acm514
程序员文章站
2022-05-29 13:33:53
1的个数 时间限制:1000 ms | 内存限制:65535 KB 难度:3 1的个数 时间限制:1000 ms | 内存限制:65535 KB 难度:3 给你两个数a和b,你的任务是计算出1在a和b之间出现的次数,比如说,如果a=1024,b=1032,那么a和b之间的数就是: 1024 1025 ......
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 }
推荐阅读
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
用C语言写一个函数返回参数二进制中1的个数
-
我们在删除SQL Sever某个数据库表中数据的时候,希望ID重新从1开始,而不是紧跟着最后一个ID开始需要的命令
-
c语言:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?打印出来?
-
C语言:有一个分数序列,2/1+3/2+5/3+8/5+13/8+…求出这个数列前 20 项的和
-
python计算1~2008中0和1的个数
-
有一个分数序列 2/1+3/2+5/3+8/5+13/8+… 求出这个数列前 20 项的和。
-
python3 题目 有四个数字:1、2、3、4,能组成多少个互不相同且无重复数字的三位数?各是多少?
-
php实现统计二进制中1的个数算法示例
-
[c语言]统计一个数二进制中的1的个数