题意：今天，作为一个友谊礼物，Bakry给予Badawy n个整数a1，a2，...，an，让他去寻找一个数X，使得max(ai⊕X) 1≤i≤n最小。
思路：从高位往低位走，直到遇到第一个0和1树，这时无论x是什么，必取1，题目要求最大值中的最小值，所以在没遇到第一个01树之前，取1亦或变大是没用的，无法成为最大值中的最小值，只有在第一个必取1的情况下，最小值才可能诞生。从第一个01树往下遍历，若是单独0或1则异或值可直接为0，但是若0和1都有，则必然为1，对于要求的最小值，01都存在时无法避免，只有单个子节点时取0可得最小。
1 #include<iostream> 2 #include<algorithm> 3 #include<queue> 4 #include<stack> 5 #include <bitset> 6 #include<set> 7 #include<map> 8 #include<unordered_map> 9 #include<vector> 10 #include<cmath> 11 #include<string> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int, int> p; 15 typedef unsigned long long ull; 16 17 int n; 18 vector<int> a; 19 int slove(vector<int> a, int k) { 20 if (a.size() == 0 || k < 0) { 21 return 0; 22 } 23 vector<int> p1, p2; 24 //每调用一次k-1，直到数值的第i位不同时，第i位取1，他是最大值中最小值的第i位 25 for (int i = 0; i < a.size(); i++) { 26 if ((a[i] >> k) & 1) { 27 p1.push_back(a[i]); 28 } 29 else { 30 p2.push_back(a[i]); 31 } 32 } 33 // 之后若仍有两条路，那条路必取1，若只有一条路则可取0 34 if (p1.size() == 0) { 35 return slove(p2, k - 1); 36 } 37 if (p2.size() == 0) { 38 return slove(p1, k - 1); 39 } 40 return (1 << k) + min(slove(p1, k - 1), slove(p2, k - 1)); 41 } 42 43 int main() { 44 cin >> n; 45 int x; 46 47 for (int i = 0; i < n; i++) { 48 cin >> x; 49 a.push_back(x); 50 } 51 // 从高位往低位建树 52 cout << slove(a, 30) << endl; 53 return 0; 54 }