自动搬运

查看原文

来自洛谷，原作者为

	codwarm #define INF 0x3f3f3f3f

搬运于2025-08-24 22:50:06，当前版本为作者最后更新于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;
}