Dr. Evil Underscores

题目:Dr. Evil Underscores

D. Dr. Evil Underscores

time limit per test:1 second
memory limit per test:256 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).

input

3
1 2 3

output

2

input

2
1 5

output

4

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

题目大意

给你n个数,让你寻找一个X,使X异或这n个数的最大值尽可能的要小

解题思路

第一题写这个题感觉还挺有意思的,仔细想了想查了查博客终于明白了,既然是位运算那肯定和二进制有关,把每个数据都按二进制去思考,如果这些数某个二进制位置上的数既有0又有1,那么不论取值X的二进制位置上对应的位置上是0还是1,这个位置上异或后的值一定是1!所以,我们每次统计一下,如果这个位置既有0又有1,那么这个位置异或后肯定是1,如果这个位置上的数据相同,那么我们就不用管它,让这个位置上的值为0,就好了最大值尽可能的小;然后我们这样每次按位处理,最多30次就可以处理完!

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int solve(vector<int> ve,int x)
{
    if(x==-1) return 0;
    if(ve.size()==0) return 0;//递归到头了,没有数据了;直接返回就可以 
    vector<int> l,r;//区分给位置的数值  
    for(int i:ve) 
    {
        if(i&(1<<x)) l.push_back(i);//如果是 1 就放进 l 里面 
        else r.push_back(i);//0就放进 r里面; 
    }
    if(l.size()==0) return solve(r,x-1);//左边为空说明这个位置都是 1 ,直接处理右边 
    if(r.size()==0) return solve(l,x-1);//右边为空说明这个位置都是 0 ,直接处理左边 
    return min(solve(r,x-1),solve(l,x-1))+(1<<x);//因为是要最小值,所以让最小的加上  
}                                    //二进制该位置唯一的十进制数(类似进制转换)        

int main()
{
    cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
    }
    cout<<solve(v,29)<<'\n';
    return 0;
} 

我的博客即将同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=2heqlgm91i04w


 本篇
Dr. Evil Underscores Dr. Evil Underscores
题目:Dr. Evil UnderscoresD. Dr. Evil Underscores time limit per test:1 second memory limit per test:256 megabytes inputst
2020-04-01
下一篇 
D. Minimax Problem D. Minimax Problem
题目链接:D. Minimax Problemtime limit per test:5 seconds memory limit per test:512 megabytes inputstandard input outputstand
2020-04-01
  目录