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

京公网安备 11010502036488号