题解 CF1395C 【Boboniu and Bit Operations】
绝顶我为峰
2020-08-13 20:03:27
由于 $n,m\leq200$，几乎允许我们做想做的任何事。所以我们可以直接暴力把每一个 $a_i\&b_j$ 求出来。
由于高位选 $0$ 一定比低位选 $0$ 更优，考虑贪心。
或运算的性质是所有参与运算的数的二进制当前位中全部是 $0$ 则答案是 $0$，否则答案是 $1$。
那么我们对于每一位，遍历数组 $a$，对于每个 $a_i$ 查找是否有一个 $a_i\&b_j$ 的当前位是 $0$，如果没有，则当前位只能为 $1$，计算贡献。
如果每一个 $i$ 当前位都可以是 $0$，根据贪心思想，当前位必是 $0$，这个时候不需要计算贡献，而是重新遍历所有的 $a_i\&b_j$，把当前位是 $1$ 的答案删去即可。
代码很显然了。
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[201],b[201],num[201][201],ans,maxn;
int main()
{
scanf("%d%d",&n,&m);
for(register int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
maxn=max(maxn,a[i]);
}
for(register int i=1;i<=m;++i)
{
scanf("%d",&b[i]);
maxn=max(maxn,b[i]);
for(register int j=1;j<=n;++j)
num[j][i]=a[j]&b[i];
}
for(register int i=10;i>=0;--i)
{
if((1<<i)>maxn)
continue;
bool flag=1;
for(register int j=1;j<=n;++j)
{
bool tag=0;
for(register int k=1;k<=m;++k)
if(num[j][k]!=-1&&!((num[j][k]>>i)&1))
{
tag=1;
break;
}
if(!tag)
{
flag=0;
break;
}
}
if(!flag)
ans+=1<<i;
else
for(register int j=1;j<=n;++j)
for(register int k=1;k<=m;++k)
if((num[j][k]>>i)&1)
num[j][k]=-1;
}
printf("%d\n",ans);
return 0;
}
```