CF1395C-Boboniu and Bit Operations

2022-03-30 题解

题目大意：给出两个数列a[]和b[]，对于a中的每个元素任取一个b中的元素（可以重复）同它按位与，这些按位与的结果全部按位或之后的最小值为多少。

这题没有从正面求出最小值的方法，注意到a、b中元素的值均不超过 $2^9$ ，所以他们按位或的值也不超过 $2^9$ ，非常小，所以对于 $0$ ~ $2^9$ 的所有整数依次验证是否可以由这两个数列进行操作得到即可。验证一个数x是否能由操作得到非常简单，若x可由操作得到，那么

\forall a \exist b (a \& b|x)=x

#include <bits/stdc++.h>
using namespace std;
int a[205], b[205];
int main()
{
    int n, m, i, j, x;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (i = 1; i <= m; i++)
        scanf("%d", &b[i]);
    for (x = 0;; x++)
    {
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= m; j++)
            {
                if ((a[i] & b[j] | x) == x)
                    break;
            }
            if (j > m)
                break;
        }
        if (i > n)
        {
            printf("%d", x);
            return 0;
        }
    }
}