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

代码语言：javascript复制

3
1 2 3

output

代码语言：javascript复制

2

input

代码语言：javascript复制

2
1 5

output

代码语言：javascript复制

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次就可以处理完！

代码

代码语言：javascript复制

#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

underscore javascript

0 人点赞