cfedu89.md 5.5 KB
+++ date = "2020-06-12T01:43:00+08:00" draft = false tags = [] title = "Educational Codeforces Round #89" authors = ["xry111"] +++
Educational Codeforces Round #89
A. Shovels and Swords
问题重述
给你数 $a$ 和 $b$ ，求
$$\max x + y \quad \text{s. t.} x, y \in \mathbb{Z},
\quad 2x + y \leq a, 2y + x \leq b$$
题解
这是个原题，答案就是 $\min\{x, y, \lfloor{\frac{x+y}{3}}\rfloor\}$。 具体怎么推导的👴忘了。时间复杂度 $\mathcal{O}(1)$。
B. Shuffle
问题重述
有 $n$ 个点排成一列，其中第 $x$ 个点上放了一个标记。 进行 $m$ 次操作，第 $i$ 次操作时可以在第 $l_i, \cdots, r_i$ 个点之间随便移动标记。求最后标记可能位于的点的个数。
$1 \leq n \leq 10^9，1 \leq m \leq 100$。
题解
直接模拟内存显然会爆炸。 容易发现每次移动的时候，如果 $l_i, \cdots, r_i$ 不包含任何当前标记可能位于的点，这步操作就没用。 否则，标记可能位于的点的集合会并上 $\{l_i, \cdots, r_i\}$。 一开始标记可能位于的点的集合为 $\{x\}$，用数学归纳法可以看出， 每个时刻标记可能位于的点的集合都是连续的若干个点。 维护一下最左边和最右边的点就行了。时间复杂度是 $\mathcal{O}(m)$。
C. Palindromic Paths
问题重述
给你一个矩阵 $\mathbf{A} \in \{0, 1\}^{n \times m}$， 你可以从左上角走到右下角，每一步只能向下或向右走， 一边走一边依次写下经过的数字，得到一个序列。 那么，至少要修改多少个数字，才能使得每种走法得到的序列都是回文的？
题解
显然序列长度 (歩数) 一定是 $n+m-1$，而第 $i$ 步走到的位置 $(x, y)$ 必须满足 $x + y = i$。观察一下可以看出， $$\{(x, y) | x + y = i\} \cup \{(x, y) | x + y = n-m-2-i\}$$ 中所有位置的数字必须相同。如果其中有 $t$ 个数字，$o$ 个 $1$， 那么就得修改 $\min\{o, t-o\}$ 个数字。对所有 $i$ 求和就行了。
时间复杂度是 $\mathcal{O}(nm)$。
注意，如果 $n + m$ 是偶数，则第 $\frac{n+m}{2} - 1$ 步走的数正好位于序列的正中间，此时不需要修改这些数。
D. Two Divisors
问题重述
给你 $n$ 个数 $a_1, \cdots, a_n$，对于每个数 $a_i$， 寻找它的两个不是 $1$ 的因子 $d_1$ 和 $d_2$， 使得 $d_1 + d_2$ 和 $a_i$ 互质。
$1 \leq n \leq 5 \cdot 10^5$，$2 \leq a_i \leq 10^7$。
题解
太难了啊，不会啊 QAQ。
问了群里的 dalao 们，他们说了一个结论：如果 $a_i$ 是某个素数的幂，则无解， 否则一定能找到 $u$ 和 $v$ 满足 $uv = a_i$，且 $u \perp v$， $(u, v)$ 就是合法的解。简要证明如下：
首先对于素数的幂 $p^j$，无论怎么取 $d_1$ 和 $d_2$， 既然要取一个因子，结果仍然是 $p$ 的幂，即 $p^{k_1}$ 和 $p^{k_2}$。 由于题目要求 $d_1 > 1$，$d_2 > 1$，有 $k_1 > 0$，$k_2 > 0$。 故 $gcd(d_1, d_2) = gcd(p^{k_1}, p^{k_2}) = p^{\min(k_1, k_2)} \geq p^1 = p > 1$。因此无解。
然后证明如果 $uv = a_i$，且 $u \perp v$，则 $(u, v)$ 对于 $a_i$ 是合法的解。 我们有 $(u + v) \mod u = 0 + v \mod u = v \mod u \neq 0$， $(u + v) \mod v = u \mod v + 0 = u \mod v \neq 0$。 根据中国剩余定理，因为 $u \perp v$，可得 $(u + v) \mod (uv) = (u + v) \mod a_i \neq 0$。这就满足了题目的要求。
最后对于所有不是素数幂的 $a_i$ 构造出 $u$ 和 $v$ 即可，最简单的方法是， 取出 $a_i$ 的最小素因子 $p$，它在 $a_i$ 中出现 $k$ 次，就使得 $u = p^k$，$v = a_i / u$ 即可满足要求。
可以用筛法预处理最小素因子，这样做时间复杂度就是 $\mathcal{O}(\max\{a_i\} \log \log \max\{a_i\} + \sum \log a_i)$。
E. Two Arrays
问题重述
给你序列 $a$ 和 $b$，把 $a$ 分成 $|b|$ 段， 使得第 $i$ 段的最小值是 $b_i$，求划分的方案数对 $998244353$ 的模。
$|a|, |b| \leq 2 \cdot 10^5$，保证 $b$ 严格单调上升。
题解
特判掉各种答案为 $0$ 的情况以后，会发现第 $i$ 个分界点 ($1 \leq i < m$) 可以选区间 $[l_i, r_i)$ 中的任意位置。 其中 $l_i$ 是 $a$ 中最后一个小于 $b_i$ 的数的位置， $r_i$ 是 $a$ 中最后一个等于 $b_i$ 的数的位置。 由于 $bi$ 的单调性，这些区间两两不相交。 所以直接用乘法原理，得到答案就是 $$\prod{i} (r_i - l_i)$$
$l_i$ 和 $r_i$ 倒着做个双指针就出来了，时间复杂度是 $\mathcal{O}(|a|+|b|)$。
这个题 WA 了一发，因为 $r_i$ 和 $l_i$ 都是下标，在 Rust 中是 usize 类型。
在本地的 64 位机器可以直接拿它当 64 位整数去乘，
但 Codeforces 的评测机是 32 位的，usize 就是 32 位无符号整数，
乘法直接爆炸。需要用 i64::try_from 搞一个类型转化。