Light Emitting Hindenburg 解题思路

ACM-ICPC

Publish Date: 2020-11-01

题目大意：

给你n个数，你从里面选出k个数，是他们相与（&）起来的值最大。
题目地址：https://nanti.jisuanke.com/t/45643

思考过程：

在二进制下，假设a有一位是1（前面都是0），而b的那一位是0，且前面没有1，那么无论b的后面是多少，a永远大于b
所以，从最开始的一位检查，如果能找到k个数，这k个数这一位是1，那么这k个数一定有构成最优解的潜质。所以就不断地这么从前往后找。

具体过程：

从第一位开始检索，统计这一位是1的个数，如果这一位为1的数的个数大于k，那么这一位肯定有戏，以后就从这几个数里面选，放弃掉这一位不是1的数。如果小于k，那么这一位就没戏了，直接取检查下一位。
最后，把所有没有放弃的数&起来就是最终结果了。
有多种可能情况也没事，因为有多种情况说明有几个数是一样的，他们&起来也是一样的。

#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
const int maxn=2e5+7;

int a[maxn],sc[maxn],n,k;

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=31;i>=0;--i){
        int cnt=0;
        for(int j=1;j<=n;++j)
            if(sc[j]==0&&((a[j]>>i)&1))
                cnt++;
        if(cnt<k) continue;
        else{
            for(int j=1;j<=n;++j)
                if(sc[j]==0&&((a[j]>>i)&1)==0)//如果能凑够k个数，而这个数这一位不是1
                    sc[j]=1;//放弃了这个数
        }
    }
    int ans=-1;
    for(int i=1;i<=n;++i)
        if(!sc[i]) ans&=a[i];
    printf("%d\n",ans);
    return 0;
}