CF1285D. Dr. Evil Underscores（字典树）

本文主要是介绍CF1285D. Dr. Evil Underscores（字典树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Today, as a friendship gift, Bakry gave Badawy 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 and challenged him to choose an integer 𝑋 such that the value max1≤𝑖≤𝑛(𝑎𝑖⊕𝑋) is minimum possible, where ⊕ denotes the bitwise XOR operation.

As always, Badawy is too lazy, so you decided to help him and find the minimum possible value of max1≤𝑖≤𝑛(𝑎𝑖⊕𝑋).

Input
The first line contains integer 𝑛 (1≤𝑛≤105).

The second line contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖≤230−1).

Output
Print one integer — the minimum possible value of max1≤𝑖≤𝑛(𝑎𝑖⊕𝑋).

Examples
inputCopy
3
1 2 3
outputCopy
2
inputCopy
2
1 5
outputCopy
4
Note
In the first sample, we can choose 𝑋=3.

In the second sample, we can choose 𝑋=5.

题意：
给出n个数，求出所有数与这n个数异或后结果的最大值，这些最大值的最小值。
思路：
143. 最大异或对（字典树）acwing

异或的最大值，很明显是字典树。X是任意的，我们需要用字典树来维护这个最大值。
因为异或是同性相斥，异性相吸，那么对所有的数建完字典树，取0，往1走的最大值，取1，往0走得最大值，如果只有一个数，就可以取相同的数，答案就是确定的。
相当于，当前位有两个选择的时候，X怎么取，这个位都要得1，结果就是2的n次方。如果只有一个选择，那么这个位可以得0。按照这个思路，在字典树上递归的写就好了。关键点就在于，通过维护二进制每一个位上的数字0和1，再根据二进制规律进行运算。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;
typedef long long ll;int n;
int a[100005],t[7000005][3],tot = 1;void insert(int val)
{int p = 1;for(int i = 29;i >= 0;i--){int ch = (val >> i) & 1;if(t[p][ch] == 0){t[p][ch] = ++tot;}p = t[p][ch];}
}int solve(int cnt,int now)
{if(cnt == -1){return 0;}if(t[now][0] == 0){return solve(cnt - 1,t[now][1]);}else if(t[now][1] == 0){return solve(cnt - 1,t[now][0]);}else return (1 << cnt) + min(solve(cnt - 1,t[now][0]),solve(cnt - 1,t[now][1]));
}int main()
{scanf("%d",&n);for(int i = 1;i <= n;i++){scanf("%d",&a[i]);insert(a[i]);}int ans = solve(29,1);printf("%d\n",ans);return 0;
}

边建树边递归的写法

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;
typedef long long ll;
int n;int solve(vector<int>a,int cnt)
{if(cnt == -1){return 0;}vector<int>a0,a1;int len = (int)a.size();for(int i = 0;i < len;i++){if((a[i] >> cnt) & 1){a1.push_back(a[i]);}else{a0.push_back(a[i]);}}if(a0.size() == 0){return solve(a1,cnt - 1);}else if(a1.size() == 0){return solve(a0,cnt - 1);}else return (1 << cnt) + min(solve(a1,cnt - 1),solve(a0,cnt - 1));
}int main()
{scanf("%d",&n);vector<int>a;for(int i = 1;i <= n;i++){int tmp;scanf("%d",&tmp);a.push_back(tmp);}int ans = solve(a,29);printf("%d\n",ans);return 0;
}