D.Dr.EvilUnderscores(分治大法好哇)jziwjxjd的博客-

$可能是我理解不太行….感觉很多博客没有讲到原理…$

可能是我理解不太行....感觉很多博客没有讲到原理...

不要去想怎么构造x,直接贪心的考虑答案

$color{Red}Ⅰ.从最高位i看起,如果这一位只有1$

Ⅰ.从最高位i看起,如果这一位只有1

$那么一定是选1把这一位异或掉,考虑下一位二进制$

那么一定是选1把这一位异或掉,考虑下一位二进制

$color{Red}Ⅱ.如果这一位只有0$

Ⅱ.如果这一位只有0

$那么一定是选0把这一位异或掉,考虑下一位二进制$

那么一定是选0把这一位异或掉,考虑下一位二进制

$color{Red}Ⅲ.如果这一位既有1也有0$

Ⅲ.如果这一位既有1也有0

$说明不管选0还是选1,这一位始终要加上(1<<i)$

说明不管选0还是选1,这一位始终要加上(1<<i)

$然后考虑下一位就应该分治了,可能最大值在二进制是1的那一组(此时放0)$

然后考虑下一位就应该分治了,可能最大值在二进制是1的那一组(此时放0)

$可能最大值在二进制是0的那一组(此时放1),递归取最小$

可能最大值在二进制是0的那一组(此时放1),递归取最小

#include <bits/stdc++.h> using namespace std; int n; int slove(vector<int>a,int deep) {  i(a.size()==0||deep<0) return 0;  vector<int>p1,p2;  for(int i=0;i<a.size();i++)  {   if( a[i]&(1<<k) ) p1.push_back(a[i]);//第deep位是1存在p1    else p2.push_back(a[i]); //0存在p2   }  if(p1.size()==0) return slove(p2,deep-1);  //这一位都是0,那么填1的话,p2所以元素异或后更大,往大的方向递归  if(p2.size()==0) return slove(p1,deep-1);   //否则,既有0也有1  return (1<<deep)+min(slove(p1,deep-1),slove(p2,deep-1));  } int main() {  scanf("%d",&n);  for(int i=1;i<=n;i++)  {   scanf("%d",&x);   a.push_back(x);  }  cout << slove(a,30) << endl; }