传送门：http://codeforces.com/contest/879/problem/C
本题是一个位运算问题——位运算的等价变换。
假设位运算符“&”“|”“^”是左结合的，且优先级相同，则一个表达式：“x@a[1]@a[2]@...@a[n]”，等价于“(...((x@a[1])@a[2])...)@a[n]”。其中，“@”为位运算符“&”“|”“^”。
将表达式“x@a[1]@a[2]@...@a[n]”表示为一个简单的等价形式：“((x&a)|b)^c”，即“x&a|b^c”。
限制条件：“(x>=0)&&(x<=0x3ff)”。
一位数的位运算：
“&”: 0&0=0，0&1=0，1&0=0，1&1=1；
“|”: 0|0=0，0|1=1，1|0=1，1|1=1；
“^”: 0^0=0，0^1=1，1^0=1，1^1=0。
将表达式看成一个映射：“f:x->((x&a)|b)^c”。
此映射服从运算规律：“f(x)=x@a[1]@a[2]@...@a[n]”。
则可枚举x，比较x和f(x)的每一位，据此推测a、b、c。
实际上，由于位运算中的每一位是独立的，因此只需测试两个值：0x0(0b00,0000,0000)和0x3ff(0b11,1111,1111B)。之后比较0和f(0x0)的每一位，以及1和f(0x3ff)的每一位。
记映射f可以分解为若干个位（bit）映射，位i的映射为f[i]，则：
若f[i]:0->0,1->0，则f[i]=“&0,|0,^0”，即a[i]=0,b[i]=0,c[i]=0；
若f[i]:0->0,1->1，则f[i]=“&1,|0,^0”，即a[i]=1,b[i]=0,c[i]=0；
若f[i]:0->1,1->0，则f[i]=“&1,|0,^1”，即a[i]=1,b[i]=0,c[i]=1；
若f[i]:0->1,1->1，则f[i]=“&1,|1,^0”，即a[i]=1,b[i]=1,c[i]=0。
于是，对每一位构造a、b、c的对应位即可。
参考程序如下：
#include <stdio.h> int main(void)
{
int n;
int x = , y = 0x3ff;
scanf("%d", &n);
for (int i = ; i < n; i++) {
getchar();
char op = getchar();
int num;
scanf("%d", &num);
switch (op) {
case '&':
x &= num;
y &= num;
break;
case '|':
x |= num;
y |= num;
break;
case '^':
x ^= num;
y ^= num;
break;
default:
break;
}
}
int num_and = , num_or = , num_xor = ;
for (int i = ; i < ; i++) {
int bit = << i;
if ((x & bit)) {
if (y & bit) num_or |= bit;
else num_xor |= bit;
num_and |= bit;
} else {
if (y & bit) num_and |= bit;
}
}
printf("3\n& %d\n| %d\n^ %d\n", num_and, num_or, num_xor);
return ;
}
对于以上位构造法：
若f[i]:0->0,1->0，则f[i]=“&0,|0,^0”，即a[i]=0,b[i]=0,c[i]=0；
若f[i]:0->0,1->1，则f[i]=“&1,|0,^0”，即a[i]=1,b[i]=0,c[i]=0；
若f[i]:0->1,1->0，则f[i]=“&1,|0,^1”，即a[i]=1,b[i]=0,c[i]=1；
若f[i]:0->1,1->1，则f[i]=“&1,|1,^0”，即a[i]=1,b[i]=1,c[i]=0。
可以直接构造a、b、c：
a=f(0x0)|f(0x3ff)；
b=f(0x0)&f(0x3ff)；
c=f(0x0)&(0x3ff^f(0x3ff))。
参考程序如下：
#include <stdio.h> int main(void)
{
int n;
int x = , y = 0x3ff;
scanf("%d", &n);
for (int i = ; i < n; i++) {
getchar();
char op = getchar();
int num;
scanf("%d", &num);
switch (op) {
case '&':
x &= num;
y &= num;
break;
case '|':
x |= num;
y |= num;
break;
case '^':
x ^= num;
y ^= num;
break;
default:
break;
}
}
int num_and = x | y,
num_or = x & y,
num_xor = x & (0x3ff ^ y);
printf("3\n& %d\n| %d\n^ %d\n", num_and, num_or, num_xor);
return ;
}