起床困难综合症
https://www.acwing.com/problem/content/1000/
思路:枚举每一位的数,计算位运算后的结果;为了保证得到的数在运算后得到的值最大,应从最高位开始枚举,原因如下
- 如果从高到低第 i 位填 1,判断 1 << i 是否小于等于 m,如果大于,则跳过该位
- 如果该位能填 1,则分别计算该位填 1 与 0 的情况:
- 如果填1后得到1,填0后得到0,则填 1 优于 0 ,结束后
m -= 1 << i
(后面几位填数的值不能超过该值); - 如果填 0 得到 1,或填 0 与填 1 都得到 0,则填 0 优于填 1(为了让后面能够填尽可能多的数位)
ac代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
string op[N];
int t[N];
int cal(int x, int j){ // 计算第 j 位上的 x 在操作后的值
for(int i = 1; i <= n; i ++){
if(op[i] == "AND") x &= t[i] >> j;
if(op[i] == "OR") x |= t[i] >> j;
if(op[i] == "XOR") x ^= t[i] >> j;
}
return x;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> op[i] >> t[i];
int res = 0;
for(int i = 30; i >= 0; i --){ // 枚举每一位,从最高位开始枚举
if(1 << i <= m){
int x1 = cal(0, i), x2 = cal(1, i);
if(x1 >= x2) res |= x1 << i;
else res |= x2 << i, m -= 1 << i;
}
else res |= cal(0, i) << i;
}
cout << res << '\n';
return 0;
}