牛客网练习赛23C 托米的位运算题解
题意： 给定n个数， a[1]~a[n]， 从中选出k个数 k个数进行与运算的结果为b 使得b%(2^v)==0, 要求v最大， 同时取得的数最多。
思路： 根据二进制的性质可知， 如果我们选中的这些数有一个共同的位(假设该位为第v位)为1即符合b%(2^v)==0， 那么这一位尽量靠前， 则v最大。
所以从大到小枚举二进制位，进行判断即可。 ①枚举的该位为1， ②并且选出的这些数低于这一位的数不全为1 即可。
ps: 如果该位为第v位， 设oth = 2^v - 1 ， oth不断与选出的数相与，如果最后oth=0，则符合②这个条件。
最坏时间复杂度： 31 * 1e5 = 3e6
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N = 1e5+3;
int a[N];
vector<int>q;
int main()
{
int n;
scanf("%d", &n);
for(int i=0;i<n;i++){
scanf("%d", &a[i]);
}
for(int k=30;k>=0;k--){
int tp = (1<<k), oth = (1<<k)-1;
for(int i=0;i<n;i++){
if(tp & a[i]){
oth = oth&a[i];
q.push_back(a[i]);
}
}
if(oth==0) break;
}
if(q.size()==0){
printf("%d\n", n);
for(int i=0;i<n;i++){
printf("%d%c",a[i], i==n-1?'\n':' ');
}
return 0;
}
printf("%d\n", q.size());
for(int i=0;i<q.size();i++){
printf("%d%c",q[i],i==q.size()-1?'\n':' ');
}
return 0;
}
蔚来一面51人在聊
查看15道真题和解析
