题意:给出n组数据,ai,bi,意味着编号为ai的物品价值为bi,求选择一些ai,他们或运算之后小于或等于k的最大价值。

题解:贪心法,因为当前选择的ai或运算之后有可能会大于k,考虑到或运算的性质,假设当前选择的数或运算之后必须小于或者等于k,那么我们必须要选择这样的一个a[i],a[i]&k==a[i]。即k的二进制位上有1的地方,a[i]才能有1。然后,循环将k二进制位上有1的位减一(即去掉这个1,低位补1),然后同上面选择k一样进行计算,最后求得最大值即可。


代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
int n, k;
int bit[33], a[maxn], b[maxn];
int main(){
    for(int i=0;i<30;i++)bit[i]=1<<i;
    while(~scanf("%d %d", &n, &k)){
        LL ans=0;
        for(int i=0;i<n;i++){
            scanf("%d%d", &a[i], &b[i]);
            if((a[i]&k)==a[i])ans+=b[i];
        }
        for(int i=0;i<30;i++){
            if(bit[i]&k){   //当前位有1
                int tmp=(bit[i]^k)|(bit[i]-1);
                LL tans=0;
                for(int j=0;j<n;j++){
                    if((a[j]&tmp)==a[j])tans+=b[j];
                }
                ans=max(ans, tans);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}