P6303 [eJOI 2018] AB 串

**题目译自 [eJOI2018](http://ejoi2018.org/) Problem C.** ***AB-Strings***

你有两个字符串 $s,t$，它们其中仅包含字母 `a` 和 `b`。你可以多次进行如下操作：选出一个 $s$ 的前缀和一个 $t$ 的前缀并交换它们。（注意，这个前缀既**可以为空**也可以为整个串） 你的任务是找出一个操作序列使得进行这些操作后，一个字符串只包含字符 `a`，而另一个只包含字符 `b`。 你应该尽可能的进行最少的操作次数，但非最优解仍可能得到一部分分数，详情见“数据范围与提示”一栏。

无

无

#### 样例 $1$ 解释： 在这个样例中，首先把第一个串 $1$ 个长度的前缀与第二个串 $0$ 个长度的前缀交换，即将 `b` 插入第二个串开头。这时两个串变成了 `ab` 和 `bbb`。接下来把第一个串 $1$ 个长度的前缀与第二个串 $3$ 个长度的前缀交换，即交换 `a` 和 `bbb`，此时两个串变成了 `bbbb` 和 `a` ，达成目标。 #### 样例 $2$ 解释： 已经是最终要求的状态了。 ------ #### 计分策略 设 $n$ 为你给出的操作数量，$m$ 为标准答案，**本题使用 SPJ**。 - 如果所有任务中 $n=m$，那么将得到 $100\%$ 的分数。 - 如果所有任务中 $n\leq m+2$，那么将得到 $70\%$ 的分数。（四舍五入到最接近的整数） - 如果所有任务中 $n\leq 2m+2$，那么将得到 $50\%$ 的分数。（四舍五入到最接近的整数） - 如果所有任务中 $n\leq 5\times 10^5$，那么将得到 $30\%$ 的分数。（四舍五入到最接近的整数） - 如果至少一个任务中 $n > 5\times 10^5$，那么将得到 $0\%$ 的分数。 ---- 对于 $100\%$ 的数据，保证 $1\leq \lvert s\rvert,\lvert t\rvert \leq 2\times 10^5$，$\lvert s\rvert,\lvert t\rvert$ 分别代表 $s,t$ 的长度，且保证至少有一个串中包含至少一个字符 `a`，至少一个串中包含至少一个字符 `b`。 #### 数据限制 |子任务编号|分数|限制| |:-:|:-:|:-:| |$1$|$5$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 6$，这两个字符串中共含有一个字符 `a`| |$2$|$10$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 6$ | |$3$|$20$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 50$ | |$4$|$20$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 250$ | |$5$|$20$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 2\times 10^3$ | |$6$|$25$|无特殊限制|