1 条题解
-
0
#include<bits/stdc++.h> using namespace std; int const N=100010,M=31*N; int n,a[N],son[M][2],idx; //M代表一个数字串二进制可以到多长 void insert(int x){ int p=0; //根节点 for(int i=30;i>=0;i--){ int u=x>>i&1; //取X的第i位的二进制数是什么 x>>k&1(前面的模板) if(!son[p][u]) son[p][u]=++idx; //如果插入中发现没有该子节点,开出这条路 p=son[p][u]; //指针指向下一层 } } int search(int x){ int p=0;int res=0; for(int i=30;i>=0;i--){ //从最大位开始找 int u=x>>i&1; if(son[p][!u]){ //如果当前层有对应的不相同的数 //p指针就指到不同数的地址 p=son[p][!u]; res=res*2+1;//*2相当左移一位 然后如果找到对应位上不同的数res+1 } else { p=son[p][u]; res=res*2+0; } } return res; } int main(void){ cin>>n; idx=0; int res=0; for(int i=0;i<n;i++){ cin>>a[i]; res=max(res,search(a[i]));//search(a[i])查找的是a[i]值的最大与或值 insert(a[i]); } cout<<res<<endl; }
- 1
信息
- ID
- 484
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- (无)
- 递交数
- 34
- 已通过
- 21
- 上传者