ACWING 998 起床困难综合症
题意
给定一个初始范围$[0,m]$,要求选择一范围内整数$x_0$,使其经过接下来的一串由$or,and和xor$构成的操作后,得到最大值。
思路
- 对于这三种操作,位与位之间互不干扰,所以可以逐位考虑。
- 我们希望最后得到的$ans$尽可能大,也就是说在$x_0$的基础上,我们希望经过运算得到更多的$1$。
- $x_0$不能大于$m$
对于2,我们又有如下考虑
如果第$k$位应该填1,我们应该保证对于每一位,以下两条规则都成立。
- 若位上的初值为1,经过这一串运算之后,它应仍是1。
- 若位上的初值为0,经过这一串运算之后,它应仍是0。
不妨考虑若这两条规则不成立时的情况。
- 若位上的初值为1,经运算后它变成了0,我们在这位上填1要么毫无用处($1\rightarrow0$,$0\rightarrow0$),要么减小了$ans$($1\rightarrow0$,$0\rightarrow1$)。
- 若位上的初值为0,经运算后它变成了1,我们在这位上填1要么毫无用处($0\rightarrow1$,$1\rightarrow1$),要么减小了$ans$($0\rightarrow1$,$1\rightarrow0$)。
由此,得到代码
#include <iostream>
using namespace std;
const int N = 100010;
typedef pair<string, int> PSI;
PSI a[N];
int n, m;
int calc(int bit, int now)
{
for (int i = 0; i < n; i++)
{
int x = a[i].second >> bit & 1;
if (a[i].first == "AND")
now &= x; // AND
else if (a[i].first == "OR")
now |= x; // OR
else
now ^= x; // XOR
}
return now;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
string op;
int x;
cin >> op >> x;
a[i] = {op, x};
}
int val = 0, ans = 0; // val用于确保不越过m的范围
for (int bit = 29; bit >= 0; bit--)
{ // 逐位考虑
int res0 = calc(bit, 0);
int res1 = calc(bit, 1);
if (val + (1 << bit) <= m && res0 < res1)
{
val += 1 << bit, ans += res1 << bit;
}
else
{
ans += res0 << bit;
}
}
cout << ans << endl;
return 0;
}