+++
date = "2020-06-12T01:43:00+08:00"
draft = false
tags = []
title = "Educational Codeforces Round #89"
authors = ["xry111"]
+++

# [Educational Codeforces Round #89](https://codeforces.com/contest/1366)

## [A. Shovels and Swords](https://codeforces.com/contest/1366/problem/A)

### 问题重述

给你数 $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)$。

[代码](https://codeforces.com/contest/1366/submission/83389977)

## [B. Shuffle](https://codeforces.com/contest/1366/problem/B)

### 问题重述

有 $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)$。

[代码](https://codeforces.com/contest/1366/submission/83394620)

## [C. Palindromic Paths](https://codeforces.com/contest/1366/problem/C)

### 问题重述

给你一个矩阵 $\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$
步走的数正好位于序列的正中间，此时不需要修改这些数。

[代码](https://codeforces.com/contest/1366/submission/83410400)

## [D. Two Divisors](https://codeforces.com/contest/1366/problem/D)

### 问题重述

给你 $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)$。

[代码](https://codeforces.com/contest/1366/submission/83574965)

## [E. Two Arrays](https://codeforces.com/contest/1366/problem/E)

### 问题重述

给你序列 $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`][1] 搞一个类型转化。

[1]:https://doc.rust-lang.org/std/primitive.i64.html#method.try_from

[代码](https://codeforces.com/contest/1366/submission/83463242)
