CF1285D Dr. Evil Underscores

思路：
首先建立字典树，然后递归计算。
实现：
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int INF = 0x7f7f7f7f;
 5 const int N = 100005;
 6 const int MAX_BIT = 31;
 7 int a[N], cnt = 0;
 8 
 9 struct trieNode
10 {
11     trieNode* next[2];
12 };
13 
14 trieNode pool[N * 32];
15 
16 trieNode* createTrie()
17 {
18     trieNode* root = &pool[cnt++];
19     for (int i = 0; i < 2; i++)
20     {
21         root->next[i] = NULL;
22     }
23     return root;
24 }
25 
26 void insert(trieNode* root, int x)
27 {
28     trieNode* tmp = root;
29     int index;
30     for (int i = MAX_BIT; i >= 0; i--)
31     {
32         int msk = (1 << i);
33         if (msk & x) index = 1;
34         else index = 0;
35         if (tmp->next[index] == NULL)
36         {
37             tmp->next[index] = createTrie();
38         }
39         tmp = tmp->next[index];
40     }
41 }
42 
43 int search(trieNode* root, int d)
44 {
45     if (root->next[0] == NULL and root->next[1] == NULL) return 0;
46     if (root->next[0] and root->next[1]) 
47     {
48         int tmp = min(search(root->next[0], d - 1), search(root->next[1], d - 1));
49         return tmp + (1 << d);
50     }
51     else if (root->next[0]) return search(root->next[0], d - 1);
52     else return search(root->next[1], d - 1);
53 }
54 
55 int main()
56 {
57     int n;
58     while (cin >> n)
59     {
60         for (int i = 0; i < n; i++) cin >> a[i];
61         trieNode* root = createTrie();
62         for (int i = 0; i < n; i++) insert(root, a[i]);
63         int ans = search(root, 31);
64         cout << ans << endl;
65     }
66     return 0;
67 }