cf754.md 4.6 KB
+++ date = "2021-11-13T01:50:00+08:00" draft = false tags = [] title = "Codeforces Round #754 (Div. 2)" authors = ["xry111"] +++
A - A.M. Deviation
题意：给你三个数 $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 可以写很短：
t = int(input())
for cs in range(1, t + 1):
a = sum(map(int, input().split()))
print(int(a % 3 != 0))
B - Reverse Sort
题意：给你一个串 $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
由于 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
题意：给定串 $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 就能过”
的假题，因为我认为这会鼓励乱冲暴力的壬。