P9612 [CERC2019] Light Emitting Hindenburg 题解

codwarm · 2023-09-13 00:49:41 · 题解

题目传送门~

题目大意

求从 n 个数中取 k 个数做与运算的最大值。

题目分析

阅读题面，可以知道本题与二进制运算有关，又根据题意，需要求出 k 个数做与运算的最大值，可以想到贪心的思路：从大到小枚举二进制位，若有大于等于 k 个数在当前二进制位上为 1，则将当前二进制位对应的权值加入答案，并在二进制位为 1 的数上打上标记，之后遍历时只有上次被打上标记的数才能参与运算（没有标记的数说明不在最大值中）。

贪心思路的证明：从大到小枚举二进制位，若当前二进制位可行，则必选当前位置。因为若不选当前位置，比当前位更低的二进制位的和不可能比当前位置大。

具体见代码，注释很清晰。

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

const int N = 200005;

int n, k, a[N], maxn, cnt;
bool vis[N];
int main()
{
    scanf("%d%d",&n, &k);
    for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
    memset(vis,1,sizeof vis);
    for (int i = 30;i >= 1;i--) //从大到小枚举第i位
    {
        cnt = 0;
        for (int j = 1;j <= n;j++) 
                            //指a[j]的第i位是否等于1
            if (vis[j] && (a[j] >> (i - 1) & 1)) //满足条件
                cnt++; //记录个数
        if (cnt < k) continue; //不及k则退出
        for (int j = 1;j <= n;j++)
            if (!(vis[j] && (a[j] >> (i - 1) & 1))) //将不满足条件的数打上0
                vis[j] = 0;
        maxn += (int)pow(2,i-1); //累加结果
    }
    cout << maxn;
    return 0;
}