这道题其实是一道思维题目,我们可以观察到,价值&的越多,答案可能会越小,而体积&的越多反而对我们越有利,由于数据范围并不大,可以直接枚举答案,枚举每种价值,再枚举每个物品价值,如果&进来不会影响,就加进来,因为体积&是更有利的,意思就是把每个满足当前价值的物品体积&起来,最后判断一下是否小于等于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;
}