1 条题解
-
1yejun LV 10 MOD @ 2019-01-08 21:03:30
/* 由于位运算不进位的特性 所以这里可以将每一位单独考虑 首先将所有数字补成32位二进制的形式(不足则加前导0) 然后依次将其每一位从高到低的插入trie 由于要保证最后异或值最大,所以在插入一个数字后,立刻在trie上查找它 查找时做以下操作: 若当前位为0,则判断trie里这一位是否有指向1的指针,若存在,则沿着这一条边遍历,否则沿着含0边遍历 若当前位为1同理 这样做的依据是:从高到低考虑每一位的时候若不同,则相当于之前有一个数字在这一位上与当前查找数不同,异或后这一位必然为1,在从高到低插入每一位的情况下,结果自然最大。 将每个局部最大的结果更新答案,就得到了全局最优解。 */ #define method_1 #ifdef method_1 /* */ #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<set> #include<map> #include<queue> #include<stack> #include<vector> #include<cstring> #include<cstdlib> using namespace std; typedef long long ll; const int maxn=1e5+5; const int INF=0x3f3f3f3f; ll n,m; char a[maxn]; ll trie[maxn*40][3]; ll tot=1; int ans=0; void insert(int val) { int p = 1; //因为p从1开始 所以tot初始化为1 for (int k = 30; k >=0; k--) { int ch = val>>k&1; if (trie[p][ch] == 0) trie[p][ch] = ++tot; p = trie[p][ch]; } } int search(int val) { int p = 1,ans=0; //因为p从1开始 所以tot初始化为1 for (int k = 30; k >=0; k--) { int ch = val>>k&1; if(trie[p][ch^1]){ ans|=1<<k; p=trie[p][ch^1]; } else{ p=trie[p][ch]; } } return ans; } int main() { ios::sync_with_stdio(false); cin>>n; ll x; for(int i=1; i<=n; i++) { cin>>x; insert(x); ans=max(ans,search(x)); } cout<<ans; return 0; } #endif #ifdef method_2 /* */ #endif #ifdef method_3 /* */ #endif
- 1
信息
- 难度
- 6
- 分类
- (无)
- 标签
- (无)
- 递交数
- 86
- 已通过
- 22
- 通过率
- 26%
- 被复制
- 4
- 上传者