7 条题解
-
4
楼上使用的是递归版的01Trie插入。 我用的循环的方式:
#include <bits/stdc++.h> #include <cstdlib> using namespace std; const int N=31000010; int son[N][2]; int cnt[N]; int idx; int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { ch=getchar(); if(ch=='-')f=-1; } while('0'<=ch&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } void insert(int x) { int p=0; for(int i=31;i>=0;i--) { int u=x>>i&1; if(!son[p][u])son[p][u]=++idx; p=son[p][u]; } cnt[p]++; } int n; int res=0x80808080; int findxor(int x) { int p=0,res=0; for(int i=31;i>=0;i--) { int u=x>>i&1; if(son[p][!u])p=son[p][!u],res+=1<<i; else p=son[p][u]; } return res; } int a[N]; int main() { n=read(); for(int i=1;i<=n;i++) { a[i]=read(); insert(a[i]); } for(int i=1;i<=n;i++)res=max(res,findxor(a[i])); printf("%d\n",res); return 0; }
信息
- ID
- 94
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 682
- 已通过
- 165
- 上传者