You have two integers L and R, and you are required to find the max xor value of a and b where L <= a <= R and L <= b <= R
Input
Two integers in a line. L, R <= 1e9
Output
One integer, the answer
Example
Input: 1 10 Output: 15
题意：
给定L，R，X1^X2^X3...最大异或,(L<=X1,X2,X3...<=R)。
没什么思路，上次CF就遇到这道题，我是用贪心写的，忽略pow的精度问题，可以AC。
http://codeforces.com/contest/912/problem/B
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<vector> #include<iostream> #include<map> using namespace std; long long a,b,n,k,ans,c,d; map<long long,int>mp; vector<long long>S; int main() { while(~scanf("%I64d%I64d",&n,&k)){ ans=0; for(long long i=log2(n);i>=0;i--){ long long tmp=pow(2,i); if(k>0){ k--; mp[tmp]=1; S.push_back(tmp); ans+=tmp; } else{ int L=S.size(); for(int j=0;j<L;j++){ if(mp[S[j]]==1&&S[j]+tmp<=n&&mp[S[j]+tmp]==0) { mp[S[j]]=0; mp[S[j]+tmp]=1; ans+=tmp; S.push_back(S[j]+tmp); break; } } } } printf("%I64d\n",ans); } return 0; }
但是仔细一想的话，得到了最大了2^n<=R,如果还可以异或一个，那么选择2^n-1就好了。(2^n)xor(2^n-1) =2^(n+1)-1。一定是最大的。
比如2^=10000, n=4,10000 xor 01111 = 11111；不可能还有不这个大的了,毕竟n=4是上界。当然只能选一个的时候，就选本身就好了。当然，为了避免卡精度问题（比如CF就hack我了），pow函数最好比较一下，这里太懒，算了。
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cmath> using namespace std; int main() { int a,b,ans,L,R; while(~scanf("%d%d",&L,&R)){ if(L==R) printf("%d\n",L); else { int a=log2(R); a=q_pow(2,a); printf("%d\n",a+a-1); } } return 0; }