2024牛客寒假算法基础集训营1——H
输入
3 4 11 1 8 1 4 1 5 1 1 4 11 5 8 1 4 1 5 1 1 4 0 2 0 0 0 3 0 4 1输出
3 6 5
思路：
考虑二进制，有点像数位dp
本题考虑集合划分，累加最大值即可
代码如下：
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n, m; cin >> n >> m;
vector<int>v(n), w(n);
for(int i = 0; i < n; i ++){
cin >> v[i] >> w[i];
}
int ans = 0, pre = 0;
for(int i = 31; i >= 0; i --){
int x = pre;//置为前缀
if((m >> i) & 1){
x += (1 << i) - 1;//不选这一位是1，贪心出最大情况
pre += (1 << i);//更新前缀
}
int sum = 0;
for(int j = 0; j < n; j ++){
if((x | w[j]) == x){
sum += v[j];
}
}
ans = max(ans, sum);
}
//补上x==m这种情况
int sum = 0;
for(int j = 0; j < n; j ++){
if((m | w[j]) == m){
sum += v[j];
}
}
ans = max(ans, sum);
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
//t = 1;
cin >> t;
while(t--)
solve();
}