CF484A Bits

题目

CF484A Bits

给定一个区间，求出这个区间当中二进制表示下 (1) 最多的数。

分析

牛逼贪心。

考虑如何得出这个数，直接构造？

因为还要要求最小，似乎并不好直接构造，于是我们可以考虑直接给 (l) 的每一位或上 (1) ，看能不能行，可以就或上 (1) ，不可以就不变。

这样做一定是正确的吗？

首先，我们保证了这个数一定是大于等于 (l) 的，然后，我们也保证了这个数一定是小于等于 (r) 的。

那么这个数的最优性呢？我们发现，在满足题意的情况下，一定是多选择低位的 (1) 会使得答案更优，而这里正式从小到大试的。

代码

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x){
	x=0;bool f=false;char ch=getchar();
	while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
	x=f?-x:x;
	return ;
}
template<typename T>
inline void write(T x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
	return ;
}
const int N=1e5+5;
#define PII pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define ll long long
int n;
signed main(){
	read(n);
	while(n--){
		ll l,r,cnt=1;
		read(l),read(r);
		for(register int i=1;(l|cnt)<=r;i++) l|=cnt,cnt<<=1;
		write(l),putchar('
');
	}
}