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 掉了，事实也确实是这样。
标签：AtCoder,答案,Contest,sum,times,Regular,端点,170 From： https://www.cnblogs.com/acwing-gza/p/18000229