[HDU5969] 最大的位或
发布时间:2020-12-14 04:20:46 所属栏目:大数据 来源:网络整理
导读:题目类型:位运算 传送门:Here 题意:给出 (l) 和 (r) ,求最大的 (x|y) ,其中 (x,y) 在 ([l,r]) 范围内 解题思路 首先让我想到了前面那题 (Bits) ,然而并不是1越多越好,而是越前面越好(于是就 (WA) 了……) 其实很简单。分类讨论: 如
题目类型:位运算 传送门:>Here<
解题思路首先让我想到了前面那题(Bits),然而并不是1越多越好,而是越前面越好(于是就(WA)了……) 其实很简单。分类讨论: 如果左右边界转为二进制后长度不等,那么左边界一定能够做到全为1,且长度为右边界-1.再或以下就又变长了一格了。于是答案很明显是(2^{len(r)}-1) 如果长度相等,我们发现他们肯定有公共前缀。而从高到低第一个不同的位上,左边界的那一位一定是0,右边界一定是1。因此只需要把这之后的全部变为1就可以了。 反思概念不要混淆,二进制里数字大并不是1越多越好,而是越前越好 依然是分类讨论,分类讨论太重要了! Code/*By DennyQi 2018*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; #define int ll const int MAXN = 10010; const int MAXM = 20010; const int INF = 1061109567; inline int Max(const int a,const int b){ return (a > b) ? a : b; } inline int Min(const int a,const int b){ return (a < b) ? a : b; } inline int read(){ int x = 0; int w = 1; register char c = getchar(); for(; c ^ '-' && (c < '0' || c > '9'); c = getchar()); if(c == '-') w = -1,c = getchar(); for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w; } int T,mx,p,t,l,r; int b1[100],b2[100],len1,len2; inline int solve(int l,int r){ len1 = len2 = 0; memset(b1,sizeof b1); memset(b2,sizeof b2); int x = l,res=0; while(x > 0){ b1[++len1] = x % 2; x /= 2; } x = r; while(x > 0){ b2[++len2] = x % 2; x /= 2; } if(len1 != len2){ return (1ll<<len2)-1; } for(int i = len2; i; --i){ if(b1[i] == b2[i]){ res += b1[i] * (1ll<<(i-1)); } else{ res += (1ll<<i)-1; return res; } } return l; } signed main(){ T = read(); while(T--){ l = read(),r = read(); printf("%lldn",solve(l,r)); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |