当前位置: 代码迷 >> 综合 >> CH 1602 求序列中两数最大异或
  详细解决方案

CH 1602 求序列中两数最大异或

热度:91   发布时间:2024-01-28 04:11:40.0

题目

书上的解释一开始没懂,看了代码才知道是怎么回事。

我们把每一个数都转换成长度为32的二进制串,每一个数插入之前都会去找与它自己异或最大的值,但是怎么找呢?根据异或的特性我们可以得知,每一位与自己不同可以令数最大,那么对于第i个数的每一位,都要去找与这位不同的数(根据树的特性,我们从高位到低位储存是最容易处理的,因为这样做确保最高位最大),能找到这一位为1,不能则为0。不懂看看代码就明白了

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<iostream>
#include<bitset>
#define int long long
using namespace std;
int trie[100002*33][3],n,a[100002],ans,k=1;
void inse(int x)
{int p=0;for(int i=31;i>=0;i--){int c=(x>>i)&1;if(!trie[p][c]){trie[p][c]=k++;}p=trie[p][c];}
}
int fin(int x)
{int p=0,anss=0;for(int i=31;i>=0;i--){int c=(x>>i)&1;int o=c^1;if(trie[p][o]){p=trie[p][o];anss=anss<<1|1;}else{p=trie[p][c];anss=anss<<1;}}return anss;
}
signed main()
{cin>>n;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);} for(int i=1;i<=n;i++){ans=max(ans,fin(a[i]));inse(a[i]);}cout<<ans;
}