102916: [Atcoder]ABC291 G - OR Sum
Description
Score : $600$ points
Problem Statement
There are length-$N$ sequences $A=(A_0,A_1,\ldots,A_{N-1})$ and $B=(B_0,B_1,\ldots,B_{N-1})$.
Takahashi may perform the following operation on $A$ any number of times (possibly zero):
- apply a left cyclic shift to the sequence $A$. In other words, replace $A$ with $A'$ defined by $A'_i=A_{(i+1)\% N}$, where $x\% N$ denotes the remainder when $x$ is divided by $N$.
Takahashi's objective is to maximize $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)$, where $x|y$ denotes the bitwise logical sum (bitwise OR) of $x$ and $y$.
Find the maximum possible $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)$.
What is the bitwise logical sum (bitwise OR)?
The logical sum (or the OR operation) is an operation on two one-bit integers ($0$ or $1$) defined by the table below.The bitwise logical sum (bitwise OR) is an operation of applying the logical sum bitwise.
| $x$ | $y$ | $x|y$ |
| $0$ | $0$ | $0$ |
| $0$ | $1$ | $1$ |
| $1$ | $0$ | $1$ |
| $1$ | $1$ | $1$ |
The logical sum yields $1$ if at least one of the bits $x$ and $y$ is $1$. Conversely, it yields $0$ only if both of them are $0$.
Example
0110 | 0101 = 0111
Constraints
- $2 \leq N \leq 5\times 10^5$
- $0\leq A_i,B_i \leq 31$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$
$A_0$ $A_1$ $\ldots$ $A_{N-1}$
$B_0$ $B_1$ $\ldots$ $B_{N-1}$
Output
Print the maximum possible $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)$.
Sample Input 1
3 0 1 3 0 2 3
Sample Output 1
8
If Takahashi does not perform the operation, $A$ remains $(0,1,3)$, and we have $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(0|0)+(1|2)+(3|3)=0+3+3=6$;
if he performs the operation once, making $A=(1,3,0)$, we have $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(1|0)+(3|2)+(0|3)=1+3+3=7$; and
if he performs the operation twice, making $A=(3,0,1)$, we have $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(3|0)+(0|2)+(1|3)=3+2+3=8$.
If he performs the operation three or more times, $A$ becomes one of the sequences above, so the maximum possible $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)$ is $8$, which should be printed.
Sample Input 2
5 1 6 1 4 3 0 6 4 0 1
Sample Output 2
23
The value is maximized if he performs the operation three times, making $A=(4,3,1,6,1)$,
where $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(4|0)+(3|6)+(1|4)+(6|0)+(1|1)=4+7+5+6+1=23$.
Input
题意翻译
给定两个长为 $n$ 的序列 $A_i$， $B_i$，重新排列 $A_i$ 使得 $ \displaystyle\sum_{i=0}^{N-1}\ (A_i|B_i) $ 最大。 $2 \le n \le 10^5$ $0 \le A_i,B_i \le 31$Output
问题描述
长度为$N$的序列$A=(A_0,A_1,\ldots,A_{N-1})$和$B=(B_0,B_1,\ldots,B_{N-1})$。
- 对序列$A$执行任意次数（可能为零次）的左循环移位操作。换句话说，将$A$替换为$A'$，其中$A'_i=A_{(i+1)\% N}$，其中$x\% N$表示$x$除以$N$的余数。
Takahashi的目标是最大化$\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)$，其中$x|y$表示位逻辑和（位或）。
找到最大的可能的$\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)$。
什么是位逻辑和（位或）？
位逻辑和（或位或操作）是对两个一位整数（0或1）定义的操作，如下表所示。 位逻辑和（位或）是对位进行逻辑和应用的操作。| $x$ | $y$ | $x|y$ |
| $0$ | $0$ | $0$ |
| $0$ | $1$ | $1$ |
| $1$ | $0$ | $1$ |
| $1$ | $1$ | $1$ |
当位$x$和$y$中的至少一个为1时，逻辑和产生1。相反，只有当它们都为0时，它才会产生0。
示例
0110 | 0101 = 0111
约束条件
- $2 \leq N \leq 5\times 10^5$
- $0\leq A_i,B_i \leq 31$
- 输入中的所有值都是整数。
输入
输入以标准输入的以下格式给出：
$N$
$A_0$ $A_1$ $\ldots$ $A_{N-1}$
$B_0$ $B_1$ $\ldots$ $B_{N-1}$
输出
打印最大的可能的$\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)$。
样例输入1
3 0 1 3 0 2 3
样例输出1
8
如果Takahashi不执行操作，$A$保持为$(0,1,3)$，我们有$\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(0|0)+(1|2)+(3|3)=0+3+3=6$； 如果他执行一次操作，使$A=(1,3,0)$，我们有$\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(1|0)+(3|2)+(0|3)=1+3+3=7$；并且 如果他执行两次操作，使$A=(3,0,1)$，我们有$\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(3|0)+(0|2)+(1|3)=3+2+3=8$。 如果他执行三次或更多次操作，$A$将变为上述序列之一，因此最大的可能的$\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)$为$8$，应该打印出来。
样例输入2
5 1 6 1 4 3 0 6 4 0 1
样例输出2
23
如果他执行三次操作，使$A=(4,3,1,6,1)$，其中$\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(4|0)+(3|6)+(1|4)+(6|0)+(1|1)=4+7+5+6+1=23$，则值最大。