link

正文

由于涉及到位运算，因此复杂度应与 n 和 $\log_2 m$ 有关。

二进制的特点为 $\wedge, \vee, \oplus$ 等运算不进位，因此每一位都是独立的。

令初始的攻击力的第 i 位为 $atk_i$， 考虑对每一位进行操作：

对 $atk_i$ 为 0 和 1 的情况分别进行模拟，得到 $res_0$ 和 $res_1$。此时，题目中的 m 就起到了限制作用：如果 $atk_i$ 能取 1，则也能取 0，故答案为 $\min \{res_0, res_1\}$；否则答案为 $res_0$。

那么如何判断 $atk_i$ 能否取 1 呢？

—— 看 $\log m$ 是否不小于 $i$ 即可，原因显然。

#include <bits/stdc++.h>

using ll = long long;

auto main()->int {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    int n;
    ll m;
    std::cin >> n >> m;

    std::vector<std::string> op(n + 1);
    std::vector<std::bitset<30>> t(n + 1);

    for (int i = 1; i <= n; ++i) {
        int x;
        std::cin >> op[i] >> x;
        t[i] = x;
    }

    std::bitset<30> ans(0);
    int k = std::__lg(m);
    for (int bit = 29; bit >= 0; --bit) {
        int res0 = 0, res1 = 1;
        for (int i = 1; i <= n; ++i) {
            if (op[i] == "AND") {
                res0 = res0 & t[i][bit];
                res1 = res1 & t[i][bit];
            } else if (op[i] == "OR") {
                res0 = res0 | t[i][bit];
                res1 = res1 | t[i][bit];
            } else {
                res0 = res0 ^ t[i][bit];
                res1 = res1 ^ t[i][bit];
            }
        }

        if (bit <= k) {
            ans[bit] = std::max(res0, res1);
        } else {
            ans[bit] = res0;
        }
    }

    std::cout << ans.to_ulong();
    
    return 0;
}

思考题

数据范围同原题，题目改为求能达到最大值的方案数。

if (bit <= k && res1 == res2) { 
    ans *= 2; 
}

**45min **$\textbf{\textcolor{#37A01D}{+}}$(Luogu) $\textbf{\textcolor{#37A01D}{+5}}$(Nowcoder)