写在前边:记录一下蒟蒻的补题日常
上题
题目描述
样例
4
3 2
2 1 1
7 0
4 6 6 28 6 6 12
1 30
0
4 4
3 1 3 1
输出
2
4
2147483646
1073741825
题意
给你 n, k 让你进行最多k次操作 使得整个数组 & 操作得到最大值.关于每次操作 你可以改变数组中某个数的某个二进制位变为 1
思路
首先,我们要明白&在本题的含义,即在这某一位上,其他的数在此都是1的情况下,最后的答案在这一位就取1(二进制),否则取0.为了最后的答案最大化,我们尽量选择在不超过k次操作的情况下能够取到此位(即每个数在此位上都是1),并且从高位向低位取.由此枚举每一位,并进行合适的累加即得到答案.
我们首先统计 二进制中 0-30 位每位有多少个 1,要想 & 运算取得最大值我们需要尽可能的把 高位 统一为 1 ,所以接下来我们贪心从最高位开始遍历,如果剩余的次数大于等于 该位不是1的个数,我们就可以加上该位的二进制数,继续向下遍历
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve()
{
int n,k;
cin >> n >> k;
vector<int> a(31,0);
for(int i = 0; i < n; i ++ )
{
int x;
cin >> x;
for(int j = 0; j < 31; j ++ )
{
a[j] += (x >> j & 1);
}
}
int res = 0;
for(int i = 30; i >= 0; i -- )
{
if(k >= n - a[i])
{
k -= (n - a[i]);
res += (1 << i);
}
}
cout << res << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T -- )
{
solve();
}
return 0;
}
其中
res += (1 << i) 与 res |= (1 << i) 是等价的 (某些黑红大佬喜欢|=)
至此
在本题中,我们需要知道&与|的含义, 并理解 OR 2^j 是在某一位上添1即可快速解题.
比赛的时候脑子容易短路,可能这方面刷的题还不够多,还需要继续努力!