嘟嘟嘟
这题算是NOI系列罕见的水题吧。
按位考虑，观察到经过每一个门无非就是4种情况：0变0,0变1,1变0,1变1。更概括的来说，就是两种情况：这一位变成1,和这一位变成0。
所以从高位到低位贪心即可。
变成1，如果满足(m)的范围，就选；变成0，如果1和0都变成了0，那么我们自然选0，这样对于低位的数就不受(m)的限制了。
时间复杂度(O(nlogm))。
求稳，就先把三道题暴力写完，回头再写正解。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<assert.h>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
In ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen("sleep.in", "r", stdin);
freopen("sleep.out", "w", stdout);
#endif
}
char s[10];
int n, m, TT[26];
struct Node
{
int op, x;
}dr[maxn];
In int solve0(int ret)
{
for(int i = 1; i <= n; ++i)
{
if(!dr[i].op) ret &= dr[i].x;
else if(dr[i].op == 1) ret |= dr[i].x;
else ret ^= dr[i].x;
}
return ret;
}
In void work0()
{
int ans = 0;
for(int i = 0; i <= m; ++i) ans = max(ans, solve0(i));
write(ans), enter;
}
int pos0 = 0;
In bool check_and0()
{
for(int i = 1; i <= n; ++i)
if(!dr[i].op && !dr[i].x) {pos0 = i; return 1;}
return 0;
}
In void work1()
{
int ans = 0;
for(int i = pos0 + 1; i <= n; ++i)
{
if(!dr[i].op) ans &= dr[i].x;
else if(dr[i].op == 1) ans |= dr[i].x;
else ans ^= dr[i].x;
}
write(ans), enter;
}
In int calc(int x, int pos)
{
for(int i = 1; i <= n; ++i)
{
int tp = (dr[i].x >> pos) & 1;
if(!dr[i].op) x &= tp;
else if(dr[i].op == 1) x |= tp;
else x ^= tp;
}
return x;
}
int main()
{
//MYFILE();
TT['A'] = 0, TT['O'] = 1, TT['X'] = 2;
n = read(), m = read();
for(int i = 1; i <= n; ++i)
{
scanf("%s", s); int x = read();
dr[i] = (Node){TT[s[0]], x};
}
if(n <= 10000 && m <= 10000) {work0(); return 0;}
if(check_and0()) {work1(); return 0;}
int _Max = 1, ans = 0;
for(int i = 30; i >= 0; --i)
{
if(_Max)
{
int x = (m >> i) & 1;
if(!x) ans += (calc(x, i) << i);
else
{
int tp1 = calc(1, i), tp2 = calc(0, i);
ans += (max(tp1, tp2) << i);
if(tp1 <= tp2) _Max = 0;
}
}
else
{
int tp1 = calc(1, i), tp2 = calc(0, i);
ans += (max(tp1, tp2) << i);
}
}
write(ans), enter;
return 0;
}
/*
5 20
XOR 3
OR 4342
AND 0
OR 4
XOR 10
*/