比赛：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

n=2n-n

，因此

n

是确定不变的。

那么按照

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

文章操作

CF2130 Div.2

A

B

C

D

E1

相关推荐

评论

比赛：CF2130 Div.2