じゅぴろの日記(⋈◍＞◡＜◍)。✧♡

Codeforces Round #685 (Div. 2) - E1. Bitwise Queries (Easy Version)

問題リンク

解説

重要な事実として

$a+b = a\ \mathrm{xor} \ b + 2(a\ \mathrm{and}\ b)$

が成り立ちます。

よって、

$a _ {0} \ \mathrm{ xor }\ a _ {2} = (a _{0} \ \mathrm{xor} \ a _ {1} )\ \mathrm{xor}\ (a _ {1} \ \mathrm{xor}\ a _ {2})$

に気づくと、

$a _ 0 + a _ 1, \ a _ 1 + a _ 2 , \ a _ 0 + a _ 2$

が5クエリで求まるので、

$a _ 0 , \ a _ 1 , \ a _ 2$

が5クエリで求まります。

あとは残りの $n - 3$ クエリは $a _ 0$ とのxorをとればそれぞれ1クエリでわかるのでこの問題は解けました

提出コード