Dr. Evil Underscores
- 2020 年 4 月 9 日
- 筆記
题目：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
