Steven_MengのBlog

传送门

首先,我们发现位运算和十进制的加减乘除不一样,位运算对于每一位都是独立的,而加减乘除会产生进位,在一位上的操作会影响另一位。

我们可以这样理解,对于一大堆不知道是蜃么奇奇怪怪的$And$,$Or$,$Xor$ ,我们可以算出来一个函数$f(x,pos)$(其中$x=0,1$且$f(x,pos)=0,1$),使得原数上$pos$位置的$x$,经过操作之后对应位置上一定是$f(x)$。

考虑如何计算$f(x)$,发现只要搞一个全是$1$的数和一个全是$0$的数,按照题目意思给他操作一遍,操作完的数对应到$pos$位上,一定是$f(1,pos)$和$f(0,pos)$(因为位运算每一位都是独立的)

算出来$f(x)$就好做了,我们考虑贪心,

可以由$0$变成$1$,那么肯定要变

可以由$1$变成$1$,也要变

可以由$0$变成$0$,不用变(因为$0$已经是最小的可能数了)

可以由$1$变成$0$,这样一搞反而亏本了,肯定不用变

详细细节见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define MAXM 30
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
inline char gc(){
char ch=getchar();
while (ch!='A'&&ch!='O'&&ch!='X') ch=getchar();
return ch;
}
int main(){
int n=read(),m=read();
int f1=0x7fffffff,f0=0;
for (register int i=1;i<=n;++i){
char opr=gc();
int x=read();
if (opr=='A') f0&=x,f1&=x;
if (opr=='O') f0|=x,f1|=x;
if (opr=='X') f0^=x,f1^=x;
}
int ans=0;
for (register int i=MAXM;i>=0;--i){
if (f0&(1<<i)){
ans|=(1<<i);
}
else if ((1<<i)<=m&&(f1&(1<<i))){
ans|=(1<<i);
m-=(1<<i);
}
}
printf("%d\n",ans);
}

 评论