Codeforces Round 649 (Div.2)

Posted on Edited on

在这场好吓人的啊这评分, 为啥我觉得最后一题的评分是恶评啊.

$\text{[CF1364A]XXXXX}$

$\color{green}{\text{[EASY]}}$

这题好诈骗啊, 差点真的被骗到了.

注意到如果所有的数都是 $x$ 的倍数, 那一定是无解.

如果所有数的和不是 $x$ 的倍数, 那直接就是 $n$ .

否则一定要减去一个不为 $x$ 的倍数的数, 那就是从左边和从右边找到第一个不是 $x$ 的倍数的数, 比较哪个数删的更少.

$\text{[CF1364D]Ehab’s Last Corollary}$

$\color{green}{\text{[EASY]}}$

这题也挺诈骗的.

考虑 $dfs$ 树, 如果出现一条非树边, 那就直接判断环是否小于 $k$ .

如果没有小于 $k$ 的环, 就判断是否 $m = n-1$ , 是的话直接奇偶分层选多的那一层就好了.

不是的话, 必然有树深度大于等于 $k$ , 因为环长都至少为 $k+1$ , 所以选深度最大的点往根间隔染色即可.

$\text{[CF1364E]X-OR}$

$\color{green}{\text{[EASY]}}$

很显然的是找到 $0$ 的位置, 就可以获得其他所有数的位置.

那么问题就转化成了如何在较少的次数里找到 $0$ 的位置.

不难想到一件事, 拿三个数来比较.

如果 $query(a,b) \geqslant query(a,x)$ 且 $query(a,b) \geqslant query(b,x)$ 那么 $a$ 显然不可能是 $0$ .

我们可以枚举每个位置, 找到值最下的两个数, 里面必然有一个是 $0$ .

随机几个数来判断一下就能判断出哪个是 $0$ .