传送门
思路
按位贪心。但是我太弱了，明明可以
O(n)
O
(
n
)
预处理，我却只会
O(32n)
O
(
32
n
)
，唉，我太弱啦！
参考代码
懒得改了。还是留意一下能够预处理的内容吧。
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
}
const int maxn = int(1e5) + 5;
int n, m;
int ans;
struct Instruction
{
enum
{
AND, OR, XOR
};
int type;
int val;
void read()
{
char str[10];
scanf("%s", str);
if (str[0] == 'A')
type = AND;
else if (str[0] == 'O')
type = OR;
else if (str[0] == 'X')
type = XOR;
val = readIn();
}
int calc(int input)
{
if (type == AND)
return input & val;
else if (type == OR)
return input | val;
else
return input ^ val;
}
} ins[maxn];
int calc(int input)
{
for (int i = 1; i <= n; i++)
input = ins[i].calc(input);
return input;
}
void run()
{
n = readIn();
m = readIn();
for (int i = 1; i <= n; i++)
ins[i].read();
int through = calc(0);
for (int i = 30; ~i; i--)
{
if ((ans | (1 << i)) > m)
continue;
int v = calc(1 << i);
if ((v & (1 << i)) > (through & (1 << i)))
ans |= 1 << i;
}
printOut(calc(ans));
}
int main()
{
run();
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
