P6303 题解

AC_love · 2023-10-26 10:53:13 · 题解

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

比如我现在有一个串：

其实它就会等价于：

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

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

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

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

不妨分类讨论。

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

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

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

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

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

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

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

这样的或类似的情况。

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

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

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

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

合并相邻的相同元素后：

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

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

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

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

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

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

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

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

怎么实现这一点呢？

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

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

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

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

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

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

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

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

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

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

我们发现：如果此时两个字符串的长度的差模 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;
}