CF631A Interview

Blake 是一家名为“Blake Technologies”的大型公司的 CEO。他非常热爱自己的公司，并且认为自己的公司应该成为最好的。因此，每一位候选人都需要通过一道包含以下内容的面试题。 我们定义函数 $f(x,l,r)$ 为整数 $x_l, x_{l+1}, \ldots, x_r$ 的按位或（bitwise OR），这里 $x_i$ 表示数组 $x$ 的第 $i$ 个元素。现在给定长度为 $n$ 的数组 $a$ 和 $b$，请你求出所有 $1 \leq l \leq r \leq n$ 中，$f(a,l,r) + f(b,l,r)$ 的最大值。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 1000$），表示两个数组的长度。 第二行包含 $n$ 个整数 $a_i$（$0 \leq a_i \leq 10^9$）。 第三行包含 $n$ 个整数 $b_i$（$0 \leq b_i \leq 10^9$）。

输出一个整数，表示所有 $1 \leq l \leq r \leq n$ 中 $f(a,l,r) + f(b,l,r)$ 的最大值。

两个非负整数 $a$ 和 $b$ 的按位或是数 $c = a\ \text{OR}\ b$，其二进制表示中，每一位若 $a$ 或 $b$ 中至少有一个在对应位上为 $1$，则 $c$ 的该位也为 $1$。 在第一个样例中，一个最优的答案是 $l=2$ 且 $r=4$，因为 $f(a,2,4) + f(b,2,4) = (2\ \text{OR}\ 4\ \text{OR}\ 3) + (3\ \text{OR}\ 3\ \text{OR}\ 12) = 7 + 15 = 22$。其他能得到最大值的方法还包括选择 $l=1$ 且 $r=4$、$l=1$ 且 $r=5$、$l=2$ 且 $r=4$、$l=2$ 且 $r=5$、$l=3$ 且 $r=4$ 或 $l=3$ 且 $r=5$。 在第二个样例中，最大值在 $l=1$ 且 $r=9$ 时取得。 由 ChatGPT 5 翻译