+++
date = "2021-11-13T01:50:00+08:00"
draft = false
tags = []
title = "Codeforces Round #754 (Div. 2)"
authors = ["xry111"]
+++

* [比赛链接](https://codeforces.com/contest/1605)

# [A - A.M. Deviation](https://codeforces.com/contest/1605/problem/A)

题意：给你三个数 $a\_1, a\_2, a\_3$，
每次你可以给 $a\_i$ 加 $1$，$a\_j$ 减 $1$。
要求最小化

$$d(a\_1, a\_2, a\_3) = |a\_1 + a\_3 - 2 \cdot a\_2|$$

显然，在题目给定的条件下，只要保证三个数和不变，可以随便改变它们的值。
最优解显然是使得三个数尽量接近，那就取它们的平均值向上向下取一取整就行了。
试几个数会发现如果 $\\sum a\_i$ 是 $3$ 的倍数则可以使得 $d$ 为 $0$，
否则 $d$ 为 $1$。

用 Python 3 可以写很短：

```python
t = int(input())
for cs in range(1, t + 1):
    a = sum(map(int, input().split()))
    print(int(a % 3 != 0))
```

# [B - Reverse Sort](https://codeforces.com/contest/1605/problem/B)

题意：给你一个串 $s \\in \\{0, 1\\}^\*$，每次操作可以从中选一个子序列，
然后将其反序，要求用尽量少的操作将整个串排好序。

这题初看上去很不可做，但是一看串只有 $0$ 和 $1$，再一看样例要么操作 $1$
1 次要么操作 $0$ 次就感觉是假题…… 然后发现只要把 $s$ 排个序得到 $t$ 以后，
找到所有 $s[i] \neq t[i]$ 的位置做反序就行了。

这题用 Python 3 也可以写很短，但是场上把数据范围看成了 $1000 \times 1000$
就怕卡常没敢用 Python，赛后才发现数据范围就是 $1000$。

# [D - Treelabeling](https://codeforces.com/contest/1605/problem/D)

由于 C 题看上去很不可做，于是先去写 D。

题意：给一个树 $T = (V, E)$，你可以指定一个双射
$f: V \\rightarrow \\{1, 2, \cdots, |V|\\}$。如果
$(i, j) \\in E$，且 $f(i) \\oplus f(j) > \\min(f(i), f(j))$，就把
$(i, j)$ 这条边删掉，这样会得到一个森林 $G = (V, E')$。
然后你选一个点 $v\_0$ 放一个棋子。之后你的对手先手，两人轮流移动，
每次可以将棋子沿 $E'$ 中的一条边进行移动，不能移动到棋子曾经占据过的点，
如果某人无法移动则输。要求你求出一个 $f$，使得能选做 $v\_0$ 的点尽量多。

这题初看上去很不可做，但是 “你的对手先手” 这个条件就很有趣。
然后在纸上画了画，感觉能够构造 $f$ 将所有边删光，
自闭了一会以后就想到怎么构造了：首先 $T$ 作为树一定是二分图。
那么我们对它做一个黑白染色，一定有一种颜色的点 (不妨设是黑点)
的个数 $c$ 不超过 $\\lfloor n / 2 \\rfloor$。然后我们发现若 $a > 0$ 且
$b > 0$，则 $a \\oplus b > \\min(f(i), f(j))$ 的一个充分条件是

$$\\text{highbit}(a) \\neq \\text{highbit}(b)$$

其中 $\\text{highbit}(x)$ 是 $x$ 中最高的，为 $1$ 的二进制位。
于是我们把 $S = \\{1, 2, \cdots, |V|\\}$ 按照 $\\text{highbit}$
值做一个划分：

$$S\_0 = \\{ 1 \\}$$
$$S\_1 = \\{ 2, 3 \\}$$
$$S\_2 = \\{ 4, 5, 6, 7 \\}$$
$$\\cdots$$
$$S\_m = \\{ \\cdots, |V| \\}$$

这样如果 $i \\neq j$ 且 $u \\in S\_i$, $v \\in S\_j$, 则边一定会被删掉，
即 $(u, v) \notin E'$。

显然，对于 $k < m$，$|S\_k| = 2^k$，
且
$$\\sum\_{k < m} |S\_k| = 2^{\\lfloor \\log\_2 |V| \\rfloor} - 1
\\geq \\lfloor n / 2 \\rfloor \geq c$$

因此我们可以把黑点的个数 $c$ 表示成 $m$ 位二进制：

$$c = \\sum\_{i = 0}^{m - 1} 2^i x\_i$$

然后如果 $x\_i = 1$，我们就将 $S\_i$ 中的元素都分配给黑点，
这样一定能为所有黑点都分配一个 $f(\\cdot)$ 值。
之后将 $S$ 中尚未分配的元素都分配给白点。这样，就不存在 $(u, v, k)$ 使得
$u$ 与 $v$ 异色，且 $u, v \\in S\_k$。这就保证了 $E' = \\emptyset$。
此时根本没有边，对手一步都动不了，所有点都可以作为 $v\_0$。

# [C - Dominant Character](https://codeforces.com/contest/1605/problem/C)

题意：给定串 $s \\in \\{a, b, c\\}^\*$，要求你在 $s$ 中找一个尽量短的子串
$t$，使得 $|t| \geq 2$，$t$ 中 $a$ 的个数大于 $b$ 的个数，也大于 $c$
的个数。

这题一开始以为是树套树二维偏序，然而做了 A、B、D
以后就感觉这出题人只会出假题，所以这题肯定也是假题。
然后就猜想如果 $|t| > 10$，就存在 $t'$ 是 $t$ 的真子串，
且 $t'$ 也满足条件，所以假设 $|t| \leq 10$ 然后交了一下就过了。

至于为啥我暂时蒙在鼓里 …… 而且我很讨厌这种 “暴力加个 `break` 就能过”
的假题，因为我认为这会鼓励乱冲暴力的壬。