对于一个正整数,我们认为它的光棍指数是它二进制表示下1的个数。
通常认为光棍指数越高,这个数就越孤单。那么问题来了,对于给定的[a,b]区间中。最孤单的数字是谁呢?
如果光棍指数相同,最孤单的就是最小的那个数。
第一行一个整数 T (1≤T≤10^4),表示问题数。
接下来 T 行,每行两个整数 a,b (0≤a≤b≤2^31−1)。数据之间用一个空格分隔。
对于每个问题,输出一行 Case x: y,其中 x 是问题编号,从 1 开始,y 是答案
2 0 14 100 1000
Case 1: 7 Case 2: 511
package 位运算; /* * 链接:https://www.nowcoder.com/questionTerminal/0e28cf34d05d422ea4a8fee8b4772c4a?orderByHotValue=1&page=1&onlyReference=false 来源:牛客网 对于一个正整数,我们认为它的光棍指数是它二进制表示下1的个数。 通常认为光棍指数越高,这个数就越孤单。那么问题来了,对于给定的[a,b]区间中。最孤单的数字是谁呢? 如果光棍指数相同,最孤单的就是最小的那个数。 解题思路: 看一下数字规模,穷举每个数求其二进制表示中1的个数,显然会超时。 可以这样想,既然要求"1"最多的数,那么我就对一个数从低位开始,将其低位上的0不断换成1,比较换之后的结果是否在区间内就行了。 关键:result |= result + 1; */ import java.util.Scanner; public class 光棍指数 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int i = 1; i <= T; i++) { long a = sc.nextLong(); long b = sc.nextLong(); long result = a; while ((result | (result + 1)) <= b) { result |= result + 1; } System.out.println("Case " + i + ": " + result); } } }
T=int(input()) a=[] def sum(l):#统计 '1' 的 个数 num=0 for i in list(l): if i=='1': num=num+1 return num for i in range(T): # a[i]=list(map(int, input().strip().split(' '))) a.append(list(map(int, input().strip().split(' ')))) for i in range(T): number = []#存储每个数字1的 个数 # a.append(list(map(int, input().strip().split(' ')))) for j in range(a[i][0],a[i][1]+1): tmp="{0:b}".format(j)#转为二进制 # number[k]=sum(tmp)#空list 不能直接用index访问赋值,会out of range,用append 添加 number.append(sum(tmp))#存储每个数字1的 个数 res=number.index(max(number)) #list 中 1最多的下标 # print('Case',i+1,':',a[i][0]+res) print("Case %d: %d" % (i+1, a[i][0]+res))