牛客网练习赛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;
}

全部评论

推荐最新楼层

bonjour201801211612594

江苏海洋大学 Java

你好，我的写法是判断b所在的区间【2*v,2*v+1），而实际上只需求出原序列最大值m，m必然在这个区间中，得到m后就知道了v的值，然后筛选其他在这个区间的数即可。但是我提交后只有71%的正确率。是我的思路有问题吗？

点赞回复分享

发布于 2018-08-03 09:47

bonjour201801211612594

江苏海洋大学 Java

#include<iostream> #include<string> #include<cstring> #include<vector> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 1e5+5; ll pow2[33]; ll inp[maxn]; int main(){ int n ; scanf("%d",&n); pow2[0]=1; for(int i = 1; i<=32;i++) pow2[i]=pow2[i-1]*2; for(int i=0;i<n;i++) scanf("%lld",&inp[i]); vector<ll> v(inp,inp+n); sort(v.begin(),v.end()); ll m = v[n-1]; ll t =-1 ; for(int i = 32 ; i>=0 ; i--) if(pow2[i]<=m){ t = i; break ; } vector<ll>ans; for(int i = 0 ;i < n;i++) if(inp[i]>=pow2[t]&&inp[i]<pow2[t+1]) ans.push_back(inp[i]); printf("%d\n",ans.size()); for(int i = 0 ; i<ans.size();i++){ printf("%d",ans[i]); if(i!=ans.size()-1)printf(" "); else printf("\n"); } return 0 ; }

点赞回复分享

发布于 2018-08-03 09:50

今天晚上吃什么

清华大学运营

大佬能写下这期的完整题解吗~

点赞回复分享

发布于 2018-08-14 16:16