题目分类:贪心,位运算
思路:看到题目范围(2e5,1e9),首先排除DP
我们需要选择物品子集,使得体积的按位与不超过k,价值的按位与最大。
看到按位与,可以想到应该要在数的二进制方面解出此题
按位与操作具有性质:选择的物品越多,结果的位数可能越少。

考虑二进制按位枚举,如何枚举最优?肯定是从高位到低位枚举
我们可以尝试从最高位到最低位逐位检查是否可以将该位设为1。对于每个候选值,检查是否存在物品子集,其中所有物品的价值包含该候选值,且这些物品的体积按位与结果不超过k。
若满足上述条件,则保留该位为1,同时更新答案;否则,继续检查下一位。

时间复杂度:O(31*n),可行

核心代码如下:(含注释)
int v[N],w[N];

void InfiniteLight() {
    int n,k;
    read(n);
    read(k);
    Forl(i,1,n){
    	read(v[i]); //体积
    	read(w[i]); //价值
	}
	int ans=0;
	Forr(i,30,0){ //按位从高到低枚举
		int tmp=ans|(1LL<<i); //现在正在尝试,看是否能够得到的值,需要保留之前的价值最大值,不然得到的结果一定比之前的最大值小 
                int vm=-1; //选中的所有价值所占的体积
		Forl(j,1,n){
			if((tmp & w[j])==tmp){ //满足条件,被选中,更新当前总体积
				if(vm==-1){
					vm=v[j];
				}else{
					vm=vm&v[j];
				}
			}
		}
		if(vm!=-1 && vm<=k){ //体积<k且需要至少一个物品被选中
			ans=tmp; //更新最大值
		}
	}
	println(ans);
    return ;
}