这道题其实是一道思维题目,我们可以观察到,价值&的越多,答案可能会越小,而体积&的越多反而对我们越有利,由于数据范围并不大,可以直接枚举答案,枚举每种价值,再枚举每个物品价值,如果&进来不会影响,就加进来,因为体积&是更有利的,意思就是把每个满足当前价值的物品体积&起来,最后判断一下是否小于等于k即可。
#include <bits/stdc++.h> using namespace std; #define endl '\n' typedef long long ll; const int N = 2e3 + 10; const int mod = 998244353; void solve() { int n,k; cin>>n>>k; vector<int> v(n+1),w(n+1); for (int i = 1; i <= n; ++i) { cin>>v[i]>>w[i]; } int ans = 0; for (int i = 2000; i >= 0; --i) { ll tmp = (ll)(1<<20) - 1; //用来计算每次枚举的体积。为什么不初始化为1呢 for (int j = 1; j <= n; ++j) {//因为初始化为1时,枚举的结果可能并不存在但tmp <= k,这就存在问题了 if( (w[j]&i) == i ){ //为什么要减一呢,因为要保证第一次与体积&不会发生变化,减一就变成了XXX111111111111 tmp = tmp&v[j]; } } if(tmp <= k){ cout<<i<<endl; return; } } cout<<ans<<endl; } int main() { int t = 1; //cin >> t; while (t--) { solve(); } return 0; }
对于F,是E的变形,我们不能直接暴力枚举答案,但我们可以枚举答案的每一位,从最高位开始,如果为1满足就把当前位变成1,否则为0,这样贪心的选择,最后的结果一定是最优的。
#include <bits/stdc++.h> using namespace std; #define endl '\n' typedef long long ll; const int N = 2e3 + 10; const int mod = 998244353; void solve() { int n,k; cin>>n>>k; vector<int> v(n+1),w(n+1); for (int i = 1; i <= n; ++i) { cin>>v[i]>>w[i]; } ll ans = 0; for (int i = 30; i >= 0; --i) { //枚举答案每一位 ans = ans|(1<<i); //把当前位赋值为1 ll tmp = (ll)(1<<30) - 1; //重复E的判断 for (int j = 1; j <= n; ++j) { if( (w[j]&ans) == ans){ tmp = tmp&v[j]; } } if(tmp > k){ ans = ans^(1<<i); //不满足就把当前为赋值为0 } } cout<<ans<<endl; } int main() { int t = 1; //cin >> t; while (t--) { solve(); } return 0; }