专栏首页一Wa哇一天Dr. Evil Underscores

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • F2. Animal Observation (hard version)

    time limit per test:3 seconds memory limit per test:512 megabytes inputstandard ...

    某些人
  • D. Minimax Problem

    time limit per test:5 seconds memory limit per test:512 megabytes inputstandard ...

    某些人
  • 树的直径

    这个题刚开始一直不理解,可能是对树的的直径比较陌生吧,可后来看看了看学长给我板子。我去咋这么简单emmm,我真是个智障呀。只要从任意一个节点出发然后找到距离他最...

    某些人
  • LeetCode Weekly Contest 33解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode 914. 卡牌分组(最大公约数)

    每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X >= 2 时返回 true。

    Michael阿明
  • LeetCode 559. N叉树的最大深度

    Michael阿明
  • Leetcode Golang 1. Two Sum.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88866806

    anakinsun
  • 爬楼梯

    一份执着✘
  • Spring的事务管理

    Spring有一个基于AOP之上的事务管理模块,这个模块能够帮助我们在逻辑层中很方便的控制数据库的事务。在此之前我们介绍了Spring对JDBC的模板支持 以及...

    端碗吹水
  • 如何比较?Comparable还是Comparator

    我家开了个小卖店,为了实现数字化管理,我准备写个后台程序来对所有货物进行管理。首先定义了这个实体类,这个类就是“货物”类,num指的是他的编号,s指他的名称或描...

    naget

扫码关注云+社区

领取腾讯云代金券