51nod1315(位运算)

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1315

题意：中文题诶～

思路：位或(|)运算是二进制位有一个为１就为１，否则为０．你们我们不难想到如果大于k的元素加入运算中其结果一定大于k, 与k异或结果大于k的元素加入运算中其结果一定不为k,　所以我们只要考虑剩下的元素就好了。剩下的也不难想到，对于当前二进制位，若k为１，那么我们可以把所有当前二进制位为１的元素去掉，其子集异或结果一定不为k；若k为０，那么我们可以把所有当前二进制位为0的元素去掉，其子集异或结果一定不为k. 我们只要取这些选择中最优的就是答案啦。。。

代码：

#include <bits/stdc++.h>
#define MAXN 60
using namespace std;

int a[MAXN];

int main(void){
    int n, k, ans=0, x, pos=0;
    cin >> n >> k;
    for(int i=0; i<n; i++){
        cin >> x;
        if(x<=k&&(x|k)<=k){//**注意这里的括号一定不能少，被坑惨了。。。
            a[pos++]=x;
            ans|=x;
        }
    }
    if(!pos||ans<k){
        cout << 0 << endl;
        return 0;
    }
    sort(a, a+pos);
    int cnt=n, key;
    while(k){
        int cc=0, gg=0;
        for(int i=0; i<pos; i++){
            if(!a[i]){
                continue;
            }
            if(a[i]%2){
                cc+=1;
            }else{
                gg+=1;
            }
            a[i]>>=1;
        }
        key=k%2;
        k>>=1;
        if(key){  //***k当前二进制位为１，我们可以选择把所有当前位二进制为１的元素删掉
            cnt=min(cnt, cc);
        }else{　　//***k当前二进制位为０，我们可以选择把所有当前位二进制为０的元素删掉
            cnt=min(cnt, gg);
        }
    }
    cout << cnt << endl;
    return 0;
}