1285DDr. Evil Underscores

Vera ·

更新时间:2024-11-14

· 585 次阅读

链接：http://codeforces.com/contest/1285/problem/D

D. Dr. Evil Underscores

time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Today, as a friendship gift, Bakry gave Badawy n integers a1,a2,…,an and challenged him to choose an integer X such that the value max1≤i≤n(ai⊕X) 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≤i≤n(ai⊕X).

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

The second line contains n integers a1,a2,…,an (0≤ai≤230−1).

Output
Print one integer — the minimum possible value of max1≤i≤n(ai⊕X).

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

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

思路：

数据范围是2的30次方，我们在二进制下进行操作，最多有30位，所以我们直接从第30位进行考虑，对每一位来讲
分两种情况看：

这个二进制位上全是0或者全是1，这个时候当然 X 的二进制位也要是0或者1，保持相同异或才能是0嘛；这个时候整个集合不变，去看下一位；当这一位又有0又有1的时候，就把是0的分成一组，是1的分成一组，此时不管怎样异或最大值的二进制在这一位是1，然后再分别对这两个集合进行分情况讨论，也就是递归下去；

#include 
using namespace std;
typedef long long ll;
vector  a;
int get_ans(vector  &now,int bit)
{
	if(now.size()==0||bit<0) return 0;
	vector zero,one;
	for(int i=0;i>bit)&1) one.push_back(now[i]);
		else zero.push_back(now[i]);
	}
	if(!one.size()) return get_ans(zero,bit-1);
	if(!zero.size()) return get_ans(one,bit-1);
	return min(get_ans(zero,bit-1),get_ans(one,bit-1))+(1<>n;
	int x;
	for(int i=0;i>x,a.push_back(x);
	cout <<get_ans(a,30)<<endl;
}

作者：lywyqmam

ddr

1024 个赞