2024牛客寒假算法基础集训营1——H

本文主要是介绍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();
}

这篇关于2024牛客寒假算法基础集训营1——H的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---