include [HTML_REMOVED]
// 二进制的常识,对于这道题
// 因为是位运算,在二进制下,所以最后的答案的每一位上要么是0要么是1,也就是无论怎么运算都是只有两种情况
// 注意到 按位与、按位或、按位异或 共有的一个性质:每次运算只有关当前两位上的数,不影响其它位上的数
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;
// x 最终只有两个值 0 1
}
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,要看填完后对答案的影响来填
{
// 如果高位可以填上 1 ,那么这一位就会使这个最后的结果最大
bool x = calc(0, i), y = calc(1, i); // 先分别处理出该位填 0 的结果和该位填 1 的结果
if (x >= y) ans|= x << i;
// 如果该位填 1 并不比该位填 0 更优,那么为了让剩下能填的数更大,也就是减去当前位的数,在该位填 0
// calc(0, i)可能返回1,而calc(1, i)经过算后反而变成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;
}