随便写一些算法（七）

Codeforces Round 804（div 2）

C.The Third Problem
题目大意
给你一个序列 $a$ ， $a$ 是一个 $[0\to n-1]$ 的排列
问能够造出多少种序列 $b$ ，其中 $b$ 也是一个 $[0 \to n-1]$ 的排列
并且必须满足， $b$ 所有的子区间 $[l, r]$
$\text{mex}(b_l\cdots, b_r) = \text{mex}(a_l, \cdots, a_r)$

算法分析
因为 $b$ 是一个排列，所以 $b$ 的所有子区间的 $\text{mex}$ 值一定会取遍 $\{0, 1, \cdots, n-1, n\}$
于是我们可以一个一个数考虑，对于数 $x \in [0, n-1]$ ，考虑它有几个位置可以放置？
最后把答案都乘起来就可以

不妨设当前正在考虑的数为 $x$
并且使得 $[0\cdots x-1]$ 这些数都出现过的最小区间是 $[l, r]$ ，我们有一些性质

$[l, r]$ 中的所有子区间（不包括 $[l, r]$ ）的 $\text{mex}$ 值只能在 $\{0,1, \cdots, x-1\}$ 中取
并且除了 $\{0, 1, \cdots, x-1\}$ 这些数所在的位置之外，剩下的数都 $> x-1$
只要 $\{0, 1, \cdots, x-1\}$ 这些数的位置不变，剩下的数换成任意一个 $> x-1$ 的数
所有子区间的 $\text{mex}$ 值都不会改变
$\{0, 1, \cdots, x-1\}$ 这些位置呢？实际上这是一个子问题
考虑 $[0\cdots x-2]$ 所有数都出现的最小子区间 $[l', r']$ ，如上分析

这样就启发我们从 $x \in [0 \to n-1]$ 递推考虑
不妨设当前正在考虑的数是 $x$ ，首先必须找到最小的满足 $[0\cdots x-1]$ 都出现的区间 $[l, r]$

$x$ 在 $[l, r]$ 区间外面，不妨设它的位置是 $p(x)$ ， $p(x) > r$
那么此时 $b$ 中 $x$ 的位置不能动
因为 $\text{mex}([r+1, p(x)-1]) = x$ ，如果将 $x$ 移动到 $\text{p}(x) - 1$
那么 $\text{mex}([r+1, p(x)-1]) = x+1 \neq x$ ，不符合条件
$x$ 在 $[l, r]$ 区间中， $l \leqslant p(x) \leqslant r$
经过我们上面的分析， $x > x-1$
所以 $x$ 可以放置在除了 $\{0, 1, \cdots, x-1\}$ 所在位置之外的任意一个位置
$x$ 放置位置的方案数为 $(r-l+1 - x)$

D. Almost Triple Deletions
题目大意
给你一个数组 $a[1\cdots n]$ ，每一次操作，如果 $a_i \neq a_{i+1}$ ，可以将 $a_i, a_{i+1}$ 都删掉
删掉之后剩下的数拼接起来
经过若干次这样操作之后，最后要使得数组中所有元素都相同
那么最后的数组最大长度是多少

思路分析
由于操作之后数组中所有元素都相同， $n \leqslant 5000$ ，所以可以枚举操作完成后，数组中相同元素的值 $x$
一开始可以对 $x$ 出现的所有位置打表，记 $x$ 出现的第 $i$ 个位置是 $\displaystyle f_x(i)$
只考虑 $x$ 出现的位置，从 $i-1 \to i$

对于区间 $[f_x(i-1)\cdots f_x(i)]$ ，如果中间的数 $[f_x(i-1)+1, f_x(i)-1]$ 能全部消去
那么就存在转移 $f_x(i) = f_x(i-1) + 1$
其中 $f_x(i)$ 表示第 $i$ 个 $x$ 这个位置，得到的数组的最大长度

这样就启发我们用 $dp$ 来实现
$dp(i)$ 表示 $i$ 位置的这个数最终保留下来，并且作为序列结尾，能得到的序列最大长度
那么存在 $dp(i) = \max(dp(j) + 1) \quad (a_j = a_i, \ 1 \leqslant j \leqslant i-1)$ 的转移
当且仅当 $[j+1, i-1]$ 中的数可以消去

要想保留 $a_i$ ，那么 $dp$ 的起点一定是找到第一个 $x = a_i$ 所在的位置 $s$
令 $dp(s) = 1$ ，然后递推
一开始的时候，所有点的 $dp$ 值都是 $0$ ，先预处理一下
如果 $[1\cdots i-1]$ 的前缀可以消去，那么 $i$ 就可以作为 $dp$ 的起点， $dp(i) = 1$
接着按上面的方法递推就可以

接下来的难点就是，什么时候 $[l, r]$ 中的元素可以全部消去？不妨设 $[l, r]$ 中的元素个数为 $n$

$n$ 必须是偶数，这根据题意很容易发现
实际上消去的充要条件是，对 $[l, r]$ 中的每一个数 $x$ ，都能找到一个 $y \neq x$ 与它匹配
对于出现次数最大的数 $x$
$x$ 如果出现次数 $> n/2$ ，必然有某个 $x$ 找不到匹配，否则一定是可以的

证明如下，如果出现次数最多的数 $x$ 出现的次数都 $\leqslant n/2$ ，那么最坏的情况
就是序列一段都是 $x$ ，最前面的 $x$ 能消去，那么一整段都可以消去
这是可能的，因为我们可以贪心地考虑 $[2\cdots, n/2]$
这些 $x$ 从后往前依次和 $[n/2+1 \cdots n]$ 这些 $y \neq x$ 配对删除
再来看看充分性
如果有一个数 $x$ 出现次数 $k > n/2$ ，那么其他元素的个数是 $n - k$
因为其他元素都要被删除，所以还剩下无法匹配的 $x$ 个数是 $n - 2(n-k) > 0$
这显然是不符合全部删除的要求的

最后计算答案的时候，因为每一个位置 $i$ 都可能作为序列的结尾
根据之前的分析， $dp(i)$ 是 $i$ 这个位置保留下来并且作为序列结尾，能够得到的最大长度
如果 $[i+1, n]$ 这一段能够完全删除，那么就可以对所有这样的 $dp(i)$ 取一个 $\max$ 就是答案

E. Three Days Grace
题目大意
给你一个数组 $a[1, n]$ ，可能有重复元素，每一个元素的值都在 $[1, m]$ 之间
接下来你可以
在 $a$ 中选出一个元素 $x$ ，然后对 $x$ 进行分解， $x = p\cdot q, \ (p, q > 1)$
然后把 $x$ 从 $a$ 中删除，再把 $p, q$ 加入集合 $a$ 中
问经过若干次这样的操作之后，数组的 $\max(a_i) - \min(a_i)$ 最小是多少

先来看一个经典问题
给你一个数组，要求你求一个区间 $[l, r]$ ，使得这个区间中 $\max(a_i) - \min(a_i)$ 最大或最小

这个问题我们一般是枚举最小值 $x$ ，单调栈求出左边第一个 $> x$ 的元素位置 $l$
以及右边第一个 $> x$ 的元素位置 $r$ ，那么 $[l+1, r-1]$ 区间的最小值都是 $x$

接下来只需要用 $\text{ST}$ 表或者是线段树求出 $[l+1, r-1]$ 的最大值 $maxv$ 即可
然后用 $maxv - x$ 来更新全局的 $ans$ ，即可在 $O(n \log n)$ 的复杂度内完成问题求解

本题也可以类似考虑
枚举 $i$ 作为序列最小元素 $minv$ 时候的情形，问题等价于
对于每一个 $i$ ， $i$ 可以由 $x \in [i\cdot i, \ i \cdot(i+1), \ i \cdot (i+2) \cdots ]$ 分解而来

$i$ 作为 $x$ 分解得到的最小的因子，我们要在 $x$ 分解出来的，并且 $\geqslant i$ 的因子中
找到尽量小的那个因子，记这个尽量小的因子是 $dp_i(x)$

尽量小的，并且比 $i$ 大的因子记为 $res$

这样对于每一个 $x$ 有 $2$ 种决策

$x$ 分解出一个 $i$ 来，不往下继续分解了， $res = dp_i(x)$
对 $x/i$ 继续往下分解，枚举 $x/i$ 的分解情况
$\textbf{for} \ \forall j \mid (x/i)$ ， $j$ 作为 $x/i$ 的因子，必须满足
$\textbf{(1)}\quad j > i, \ j = [i, i+1, \cdots]$
$\textbf{(2)}\quad j$ 是 $x/i$ 分解出来的最小因子

这样就有转移

$\displaystyle dp_i(x) = \min(dp_i(x), \forall j \min_{j} dp_j(x/i)), j$ 满足上述两个条件

那么这个问题很容易用 $O(n^2)$ 枚举求解，一边求解的时候一边用 $dp_i(x) - i$ 更新答案即可
下面考虑如何优化

注意到我们这里用 $dp_j(x')$ 来更新 $dp_i(x)$ ，其中 $j \geqslant i$
如果我们 $j$ 从大往小去遍历，相应的 $dp_{j+1}(x)$ 就可以实时维护
换句话说，当 $j+1 \to j$ 的时候， $dp_{j+1}(x)$ 的值实际上是维护了 $\left< dp_{j+1}(x), dp_{j+2}(x), \cdots \right>$

由此，从大往小去遍历 $i$ ，上面的式子就可以实时维护了
具体来说用旧的 $dp(x/i)$ 来更新当前的 $dp(x)$

那最后一个问题就是如何计算答案，可以用一个 $\textbf{set}$ 维护 $dp$ 值，一开始所有数 $dp(x) = x$
将其都放入 $\text{set}$ 中
对于 $\textbf{for} \ \forall i \in [maxv \to 1]$
执行 $dp(x) = \min (dp(x), dp(x/i))$ 的时候，我们要这样做
（1）将原来的 $dp(x)$ 从 $\text{set}$ 中删除
（2）更新 $dp(x) = \min(dp(x), dp(x/i))$
（3）在 $\text{set}$ 中插入新的 $dp$ 值

当遍历 $i \leqslant minv$ ， $minv$ 是原序列的最小值
我们就可以用 $\text{set 中的最大值} - i$ 来更新答案了

Educational Codeforces Round 131

D. Permutation Restoration
题目大意
你有一个排列 $a$ ，现在你可以根据 $a$ 得到数组 $b$ ，其中 $b_i = \displaystyle \left \lfloor \frac{i}{a_i} \right \rfloor$

现在你忘了排列 $a$ 是啥，给你一个数组 $b$ ，要求从数组 $b$ 构造出数组 $a$

原问题可以转换成为，已知 $i, b_i$ ，构造出 $a_i$ 满足

$\displaystyle \frac{i}{b_i+1} < a_i \leqslant \frac{i}{b_i}$ ，不妨记 $L(i) = \displaystyle \frac{i}{b_i + 1} + 1, R(i) = \frac{i}{b_i}$

下面问题转换成
给你 $n$ 个数，第 $i$ 个数的取值区间是 $[L(i), R(i)]$ ，要求你在每一个区间内选一个数来构造排列
其中要求，所选的数不能重合，这是贪心算法中很典型的活动选择问题

在活动选择问题中，我们是这样执行贪心策略的
对所有区间按照右端点排序，然后依次检查每一个区间
对于每个区间，我们选择最小的，并且未被选过的数，那么这个问题也类似

这个问题与区间选择问题不同的是，可能多个 $a(i_1), a(i_2), \cdots$ 有着相同的左端点
可以先打表处理 $\text{has}(x) = \{i_1, i_2, \cdots\}$ ，表示这些 $i$ 都以 $x$ 作为值域区间的左端点

然后我们遍历 $\textbf{for} \ \forall x \in [1\cdots n]$
对于 $\text{has}(x)$ 中的 $\left<i_1, i_2, \cdots \right>$ ，根据活动选择问题中的分析
这些 $i$ 我们理论上都可以赋值成 $a_i = x$ ，但我们应该取 $R(i)$ 尽量小的那个 $i$ 赋值成 $x$

算法实现上，用一个二元组 $(R(i), i)$ 来表示
那么我们应该把 $x$ 值，赋给尽量小的 $R(i)$ 所对应的那个 $i$
将二元组放入 $\text{set}$ 中，然后将 $\text{set}$ 最开头那个元素对应的 $i$ 赋值成 $x$
赋值完成后就将其删除，这样就保证了每个元素只会被赋值一次

E. Text Editor
题目大意
你有一个文本编辑器，你本来想要打一个目标串 $t$ ，包含 $m$ 个小写字符
但是你现在打了一个文本串 $s$ ，包含 $n$ 个小写字符并且 $m \leqslant n$

现在你有以下几种操作，一开始光标在 $s$ 的最后一个字符后边
$\text{left}$ 将光标左移 $1$ 位， $\text{left}$ 将光标右移 $1$ 位
$\text{Home, End}$ 分别将光标置为文本串的最开始（第一个字符前面）和最末尾（最后一个字符后边）
$\text{Back}$ 删除光标前的字符并将其删除