题目大意:
让我们选择 $0$ 到 $m$ 之间的一个整数,经过给定的 $n$ 次位运算,使结果最大。
解题方法:
位运算的主要特点是在二进制下不进位,所以说,一个数的每一位是独立的,也就是说,答案的每一位只与最开始选定的每一位有关系,所以我们可以从高位到低位开始依次枚举(为什么要倒着枚举见补充说明)。
一开始选定的数的第 $k$ 位应该填 $1$,当且仅当满足下列两个条件:
- 已经填好的更高位加上 $1 << k$ 以后不超过 $m$。(也就是你选的数不能超过 $m$)
- 参与位运算后,若初值为 $1$,则结果为 $1$;若初值为 $0$,则结果为 $0$。
如果不满足两个条件,要么会不满足题目条件,要么填 $1$ 不如 $0$ 更优(见结尾补充说明)。这种情况下显然 $0$ 会更好,这样就可以确定初始值得每一位,这样就可以求出答案了。
完整代码,时间复杂度:$O(n\log m)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m, val, ans;
pair<string, int> a[N];
int calc(int bit, int now) {
for (int i = 1; i <= n; i ++ ) {
int x = a[i].second >> bit & 1;
if (a[i].first == "AND") now &= x;
else if (a[i].first == "OR") now |= x;
else now ^= x;
}
return now;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i].first >> a[i].second;
}
for (int i = 29; i >= 0; i -- ) {
int res0 = calc(i, 0);
int res1 = calc(i, 1);
if (val + (1 << i) <= m && res0 < res1)
val += 1 << i, ans += res1 << i;
else
ans += res0 << i;
}
cout << ans << endl;
return 0;
}
补充说明:
倒着枚举的原因:如果从低到高,那么就会出现选择不了更大的数,就会错误。
第一种:$1 \rightarrow 0, 0 \rightarrow 1$:这种就很好理解了对吧,显然填 $0$ 更优。
第二种:$1 \rightarrow 1, 0 \rightarrow 1$:两个填之后都为 $1$,但是填 $0$ 可以更节省数值,为后面提供更多机会,所以填 $0$。
第三种:$1 \rightarrow 0, 0 \rightarrow 0$:两个都为 $0$,但是填 $0$ 可以更节省数值,为后面提供更多机会,所以填 $0$。