【比赛记录】 Codeforces Round #682 Div.2

Problems：

#	Name	Submit
A	Specific Tastes of Andre
B	Valerii Against Everyone
C	Engineer Artem
D	Powerful Ksenia
E	Yurii Can Do Everything
F	Olha and Igor

题解：

A：Specific Tastes of Andre

全部输出相同的数即可。

B：Valerii Against Everyone

猜测当且仅当 \(b\) 数组中存在两个相同的数，存在答案。
充分性容易理解，通过 \(\sum\limits_{i=l}^r a_i\) 的二进制表示可以证明必要性。

C：Engineer Artem

\(+1\) 可以改变一个数的奇偶性，而奇偶性不同的数一定不同。
故只需构造奇偶相互交替的矩阵即可。

D：Powerful Ksenia

性质：

• 一次操作可以把三个数变为相同的一个数。
• 将 \(a,a,b\) 异或起来可以得到 \(b,b,b\) 。
• 每次操作前后整个序列的异或和不变。

 
对于 \(n\) 是奇数的情况，容易通过将 \(a_{2k-1},a_{2k}\) 与 \(a_n\) 异或，
将序列变为若干段长度为 \(2\) 的相同的数，以及最后一段长度为 \(3\) 的相同的数，
最后再来一遍将 \(a_{2k-1},a_{2k}\) 与 \(a_n\) 异或的操作，操作数 \(n-2\) 。
对于 \(n\) 是偶数的情况，根据性质可知：若有解，则整个序列异或和为 \(0\) 。
那么考虑将最后一个数单独拎出来，对前 \(n-1\) 个数像奇数一样操作。
因为整个序列异或和为 \(0\) ，操作完后前 \(n-1\) 个相等的数一定与第 \(n\) 个数相等。

E：Yurii Can Do Everything

设 \(a_l\) 的二进制下的最高位为 \(k\) ，那么 \(a_l \oplus a_r <2^{k+1}\) 。
那么对于一个 \(l\) ，只需要枚举到 \(\sum\limits_{i=j+1}^{r-1}a_i>2^{k+1}\) 处。
现证明该复杂度为 \(\text{O}(n\log a_i)\) 。
对于若干个最高位为 \(k\) 的 \(a_{b_1},a_{b_2},\ldots,a_{b_j}\) 。
对于每一个 \(l=b_i\) ，\(r\) 最远只能取到 \(b_{i+2}\) ，
因为此时最高位均为 \(k\) ，相加进位，大于等于 \(2^{k+1}\) ，继续往后不载满足条件。
一共枚举 \(\sum\limits_{i=1}^j (b_{i+2}-b_i)\) 个位置，上界为 \(2n\) ，
故每一位复杂度为线性，总复杂度为 \(\text{O}(n\log a_i)\) 。

F：Olha and Igor

交互题，不会，爪巴。