A
贪心。
首先判无解。
如果一个位置要变成 A,那么它右边必须要有个 B。
如果一个位置要变成 B,那么它右边必须要有个 A。
然后算答案,首先有一个明显的上限:
$$\sum_{i=1}^{n}[s_i \neq t_i]$$
假设我们有 $i$ 位置要变成 A,$j$ 位置要变成 B,且 $i<j$,那么可以减少一次操作,扫一遍即可,$O(n)$。
B
明显的难度区别:A>>B。
枚举 $j$ 和公差,寻找最近的 $i$ 和 $k$。
如何更新答案?我们要知道固定左端点的情况下枚举右端点,是否是“好对”这一条件是有单调性的。
我们设 $f_i$ 为固定左端点为 $i$ 的情况下,最小的 $j$ 使得 $(i,j)$ 为好对。
假设我们搜索出了一个 $(i,k)$ 对,那么对于 $f_{1} \sim f_{i}$,都要对 $k$ 取个 $\min$。
具体实现上是做了一个 lazytag,每次只标记了 $i$ 一个点,然后最后统计答案的时候往前推一遍 tag 即可。
答案为:
$$\sum_{i=1}^{n}(n-f_i+1)$$
C
非常厉害的 dp。
当 $m>n$ 的时候,答案一定是:
$$m^{\sum_{i=1}^{n}[a_i=0]}$$
当 $m \leq n$ 的时候,细细考虑一下:
我们只关心当前前缀的 $\operatorname{mex}$ 是否为 $i$。
-
$a_i=1$ 的时候相当于强制干掉最左边的空位。
-
$a_i=0$ 的时候相当于找别的地方填一下即可(可重复填)。
假设取了一个 $i$ 称为占了一个格子。
设 $f_{i,j}$ 表示前 $i$ 个占掉了 $j$ 个格子的方案数。
则有转移:
$$ f_{i,j}= \begin{cases} f_{i-1,j-1} & a_i=1 \\ j \times f_{i-1,j}+(m-j+1) \times f_{i-1,j-1} & a_i=0 \end{cases} $$
时间复杂度 $O(n^2)$。
值得注意的是,这里的转移系数都不与 $i$ 有关,那么有没有神仙能优化优化呢?
D
考虑人类智慧做法。
排序 $a$ 和 $b$,然后猜测选完 $a$ 以后 $b$ 一定是选择较大或较小的几个,接着我们二分第二次选 $a$ 中是否可行。
继续猜测!前后扫描 15 个差不多就可以 A 掉了,事实也确实是这样。