比赛：CF2130 Div.2

· · 题解

CF2130 Div.2

A

把所有 0 全部用 \mathrm{mex}，剩下全部用 \mathrm{sum} 即可。

B

分讨题。

首先每个格子会走至少一遍，那么先累加上，记为 x。判掉 x>s 的情况。如果有 01 的结构，Alice 可以重复增加 1。如果没有，那么一定同时有 02 和 12 的结构，02 可以同时增加 2，12 可以增加 3 并改变奇偶性。分讨即可。

C

发现如果图中存在环，那么断掉任意一条边，f(S) 不变，g(S) 变小，答案变大。因此只需要求图上任意一个生成森林即可。

D

那么按照 $p_i$ 从大到小往序列里填数。发现对于 $i<j$，$2n-i>2n-j>j$ 且 $i<j<2n-j$，因此不管已经填过的数如何选择，都不会影响后续填数，因为后续仍然可以随意控制它们的相对大小。贪心即可。 ### E1 想到二分之前想了一段时间错误的方向，但是发现二分之后很快就想到正解了。 考虑这个 $550$ 次，合理猜测是每次询问确定两个位置，然后还有 $<50$ 次额外操作。（一开始也感觉这个 $50$ 很像 $\log$）。 题目保证一定存在至少一个 `(` 和 `)`，因此一开始直接询问 $f([1,n])$，若答案为 $0$，则说明序列一定为 `)...)(...(`，二分找到分界点即可。 否则，二分确定第一个前缀答案为 $0$ 的位置，即找到最小的 $p$，使得 $f([1,p])=0$，那么 $[1,p]$ 一定形如 `)...)(...(`，因此也是二分确定 $[1,p]$ 的答案。 然后 $p+1$ 一定是 `)`，于是我们从 $p+2$ 开始两个两个往后确定。 设 $x$ 初始为 $p+1$，$a$ 括号序列，$y=x+1$，$z=x+2$。 - 若 $a_x=$ `)`，询问 $k=f(z,x,x,z,y,z,y,z,y)$， - 若 $k=0$，则 $a_y=$ `)`，$a_z=$ `)`。 - 若 $k=7$，则 $a_y=$ `)`，$a_z=$ `(`。 - 若 $k=1$，则 $a_y=$ `(`，$a_z=$ `(`。 - 若 $k=3$，则 $a_y=$ `(`，$a_z=$ `)`。 - 若 $a_x=$ `(`，询问 $k=f(z,y,z,y,z,y,x,x,z)$， - 若 $k=1$，则 $a_y=$ `)`，$a_z=$ `)`。 - 若 $k=6$，则 $a_y=$ `)`，$a_z=$ `(`。 - 若 $k=0$，则 $a_y=$ `(`，$a_z=$ `(`。 - 若 $k=4$，则 $a_y=$ `(`，$a_z=$ `)`。 - 令 $x=x+2$，不断向后扩展。 询问次数为：$2\log n+\frac{n}{2}$。 [Code](https://codeforces.com/contest/2130/submission/331911198)