题解 CF631A 【Interview】

Solution

讲白了，就是让你求 ${f(A,l,r) + f(B,l,r)}_{\max}$， 其中 $f(A,l,r) = A_l \text{ or } A_{l+1} \text{ or} \cdots \text{ or } A_r$。

结论楼上的都说了，这里只是来证明一下。

证明：
设这两个数为 $a$ 和 $b$ , $c = a \text{ or } b$
因为 $a$ 和 $b$ 化为二进制之后由 $0$ 和 $1$ 构成
又 $0\text{ or }0 = 1$,$0\text{ or }1 = 1$,$1\text{ or }1 = 1$
所以，对于 $a$ 和 $b$ 的每一位来说，进行 or 运算之后所得的结果都大于等于原来的数字
所以，$a\text{ or }b \le c$，即任意两个数字的或值大于等于两数
命题得证。

那么我们就把所有的数字都拿来用，这样就不用担心会小了。

Code

#include <bits/stdc++.h>
using namespace std;

inline void read(int &x) {
    int f = 1; x = 0;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    x = x * f;
}

int ans,n,x,m;

int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        read(x); m = m | x;
    }
    ans += m; m = 0;
    for(int i = 1;i <= n;i++) {
        read(x); m = m | x;
    }
    ans += m;
    printf("%d\n",ans);
    return 0;
}