题目描述

一个 $\operatorname{boss}$ 的防御战线由 $n$ 扇防御门组成，其中第 $i$ 扇防御门的属性包括一个运算 $op_i$ 和一个参数 $t_i$，运算一定是 $\operatorname{OR、XOR、AND}$ 中的一种，参数是非负整数。若在未通过这扇防御门时攻击力为 $x$，则通过这扇防御门后攻击力将变为 $x \ op_i \ t_i$。最终 $\operatorname{boss}$ 受到的伤害为玩家的初始攻击力 $x_0$ 依次经过所有 $n$ 扇防御门后得到的攻击力。由于水平有限，玩家的初始攻击力只能为 $[0,m]$ 之间的一个整数。玩家希望通过选择合适的初始攻击力，使他的攻击能造成最大伤害，求这个伤害值。
数据范围：$n \le 10^5，m,t_i \le 10^9$。

样例

输入：

3 10
AND 5
OR 6
XOR 7

输出：

1

算法

(位运算)

本题是让我们选择 $[0,m]$ 之间的一个整数 $x_0$，经过给定的 $n$ 次位运算，使结果 $ans$ 最大。
位运算的主要特点之一是 在二进制表示下不进位。正因如此，在 $x_0$ 可以任意选择的情况下，参与位运算的各个位（$\operatorname{bit}$）之间是独立无关的。换言之，对于任意的 $k(0 \le k < 30)$，“$ans$ 的第 $k$ 位是几”只与“$x_0$ 的第 $k$ 位是几”有关，与其他位无关。
所以我们可以从高位到低位，依次考虑 $x_0$ 的每一位填 $0$ 还是填 $1$。
$x_0$ 的第 $k$ 位应该填 $1$，当且仅当同时满足下列两个条件。

1. 已经填好的更高位构成的数值加上 $1 << k$ 以后不超过 $m$。
2. 用每个参数的第 $k$ 位参与位运算。若初值为 $1$，则 $n$ 次位运算后结果为 $1$；若初值为 $0$，则 $n$ 次位运算后结果为 $0$。

如果不满足上述条件，要么填 $1$ 会超过 $m$ 的范围，要么填 $1$ 不如填 $0$ 更优。这种情况下令 $x_0$ 的第 $k$ 位为 $0$ 显然更好。确定 $x_0$ 的每一个位以后，自然可以得到 $ans$ 的值。

提醒：一些运算符优先级从高到低的顺序如下表所示。最需要注意的地方是：大小关系比较的符号优先于“位于”“异或”“位或”运算。在程序实现时，如果不确定优先级，建议加括号保证运算顺序正确性。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

pair<string, int> a[100005];
int n, m, x, val, ans;
char str[5];

int calc(int bit, int now)
{
    // 用参数的第 bit 位进行 n 次运算
    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 >> str >> x;
        a[i] = make_pair(str, x);
    }
    for (int bit = 29; bit >= 0; bit --)
    {
        int res0 = calc(bit, 0), res1 = calc(bit, 1);
        if (val + (1 << bit) <= m && res0 < res1)
        {
            val += 1 << bit;
            ans += res1 << bit;
        }
        else
            ans += res0 << bit;
    }
    cout << ans << '\n';
    return 0;
}