cf(Round613)D. Dr. Evil Underscores

巧妙递归系列

题意:

• 给定一个数组$a_n$an​, 要求任找一个数x, 并求$max_1^n(x\&a[i])$max1n​(x&a[i])的最小值

>> face <<

前置技能 : trie ?

数据范围 : $n\leq 1e5, a[i]\leq2^{30}-1$n≤1e5,a[i]≤230−1

tutorial: 若以a建trie树(a补全前导零),会发现出现分叉的点会对答案有贡献(因为选定了x是任意一条路都会对另外一条路有$2^i$2i的贡献),相反,若是只有一条路的话倒还好, 于是就会发现分岔路口是个突破点, 只要最小化分叉路口的个数就成

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define _rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define _rev(i, a, b) for (ll i = (a); i >= (b); --i)
#define _for(i, a, b) for (ll i = (a); i < (b); ++i)
#define _rof(i, a, b) for (ll i = (a); i > (b); --i)
#define oo 0x3f3f3f3f
#define ll long long
#define db double
#define eps 1e-8
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
const ll mod = 998244353;
const ll maxn = 7e6 + 10;

struct trie
{
	ll cnt = 1, ch[maxn][3];
	int init(int o)
	{
		met(ch[o], 0);
		return o;
	}
	void insert(ll val, int root = 1)
	{
		_rev(i, 29, 0)
		{
			int cur = (val >> i) & 1;
			if (!ch[root][cur])
			{
				ch[root][cur] = ++cnt;
			}
			root = ch[root][cur];
		}
	}
	ll dfs(int th, int cur){
		if(th == -1)return 0;
		if(!ch[cur][1])return dfs(th-1,ch[cur][0]);
		else if(!ch[cur][0])return dfs(th-1,ch[cur][1]);
		else return (1ll << th) + min(dfs(th-1, ch[cur][0]), dfs(th-1,ch[cur][1]));
	}
} store_data_trie;
ll a[maxn];

signed main()
{
	int n;
	cin >> n;
	
	_rep(i, 1, n)	
	{
		cin >> a[i];
		store_data_trie.insert(a[i]);
	}
	ll ans = store_data_trie.dfs(29, 1);
	cout << ans << endl;
}