hdu 5969 最大的位或 2016ACM/CCPC合肥赛区现场赛I

news/2024/5/18 23:03:31 标签: 贪心, 枚举

Problem Description
B君和G君聊天的时候想到了如下的问题。
给定自然数l和r ,选取2个整数x,y满足l <= x <= y <= r ,使得x|y最大。
其中|表示按位或,即C、 C++、 Java中的|运算。
 

Input
包含至多10001组测试数据。
第一行有一个正整数,表示数据的组数。
接下来每一行表示一组数据,包含两个整数l,r。
保证 0 <= l <= r <=  1018
 

Output
对于每组数据输出一行,表示最大的位或。
 

Sample Input
  
5 1 10 0 1 1023 1024 233 322 1000000000000000000 1000000000000000000
 

Sample Output
  
15 1 2047 511 1000000000000000000

首先,这两个数中肯定有一个是R

因为只是或的操作,所以我们可以按照L的位来枚举某一位后面都是1的情况,

’再比较它和R的大小,和R进行或运算后更新答案即可

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long bits[80];
long long a1[101],a2[101];
int main(){
	int T;
	int i,j;
	bits[1] = 1;
	for(i=2;i<=63;i++){
		bits[i] = bits[i-1]<<1;
	}
	scanf("%d",&T);
	while(T>0){
		T--;
		long long l,r;
		scanf("%lld%lld",&l,&r);
		long long t = r;
		int p1=0;
		while(t!=0)
		{
			p1++;
			a1[p1]=t%2;
			t/=2;
		}
		memset(a2,0,sizeof(a2));
		t = l;
		int p2=0;
		while(t!=0)
		{
			p2++;
			a2[p2]=t%2;
			t/=2;
		}
		long long ans=0;
		long long d=0;
	//	printf("%d %d\n",p1,p2);
		for(i=p1;i>=1;i--)
		{
			long long t=d;
			for(j=i;j>=1;j--)
				t+=bits[j];
			if(t<=r)
				ans=max(ans,t|r);
			d+=a2[i]*bits[i];
		}
		ans=max(ans,d|r);
		printf("%lld\n",ans);
	}
	return 0;
}



http://www.niftyadmin.cn/n/942550.html

相关文章

[bzoj2743][HEOI2012]采花

Description 给出一个长度为n的序列&#xff0c;序列中的数再[1~c]的范围内&#xff0c;和m次询问&#xff0c;每次询问[l,r]这个区间中有多少个出现大于等于两次的数。 n,m,c<10^6 Solution 看到这种题&#xff0c;有没有强制在线&#xff0c;自然很容易想到莫队~(≧▽…

暑假测试 Day 5

问题 A: 单词检索 时间限制: 1 Sec 内存限制: 128 MB 提交: 634 解决: 96 [提交][状态][讨论版]题目描述 小可可是学校图书馆的管理员&#xff0c;现在他接手了一个十分棘手的任务。 由于学校需要一些材料&#xff0c;校长需要在文章中检索一些信息。校长一共给了小可可N篇文…

[bzoj1008][HNOI2008]越狱

Description 求n个数排成一行&#xff0c;每个数都在1~m范围内且相邻两个数至少有一组相同的方案数。 n<10^12,m<10^8 Solution 发现直接计算很麻烦。 正难则反&#xff0c;我们考虑用总数-不合法的方案数。 总数很显然是mn那么不合法的方案数就是 第一个位置可以…

BZOJ 1606 [Usaco2008 Dec]Hay For Sale 购买干草 DP---背包

Description 约翰遭受了重大的损失&#xff1a;蟑螂吃掉了他所有的干草&#xff0c;留下一群饥饿的牛&#xff0e;他乘着容量为C(1≤C≤50000)个单位的马车&#xff0c;去顿因家买一些干草&#xff0e; 顿因有H(1≤H≤5000)包干草&#xff0c;每一包都有它的体积Vi(l≤Vi≤C).…

[bzoj1015][JSOI2008]星球大战starwar

Description 给出n个点和m条无向边&#xff0c;再给出q次操作&#xff0c;每次操作把一个点和与他相连的边全部删除&#xff0c;求每次操作之后的联通块个数。 n,q<4 * 10^5, m<2 * 10^5 Solution 正着做似乎很麻烦&#xff1f;我们可以考虑正难则反&#xff08;又来…

bzoj 2648: SJY摆棋子

Description 这天&#xff0c;SJY显得无聊。在家自己玩。在一个棋盘上&#xff0c;有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子&#xff0c;要么放上一个白色棋子&#xff0c;如果是白色棋子&#xff0c;他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离…

2016.6.11初中部模拟赛总结

由于昨天在家里腐了一晚上&#xff0c;起来还是昏昏沉沉的&#xff0c;假期综合症又犯了。。。高考假没了啊&#xff01;&#xff01;&#xff01; 9&#xff1a;00 8:10分才出发&#xff0c;在路上、宿舍有耽误了一些时间&#xff0c;就9:00才到机房。 来不及了&#xff0c…

BZOJ 1059 [ZJOI2007]矩阵游戏 二分图匹配

Description 小Q是一个非常聪明的孩子&#xff0c;除了国际象棋&#xff0c;他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行&#xff08;如同国际象棋一般&#xff0c;只是颜色是随意的&#xff09;。每次可以对该矩阵进行两种操作&#xff1a;行交…