前言:暑假集训时学的字典树orz 太弱了www
模板用的是wiki上用一个结构体封装的模板(当时就是看wiki学的字典树
链接:https://oi-wiki.org/string/trie/
做法:01字典树
思路:
- 一个整数,是可以转化成为一个32位的二进制数,而也就可以变成长度为32位的二进制字符串.
- 每一次检索的时候,我们都走与当前这一位相反的位置走,也就是让异或值最大,如果说没有路可以走的话,那么就走相同的路.
代码
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define X first #define Y second #define lowbit(a) (a&(-a)) typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; typedef long double ld; const int N=1e5+10; const int INF=0x3f3f3f3f; const int mod=1e9+7; const double eps=1e-6; int ans,a[N]; struct Trie { int nex[N*32][2],cnt=0; void insert(int x) { int p = 0; for (int i = 30; i >= 0; i--) { int c = x>>i&1; if (!nex[p][c]) nex[p][c] = ++cnt; p = nex[p][c]; } } int find(int x) { int p = 0,res = 0; for (int i = 30; i >= 0; i--) { int c = x>>i&1; if(nex[p][c^1]) p=nex[p][c^1],res|=(1<<i); else p=nex[p][c]; } return res; } } t; int main() { ios::sync_with_stdio(0); cin.tie(0); #ifdef DEBUG freopen("F:/laji/1.in", "r", stdin); // freopen("F:/laji/2.out", "w", stdout); #endif int n; cin>>n; _for(i,n){ cin>>a[i]; t.insert(a[i]); } _for(i,n){ ans=max(ans,t.find(a[i])); } cout<<ans; return 0; }