Solution for ZZQ's Maximum AND
Solution for ZZQ's Maximum AND
idea by bakapiano
prepared by bakapiano
题意
在 \(n\) 个数中选恰好 \(k\) 个使得这 \(k\) 个数 \(and\) 起来的和最大。
题解
题目难度 easy+
注意到位运算时各位的运算是相互独立的，因此我们可以将这 \(n\) 个数拆成二进制并从高位到低位依次考虑。假设当前处理的是第 \(i\) 位，我们首先统计在二进制下这一位是 \(1\) 的数的个数 \(num\)，然后我们分两种情况进行讨论：
若 \(k \leq num\)，说明存在一种选数的方案使得这一位是 \(1\)，此时我们可以抛弃这一位是 \(0\) 的那些数而仅保留这一位是 \(1\) 的数，可以这么做的依据是如果我们选择了某一个该位是 \(0\) 的数作为 \(k\) 个数中的一个，那么这一位 \(and\) 起来的结果必然是 \(0\)，但是考虑到低位无论如何组合都不可能比这一位是 \(1\) 的结果更优，因此我们不可能选择这一位是 \(0\) 的那些数作为我们选择的结果之一。
若 \(k > num\)，说明无论怎么选这一位 \(and\) 的结果都必为 \(0\)，因此保留所有数并继续处理下一位即可。
时间复杂度 \(O(nlogn)\)，可以在规定时限内通过本题。
此外可以考虑一下 \(m\) 组询问，每次询问给出 \(k\) 的加强版怎么做：）
tag: 贪心 位运算
标称
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
int n,k;
int val[MAXN];
int solve()
{
int ans=0;
vector<int> a,b;
for(int i=1;i<=n;i++) a.push_back(val[i]);
for(int i=20;i>=0;i--)
{
int cnt=0;
for(auto x:a) if(x&(1<<i)) cnt++;
if(cnt>=k)
{
ans+=(1<<i);
b.clear();
for(auto x:a) if(x&(1<<i)) b.push_back(x);
swap(a,b);
}
}
return ans;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
printf("%d\n",solve());
return 0;
}