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$ 的数的位置。 由于 $b_i$ 的单调性，这些区间两两不相交。 所以直接用乘法原理，得到答案就是 $$\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 搞一个类型转化。

代码