cf628.md 4.8 KB

+++ date = "2020-03-15T21:15:00+08:00" draft = false tags = [] title = "Codeforces Round #628 (Div. 2)" authors = ["xry111"] +++

Codeforces Round #628

A. EhAb AnD gCd

问题重述

给你数 $x$,让你求 $a, b$ 使得 $GCD(a, b) + LCM(a, b) = x$。

题解

假题,只要选择 $a = x-1, b = 1$ 即可。

代码

B. CopyCopyCopyCopyCopy

问题重述

给你一个数列 $\mathbf{a} = \{a_i\}$, 把它重复 $n$ 次以后得到一个新的数列, 求新的数列的最长严格上升子序列的长度。

题解

假题,我们在第 $k$ 次重复中选择 $\mathbf{a}$ 中第 $k$ 小的元素。 如果所有元素都相同,那么就能选出 $n$ 个。如果有重复的,相同的数只能选一次, 因此答案就是 $\mathbf{a}$ 中不同元素的个数。

代码

C. Ehab and Path-etic MEXs

问题重述

给你一个树 $G = (V, E)$,让你给出一个双射 $f: E \rightarrow \{0, \cdots\, |E|-1\}$,使得

$$\max_{u, v} MEX(\{f(x) | x \in PATH(u, v)\})$$

最小。$PATH(u, v)$ 是 $u$ 到 $v$ 路径上的所有边的集合, $MEX$ 就是博弈论里的那个东西; $$MEX(S) = \min (\mathbb{N} \setminus S)$$

题解

如果有 $3$ 个叶子节点 $u, v, w$,我们把 $0, 1, 2$ 直接分别指定给连接这 $3$ 个叶子节点的边,可以看出此时答案一定是 $2$,不可能有更小的答案。 如果只有 $2$ 个叶子节点,树就退化成一条链,此时无论怎么指定, 答案都是 $|E|$。

代码

D. Ehab the Xorcist

问题重述

给定非负整数 $u$ 和 $v$,求一个尽量短的数列 $\mathbf{a}$, 使得其中所有数异或起来为 $u$,和为 $v$。

题解

首先如果 $u > v$ 或者 $u$ 和 $v$ 奇偶不同,显然无解。

根据计算二进制和的进位法,容易看出 $$(a \oplus b) + (a \cup b) + (a \cup b) = a + b$$

根据异或的计算法则,有 $$(a \oplus b) \oplus (a \cup b) \oplus (a \cup b) = a \oplus b$$

两边对照一下,我们取 $p = u, q = r = (v-u)/2$,则 $\{p,q,r\}$ 就是一个合法的答案。可见答案的长度最长就是 $3$。 有一些特殊情况下答案可能更短:如果 $u = v = 0$,则答案是空数列。 如果 $u = v > 0$,则答案就是一个包含 $u$ 的长度为 $1$ 的数列。 如果 $p \oplus q = p + q$,则我们可以将它们合并起来, 得到长度为 $2$ 的数列。

代码

E. Ehab's REAL Number Theory Problem

问题重述

给定一个正整数组成的数列 $\mathbf{a} = \{a_i\}$,从中选出尽量少的数, 使得它们的乘积是完全平方数。保证 $|\mathbf{a}| \leq 10^5$, $a_i \leq 10^6$,且 $a_i$ 至多有 $7$ 个因子

题解

$a_i$ 至多有 $7$ 个因子,说明其至多有 $2$ 个不同的质因子 ($3$ 个不同质数乘来乘去就能得到 $8$ 个不同的数了)。 对于每个质因子我们只关心它在 $a_i$ 中出现次数的奇偶性。 如果某个 $a_i$ 本身就是完全平方数,那么只选它就行了。 否则,$a_i$ 要么有 $1$ 个出现奇数次的质因子, 要么有 $2$ 个出现奇数次的质因子。我们将所有质数和 $1$ 作为点建个图, 对于第一种情况,把这个质因子和 $1$ 连起来;对于第二种情况, 把两个质因子连起来。然后容易看出,图中的每个环都是一个合法的答案, 我们要找的就是最小环。BFS 找最小环的时间复杂度是 $\mathcal{O}(|V||E|)$: 每次 BFS 需要 $\mathcal{O}(|E|)$ 的时间,需要对于 $|V|$ 个点都作为起点 BFS 一次,这样会超时。但是本题中如果大于 $\sqrt{\max a_i}$ 的点在某个环中,则它连接到的必然都是小于 $\sqrt{\max a_i}$ 的点。 因此,我们不需要考虑以大于 $\sqrt{\max a_i}$ 的点作为起点的情况 (这样的环一定也包含小于 $\sqrt{\max a_i}$ 的点, 以这个较小的点做起点就能找到这个环了)。这样就只要枚举 $\mathcal{O}(\sqrt{\max a_i} / \log \max a_i)$ 个起点, 边数 $|E|$ 是 $\mathcal{O}(|\mathbf{a}|)$ 的,因此总的时间复杂度是 $$\mathcal{O}(\frac{\sqrt{\max a_i} |\mathbf{a}|}{\log \max a_i})$$ 大概算一下也就是不到 $10^8$ 量级,这题时限还是 $3$ 秒,肯定没问题了。

代码