Codeforces Round #754 (Div. 2)

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 就能过” 的假题,因为我认为这会鼓励乱冲暴力的壬。

Xi Ruoyao
Xi Ruoyao
PhD Student

Retired from ICPC, now a PhD student and an assistant ICPC coach (with no salary).