CF R864 div2

发布时间 2023-04-12 20:12:15作者: P32sx

A

 发现最劣的方案就是把其中一个围起来,答案为 \(4\),当 \(x=1/x=n/y=1/y=m\) 时答案有可能为 \(2/3\)
分类讨论即可

B

 要将原图形变为中心对称,若\((x,y)!=(n-x+1,n-y+1)\)我们必须操作,若步数有剩,剩余步数是偶数时对一个方块一直操作即可;剩余步数为奇数时,我们还需判断\(n\)的奇偶性,奇数时依旧合法(对中央的方块操作即可)

C

 这题策略本身不难,交互题。我们先询问 \((1,1)\),我们可以计算出国王的 \(x/y\)
我们再询问 \((t+1,t+1)\)\(t\) 为交互所得答案。
分类讨论可以得出答案。

D

 我们分析旋转后哪些变量会改变,发现只要确定新的儿子,那么其他信息都可以快速完成。所以问题等价转化为找旋转后的儿子。
发现这是一个无序的有两个扼要属性的集合(子树大小及其编号),我们以这两个信息为关键字维护集合 \(S\),先把所有重儿子放在集合中,然后可以在\(O(logn)\)的时间内查询对应新儿子。
而在此基础上,我们可以更新 \(S\) 集合,从而维护旋转操作。
对于查询操作,直接输出信息。