题目

n(n<=150000)个数，第i个数ai(0<=ai<2^30)，

你可以选择一个非负的数x，对每个数都异或x，

使ai异或x的最大值最小，输出此时的最大值

思路来源

自己20年1月的补题提交

原题：Codeforces Round #613 (Div. 2) D. Dr. Evil Underscores

题解

考虑按位分治，

1.当有一位全是0或者全是1时，一定可以置0

2.当不全是1时，会把数分成两堆，其中一堆取0，另一堆取1，

因为有后效性，所以对低位，递归这两堆，

将其中较小的数挂在1的后面，较大的数挂在0的后面

心得

cf1900做过的原题，破防了，

甚至看到代码提交，还能想起当时是按dup4的提交补的

但是，当时没有写博客，

今天做这题的时候正解一瞬而过，但可惜也只是一瞬

那就补一下吧

代码

#include
using namespace std;
typedef long long ll;
int n,v;
vectornow;
ll gao(int dep,vectorq)
{if(dep<0)return 0;int cnt[2]={0};for(int i=0;i>dep&1]++;if(!cnt[0]||!cnt[1])return gao(dep-1,q);else{vectornex[2];for(int i=0;i>dep&1].push_back(q[i]);return (1<