题意:给你一堆数,问你从里面跳出来两个数异或和最大。
(菜鸡第一次用字典树做题)
题解:之前没用过字典树做题,,看了大佬的题解,才知道字典树还有这种妙用。
对于二进制,如果我们想让它最大,(一点贪心的小思想)那么最高位的1 我们是要尽量保留的,(再就是保留次高位.....)。
对此我们建立一颗字01字典树,一条链对应的是一棵树的二进制形式,每次查询一个数字与已经放进去的最大异或值,
如何异或最大,就是在二进制下 与查询的这个数字 每位尽可能不同 **
**当然前提下是从 最高位到最低位进行遍历(最高位权重大)。
所以根节点的两个孩子代表的是最高位的二进制数是几
代码:
/*Keep on going Never give up*/ //#pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> #define int long long #define endl '\n' #define Accepted 0 #define AK main() #define I_can signed using namespace std; const int maxn =1e7+10; const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c0c00c; typedef long long ll; const int inf=0x3f3f3f3f; const ll mod=1e9+7; using namespace std; int n,total; int trie[maxn][2]; void ins(int x){ int node=0; for(int i=31;i>=0;i--){ int t=(x>>i)&1; if(!trie[node][t]) trie[node][t]=++total; node=trie[node][t]; } } int ifind(int x){ int node=0,res=0; for(int i=31;i>=0;i--){ int temp=(x>>i)&1,t=temp^1; if(trie[node][t]) node=trie[node][t],res=res<<1|1; else node=trie[node][temp],res<<=1; } return res; } signed main() { ios::sync_with_stdio(false); int n; cin>>n; int ans=0; for(int i=1;i<=n;i++){ int x; cin>>x; ans=max(ans,ifind(x)); ins(x); } cout<<ans<<endl; return 0; }