CF1556D Take a Guess 做题记录

这是一道交互题，给定两个正整数 $n,k$，你需要通过 $\leq 2n$ 次询问猜出长度为 $n$ 的序列 $\{a_i\}$ 中的第 $k$ 小值。

询问分为两种类型：

1. or i j，交互器会返回 $a_i \operatorname{or}a_j$ 的值。
2. and i j，交互器会返回 $a_i\operatorname{and}a_j$ 的值。

其中需要满足 $1\leq i,j\leq n$ 且 $i\not = j$。

最后你需要输出 finish res，其中 $res$ 表示你的答案。

$3\leq n \leq 10^4,1\leq k\leq n,0\leq a_i\leq 10^9$。

首先有个结论：$x+y=(x\operatorname{or} y)+(x\operatorname{and}y)$。

证明可以考虑每一位的贡献。

那么用 $2n-2$ 次询问求出 $a_1+a_i$，用两次询问求出 $a_i+a_j$ 即可解方程得到 $a_1$，进而得出序列 $a$。