题目描述

这就不说原题目描述了，又长又不好懂
题意：给定 $n, m$ 以及 $n$ 个数和该数所对应的运算，其中运算有 与、或、异或 三种，问在所有不大于 $m$ 的非负整数中，对给定的 $n$ 个数都按该数所对应的运算运算一遍后，能得到得最大的值是多少。

• AND 表示按位与，OR 表示按位或，XOR 表示按位异或

输入样例：

3 10
AND 5
OR 6
XOR 7

输出样例：

1

算法

(按位枚举) $\mathcal O(n \log m)$

注意到 按位与、按位或、按位异或 共有的一个性质：每次运算只有关该位上的数，不影响其它位上的数
所以我们可以像最大异或对这题一样，从高位到低位来确定数的每一位。
如果该位可以填 $u$，并且填 $u$ 之后答案的该位是 $1$，那么在该位填 $u$，否则填 $!u$
那么如何判断该位能填几呢？

• 如果该位填 $1$ 后，所得到的数大于 $m$，那么该位填 $!u$
• 否则如果该位填 $1$ 后，所得到的数对 $n$ 个数都运算之后，结果小于等于该位填 $0$ 后得到的结果，那么为了让剩下能填的数更大，该位填 $0$
• 否则该位填 $1$

由于我们只需要得到填出来的数对所有数运算后的结果，而并不需要输出填出来的数，所以在写代码的时候并不需要真正的把数填出来，只需要确定是否能将答案的该位填成 $1$ 即可

时间复杂度

一共要判断 $\log m$ 次，每次判断是 $\mathcal O(n)$ 的，所以总的时间复杂度是 $\mathcal O(n \log m)$

参考文献

C++ 代码

#include <stdio.h>

const int N = 100005;

int n, m;             // n, m 即题目描述中 n, m
int ans;              // ans 存我们能得到的最大的答案
int t[N];             // t 存输入的 n 个数
short op[N];          // op 存 n 个数对应的操作，1 表示按位或，2 表示按位异或，3 表示与
char str[4];          // str 用于读入操作

bool calc(bool x, int j)                         // calc 用于计算 x 经过所有数的第 j 位操作后所得到的结果
{
    for (int i = 0; i < n; i ++ )                // 从 0 到 n 枚举所有读入的数与其对应操作
        if (op[i] == 1) x |= t[i] >> j & 1;      // 如果 op[i] 为 1，说明该数所对应的运算为按位或
        else if (op[i] == 2) x ^= t[i] >> j & 1; // 如果 op[i] 为 2，说明该数所对应的运算为按位异或
        else    x &= t[i] >> j & 1;              // 如果 op[i] 为 3，说明该数所对应的运算为按位与
    return x;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        scanf("\n%s %d", str, t + i);
        if (*str == 'O') op[i] = 1;              // 如果该操作为 OR ，那么 op[i] 制为 1
        else if (*str == 'X') op[i] = 2;         // 如果该操作为 XOR，那么 op[i] 制为 2
        else    op[i] = 3;                       // 否则该操作为 AND，那么 op[i] 制为 3
    }

    for (int i = 29; ~i; i -- )                  // 因为本题中 m 最大是 10 ^ 9，log2(10 ^ 9) = 3log2(10 ^ 3) < 3 * 10 = 30，所以每次 i 从 29 往后枚举就可以了
        if (1 << i <= m)                         // 如果填 1 后小于等于 m，要看填完后对答案的影响来填
        {
            bool x = calc(0, i), y = calc(1, i); // 先分别处理出该位填 0 的结果和该位填 1 的结果
            if (x >= y) ans|= x << i;            // 如果该位填 1 并不比该位填 0 更优，那么为了让剩下能填的数更大，在该位填 0
            else ans |= y << i, m -= 1 << i;     // 否则在该位填 1，填完后让 m 减去该位填 1 的结果，这样在后面填数的时候只用考虑是否大于 m 就可以了
        }
        else ans |= calc(0, i) << i;             // 否则该位只能填 0,

    printf("%d\n", ans);
    return 0;
}