2 条题解
-
2姜逸飞 (jiangyifei) LV 6 @ 2022-8-28 11:37:23
/***************************************** Note: ******************************************/ #include <queue> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> using namespace std; #define LL long long const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; int tr[N*2][2] , a[N] , idx; void add(int x) { int len = 0; for(int i = 30 ; ~i ; i-- ) { int k = (x & (1 << i)) ? 1 : 0; if(!tr[len][k]) tr[len][k] = ++idx; len = tr[len][k]; } } int find(int x) { int len = 0 , ans = 0; for(int i = 30 ; ~i ; i-- ) { int k = (x & (1 << i)) ? 0 : 1; if(tr[len][k]) { ans += (1 << i); len = tr[len][k]; } else len = tr[len][k^1]; } return ans; } int main() { int n; cin >> n; for(int i = 1 ; i <= n ;i ++) { cin >> a[i]; add(a[i]); } int maxx = 0; for(int i = 1 ; i <= n ; i++) maxx = max(maxx , find(a[i]) ); cout << maxx << endl; return 0; }
-
12022-8-28 11:22:14@
/***************************************** Note: ******************************************/ #include <queue> #include <set> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; #define LL long long const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; int a[N],n,maxn; struct node{ int son[3],f; node(){ memset(son,0,sizeof(son)); f=-1; } }trie[N*2]; int idx=0; void add(int x) { int num=0; for(int i=30;i>=0;i--) { bool y=(x>>i)&1; if(!trie[num].son[y]) trie[num].son[y]=++idx; num=trie[num].son[y]; } } int find(int x) { int num=0,sum=0; for(int i=30;i>=0;i--) { bool y=(x>>i)&1; if(trie[num].son[!y]) { sum+=((y^1)<<i); num=trie[num].son[y^1]; } else { sum+=(y<<i); num=trie[num].son[y]; } } return x^sum; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { cin>>a[i]; add(a[i]); } for(int i=1;i<=n;i++) maxn=max(maxn,find(a[i])); cout<<maxn; return 0; }
- 1
信息
- ID
- 391
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- 递交数
- 60
- 已通过
- 19
- 上传者