自动搬运

查看原文

来自洛谷，原作者为

	AC_love 鞍山刻岩玉雕 窗锁烟雨遥 我入背景

搬运于2025-08-24 22:19:30，当前版本为作者最后更新于2023-10-26 10:53:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先我们注意到一个显然的性质：如果有相同的字符连在了一起，显然它们就永远分不开了。

比如我现在有一个串：

$$\texttt{aaaaaabbbbaaaaabbbbbb}$$

其实它就会等价于：

$$\texttt{abab}$$

那么我们可以把这两个串都压缩一下，其实我们发现它们都会形如 $\texttt{ababab}\cdots$ 这种形式。

那么我们只需要考虑怎么处理这样的字符串即可。

我们希望让两个字符串中都只含一种字符，也就是让两个串最后变成一个是 $\texttt{a}$ 另一个是 $\texttt{b}$。

那么怎么做才能让交换次数最少呢？

不妨分类讨论。

假设两个字符串首字母相同：

$\texttt{ababab}\cdots$

$\texttt{ababab}\cdots$

此时我们的最优解是选择一个串的 $\texttt{ab}$ 和另一个串的 $\texttt{a}$ 交换。交换后变成了：

$\texttt{aabab}\cdots$

$\texttt{abbabab}\cdots$

把相邻的相同字符缩成一个之后就是：

$\texttt{abab}\cdots$

$\texttt{ababab}\cdots$

观察到，这种消法可以消掉两个字符。

此时需要一个串取前奇数个，另一个串取前偶数个。

但是需要注意的是：如果你有两个首字母相同的字符串，那么最后你一定要花一步来消掉一个字符。因为最后剩的情况一定是类似这样的：

$\texttt{ab}$

$\texttt{aba}\cdots$

此时你一定需要一步来消掉下面的一个 $\texttt{a}$ 转移到上面，然后变成：

$\texttt{ab}$

$\texttt{ba}\cdots$

这样的或类似的情况。

于是问题就转化成了两个字符串的首字母不同的情况。

因此我们不妨把这一步放到一开始就去进行，免得过程中一大堆特判影响心情（莫名押韵）。

而如果两个字符串首字母不同：

$\texttt{ababab}\cdots$

$\texttt{bababa}\cdots$

此时我们选择各自的第一个字符进行交换，得到：

$\texttt{bbabab}\cdots$

$\texttt{aababa}\cdots$

合并相邻的相同元素后：

$\texttt{babab}\cdots$

$\texttt{ababa}\cdots$

发现也可以消掉两个字符，甚好。

此时需要两个串都取前奇数个。

但是需要注意一种特殊情况：

如果某个字符串长度为 $1$：

$\texttt{a}$

$\texttt{ababab}\cdots$

此时不管怎么转，都最多只能消掉一个字符。

消掉一个字符显然不如消掉两个字符，因此我们不希望看到这种只能消掉一个字符的情况。

也就是说，不论何时，我们都不希望某个串的长度是 $1$。

那么我们就需要让两个串的长度尽可能平衡（注：平衡指两个字符串长度差不超过 $1$）。

怎么实现这一点呢？

我们想到：可以在第一次交换时就让他俩平衡，以后每次交换只交换前两个即可。这样一定可以保证他俩始终是平衡的。

因此我们就要在第一次交换的时候特判一下应该怎么交换。

首先为了便于判断，我们假定缩减后第一个字符串更长。如果第二个更长怎么办？办法显而易见，直接 swap 一下就好了。

注意我这里说的是缩减后的字符串而不是原字符串，因为原字符串长不代表缩减之后的字符串长，举个例子：

$\texttt{aaaaaaaaaaaaaa}$

$\texttt{abab}$

显然第一个字符串更长，但缩减后第一个字符串只有一个字符，而第二个字符串有四个。

还是分成刚才的两种情况。

如果两个字符串首字母相同，刚才说过了，我们需要一步来消掉一个字符来变成两个字符串首字母不同的情况。

看起来我们把长的向短的转使两个尽可能平衡更优，但是如果这样做就会只有 $89$ 分，以下是一个反例：

$\texttt{ababab}$

$\texttt{aba}$

此时我们发现如果把长的向短的转，不管怎么转，转完之后两个字符串长度还是不平衡（注意我们转的时候必须要消掉一个）。

这就让我们很不高兴，怎么解决呢？

我们发现：如果此时两个字符串的长度的差模 $4$ 等于 $3$，那么如果直接把大的向小的转，不管怎么转都是不能平衡的。

为什么呢？因为如果你想消掉一个并做到平衡，转过去的长度必然等于两个字符串的长度的差减一之后再除以二，然而此时你发现转过去之后消不掉。而如果你不消一个转过去的话，那你这一步就失去了意义，白白浪费了一步。

那我们不妨就先转一步把这个差变成模 $4$ 不等于 $3$ 的，然后我们再进入一般情况即可。

如果两个字符串首字母不同，直接转长的使两个串平衡即可，很容易实现。

还有一个需要注意的是：因为我们把一个原字符串转化成缩完之后的字符串的 push 是不停从后 push 的，如果我们顺序存字符串，在转的时候就需要重写一个新的 push 从头部 push，这样很麻烦。不妨考虑倒序存字符串，这样只需要一个 push 就能同时完成两个功能，会方便一些。

代码实现如下：

#include <bits/stdc++.h>
using namespace std;

int n, m, b;
string s1, s2;
struct ch
{
	bool typ;
	int num;
};

deque <ch> v[3];

struct res
{
	int x;
	int y;
};
deque <res> ans;

void push(int w, ch nxt)
// 加入一个字符 
{
	int sz = v[w].size();
	if(!sz || v[w][sz - 1].typ != nxt.typ)
		v[w].push_back(nxt);
	else
		v[w][sz - 1].num += nxt.num;
}

void work(int x)
// 取出 v1 的前 x 个与 v2 交换 
{
	int l = 0;
	ch tmp = v[1].back();
	v[1].pop_back();
	for(int i = x; i; i = i - 1)
	{
		push(1, v[2][v[2].size() - i]);
		l += v[2][v[2].size() - i].num;
	}
	ans.push_back({tmp.num, l});
	while(x --)
		v[2].pop_back();
	push(2, tmp);
}


signed main()
{
	cin >> s1 >> s2;
	int l1 = s1.length();
	int l2 = s2.length();
	for(int i = l1 - 1; i >= 0; i = i - 1)
		push(1, (ch){s1[i] == 'a', 1});
	for(int i = l2 - 1; i >= 0; i = i - 1)
		push(2, (ch){s2[i] == 'a', 1});
	if(v[1].size() > v[2].size())
		swap(v[1], v[2]),
		b = 1;
	if(v[1][v[1].size() - 1].typ == v[2][v[2].size() - 1].typ)
	// 首个字母相同 
	{
		if(((v[2].size() - v[1].size()) & 3) == 3)
			// 此时不管怎么转都无法平衡 
			work((v[2].size() - v[1].size() + 1) / 2);
			// 先转一次 
		push(1, (ch){1 - v[1][v[1].size() - 1].typ, 0});
		work((v[2].size() - v[1].size() + 1) / 4 * 2 + 1);
		// 使之平衡 
	}
	else if(v[2].size() - v[1].size() > 2)
	// 首个字母不同，两个字符串长度不平衡
		work((v[2].size() - v[1].size() + 1) / 4 * 2 + 1);
		// 使之平衡 
	while(v[1].size() > 1 || v[2].size() > 1)
		work(1);
		// 已经平衡了，直接开转就行 
	cout << ans.size() << "\n";
	for(int i = 0; i < ans.size(); i = i + 1)
	{
		if(b)
			swap(ans[i].x, ans[i].y);
		cout << ans[i].x << " " << ans[i].y << "\n";
	}
	return 0;
}