CF1451E1&2 Bitwise Queries (Easy&Hard Version) 做题记录

Ridbit 有一个隐藏的长度为 $n$ 的数组 $a$，Ashish 要去猜，$n$ 是 $2$ 的整数次幂。Ridbit 允许 Ashish 提出三种不同类型的查询。它们分别是：

• AND $i,j$：求元素 $a_i$ 和 $a_j$ 每一位的 $and$（$1≤i$,$j≤n$,$i≠j$）

• OR $i,j$：求元素 $a_i$ 和 $a_j$ 每一位的 $or$（$1≤i$,$j≤n$,$i≠j$）

• XOR $i,j$：求元素 $a_i$ 和 $a_j$ 每一位的 $xor$（$1≤i$,$j≤n$,$i≠j$）

限制：

• Ashish 最多可以询问 $n + 1$ 次（Hard Version）$n+2$ 次（Easy Version）。
• $0 \le a_i \le n - 2$。

$1\le n\le 2^{16}$。

Easy Version

发现求出 $a_1$ 就能通过异或求出剩下的数，那么考虑求 $a_1$。

先用两次操作求出 $a_1\oplus a_2=xor12$ 和 $a_1\&a_2=and12$。显然对于某一个二进制位 $i$，若 $and12$ 的第 $i$ 位为 $1$，$a_1$ 和 $a_2$ 的第 $i$ 位也肯定为 $1$；若 $xor12$ 的第 $i$ 位为 $1$，$a_1$ 和 $a_2$ 之间肯定有且仅有 一个数第 $i$ 位为 $1$。

考虑确定 $xor12$ 二进制中的 $1$ 哪些属于 $a_1$，哪些属于 $a_2$。显然可以再用两次操作求出 $a_2|a_3=or23$ 和 $a_1\&a_3=and13$。 对于某一个满足 $xor12$ 的第 $i$ 位为 $1$ 的二进制位 $i$，若 $or23$ 的第 $i$ 位为 $0$，那么这个 $1$ 显然属于 $a_1$；否则若 $and13$ 的第 $i$ 位为 $1$ 那么这一个 $1$ 属于 $a_1$，否则这个 $1$ 属于 $a_2$。

这样我们就用 $4$ 次操作求出了 $a_1$ 和 $a_2$，接下来用 $n-2$ 次操作即可求出整个序列 $a$，总共花费了 $n+2$ 次操作。

Hard Version

先对 $2\le i\le n$ 的 $i$ 求出 $b_i=a_1\oplus a_i$，耗费 $n-1$ 次操作。

然后考虑用 $2$ 次操作求出 $a_1$：

• 显然若 $b$ 中有相同的元素或者存在 $b_i=0$ 那么可以直接花费 $1$ 次操作求出重复的元素，然后直接异或上 $b_i$ 求出 $a_1$。
• 否则此时 $a$ 中元素两两不同，那么显然一定有且仅有一个 $b_i=1$，也有且仅有一个 $b_j=2$，那么找出 $i,j$，询问 $a_1\& a_i$ 即可确定 $a_1$ 二进制中除了最后一位的其它位，询问 $a_1\&a_j$ 即可确定 $a_1$ 二进制中的最后一位。