Codeforces Round 779 (Div. 2) D2. 388535（思维题 二进制性质/trie树上最大最小异或）

本文主要是介绍Codeforces Round 779 (Div. 2) D2. 388535（思维题 二进制性质/trie树上最大最小异或），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

t(t<=1e5)组样例，每次给定l,r(0<=l<r<2^17)

和r-l+1个数ai，新序列是被[l,r]这些数异或上同一个x得到的，

求出x，有多个输出任意一个即可

思路来源

官方题解

洛谷题解

Educational Codeforces Round 157 (Rated for Div. 2) D. XOR Construction (思维题)-CSDN博客

心得

Educational Codeforces Round 157 (Rated for Div. 2) 是该题的减弱版，感觉一模一样

题解1（性质）

注意到，若a^b=1，则(a^x)^(b^x)=1恒成立

如果l是偶数，r是奇数，那么x的末尾是0或1均可，因为总可以将ai和ai^1两两配对

此时可以将末位除掉，规模递减到原来一半，继续递归

否则，当我们将ai和ai^1两两配对时，

由于原序列末位所构成序列，形如01010或者10101，必有一个无法配对

l%2==0时，r无法配对，否则l无法配对，记原来无法配对的数为ans

遍历这r-l+1个数，找到无法配对的那一个ai，ans^ai=x成立，输出x即可

题解2（trie树）

r-l+1个数中，肯定有一个ai是l^x得到的，那么令每个数再异或l，

即令bi=ai^l，必有一个bi是等于x的，

将每个ai插入到trie上，枚举bi，

若存在一个bi，min(bi^trie)=l，max(bi^trie)=r，则bi即为x所求

其中，min(bi^trie)表示取trie上一个数和bi异或能得到的最小值，

max表示取trie上一个数和bi异或能得到的最大值

代码1（性质）

#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 5;
int a[N], l, r; 
set <int> s, s2;void solve() {int mul = 1;s.clear();cin >> l >> r; for (int i = l; i <= r; ++i) {cin >> a[i];s.insert(a[i]);}for (; l % 2 == 0 && r % 2 == 1; l >>= 1, r >>= 1, mul <<= 1) {s2.clear();for (int i: s) s2.insert(i >> 1);swap(s, s2);   }int ans;if (l % 2 == 0) ans = r;else ans = l;for (int i: s) {if (s.find(i ^ 1) == s.end()) {int cur = i ^ ans;bool f = true;for (int j : s)f &= ((cur ^ j) >= l && (cur ^ j) <= r);if (f) {ans = cur;break;}}}cout << ans * mul << '\n';
}int main() {ios_base::sync_with_stdio(false);cin.tie(NULL);int t; cin >> t;while (t--) solve();return 0;
}

代码2（trie树）

#include<bits/stdc++.h>
#define N 1000005
#define int long long
using namespace std;
int T,l,r,a[N],cnt,trie[N][30],b[N];
void insert(int sum){int now=0;for(int i=17;i>=0;i--){bool tmp=(1<<i)&sum;if(!trie[now][tmp])trie[now][tmp]=++cnt;now=trie[now][tmp];}
}
int Max(int sum){int now=0,res=0;for(int i=17;i>=0;i--){bool tmp=(1<<i)&sum;if(!trie[now][tmp^1])now=trie[now][tmp];else now=trie[now][tmp^1],res+=(1<<i);}return res;
}
int Min(int sum){int now=0,res=0;for(int i=17;i>=0;i--){bool tmp=(1<<i)&sum;if(!trie[now][tmp])now=trie[now][tmp^1],res+=(1<<i);else now=trie[now][tmp];}return res;
}
signed main() {cin>>T;while(T--){cin>>l>>r;for(int i=0;i<=cnt;i++)trie[i][0]=trie[i][1]=0;cnt=0;for(int i=l;i<=r;i++)cin>>a[i],b[i]=a[i]^l;for(int i=l;i<=r;i++)insert(a[i]);for(int i=l;i<=r;i++){if(Max(b[i])==r&&Min(b[i])==l){cout<<b[i]<<endl;break;}}}
}

这篇关于Codeforces Round 779 (Div. 2) D2. 388535（思维题 二进制性质/trie树上最大最小异或）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---