526互联

1699H - Maximal And

发布时间 2023-07-01 12:43:20作者: Cruzz

思路：

0. 只有所有数这一位是1 &结果才为1
1. 想要得出最大值，高位越大越好 所以从高位开始操作
2. 记录所有数字的每位 为1的cnt[位数]++ 然后那位需要操作的次数为 n-cnt[位数]
3. 优先执行：操作数给高位 如果操作数不够使高位&后结果改变 则给可以被改变的最高位
4. 终止条件： 操作数为0或剩余所有位数均无法改动

#include<bits/stdc++.h>
using namespace std;
int t,n,k,a[200010],cnt[31],ans;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        ans=0;
        for(int i=0;i<31;i++){
            cnt[i]=0;
        }
        for(int i=0;i<n;i++){
            cin>>a[i];
            for(int j=30;j>=0;j--){
                if(a[i]&(1<<j)){
                    cnt[j]++;
                }
            }
        }
        for(int i=30;i>=0;i--){
            if(n-cnt[i]<= k) {
                k-=n-cnt[i];
                ans+=1<<i;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}