题解：P10191 [USACO24FEB] Test Tubes S

· · 题解

题解：P10191 [USACO24FEB] Test Tubes S

前言

小小思维题。

题意简述

你有三个栈，每次可以将一个栈顶端所有颜色相同的数移动到另外一个栈顶。\ 最开始只有第一个和第二个栈有数，并且只有两种。求让第一个栈和第二个栈中的数都相同的最小操作数，并给出操作方法（并且需要保证第三个栈中没有数）。

思路

这里令三个栈分别为 A,B,C 其 \text{top} 分别为 ida,idb,idc。

注意到每次移动只能将连续的相同颜色的数移动，那么我们就把连续相同颜色的数捆在一起。这样可以方便我们的操作。

那么如果我们将某个栈顶移动到的另外一个栈顶，且它们颜色相同，可以视作弹出了前者的栈顶。

于是有个重要结论，C 中只可能有 1 个数，且永远不会变。

证明如下：

可能不太严谨。首先如果 A,B 的栈顶相同时，我们不会用到 C 直到出现它们两栈顶不同。然后我们将其中大小更大的栈的栈顶丢到 C 里（至于为什么是更大的，我们在后面说）。因为我们去重后，一定颜色是相间的，所以就可以一直进行消除栈顶的操作。

接着是中间的消除过程。

显然如果 A,B 的顶端相同，那么我们可以消除，策略是将大小更大的顶端消除。欸，你会发现这里和上面都是更大的，有什么联系吗？有的，你会发现，我们这样做，可以控制 A,B 栈两者的差尽量接近。当我们 C 中有元素后，我们做上面的操作，就可以把 A,B 两个栈的元素之差控制在 1 以内。至于证明比较显然，你可以自己手动模拟。

但是控制在 1 以内有什么理由吗？如果不控制在 1 之内，就会出现某一个栈空了，但另外一个栈就像夹心蛋糕一样，此时的消除就会花费花费很多额外的代价。而控制在 1 之内就没有这些代价，因为最后的状态十分简洁。

现在就在于处理终止状态。根据上面的操作方法，条件不难得出。

显然终止条件只能是 ida+idb=2。此时栈中的元素一定是尽可能简洁的。

此时分类讨论一波，A 的栈顶和 B 的栈顶是否相同。如果相同，那么一定是 ida=1,idb=1，再加上 C 的贡献就行。

如果不同，就讨论是否 C 中有数，此时有可能 ida=1,idb=1 或者出现其中一个为 2 的情况。

讨论完之后，你就做完了。

CODE

#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back
using namespace std;
constexpr int N=1e5+5;
int n,typ;
int a[N],b[N],c[N];
int ida,idb,idc;
vector<pii>ans;
void solve()
{
    scanf("%d%d",&n,&typ);
    ans.clear(),ida=idb=idc=0;
    for(int i=1,x;i<=n;i++)
    {
        scanf("%1d",&x);
        if(x!=a[ida])a[++ida]=x;
    }
    for(int i=1,x;i<=n;i++)
    {
        scanf("%1d",&x);
        if(x!=b[idb])b[++idb]=x;
    }
    while(ida+idb>2)
    {
        if(ida && idb && a[ida]==b[idb])
        {
            if(ida>=idb)ans.pb(1,2),ida--;
            else ans.pb(2,1),idb--;
            continue;
        }
        if(idc)
        {
            if(ida && a[ida]==c[idc])ans.pb(1,3),ida--;
            else if(idb && b[idb]==c[idc])ans.pb(2,3),idb--;
        }
        else
        {
            if(ida>=idb)ans.pb(1,3),c[++idc]=a[ida--];
            else ans.pb(2,3),c[++idc]=b[idb--];
        }
    }
    if(a[ida]==b[idb])
    {
        ans.pb(1,2);
        if(idc)ans.pb(3,1);
    }
    else if(idc)
    {
        // cerr<<"1:";
        if(ida!=idb)
        {
            // cerr<<"1:";
            if(ida==2)ans.pb(1,2),b[++idb]=a[ida--];
            else ans.pb(2,1),a[++ida]=b[idb--];
        }   
        if(c[idc]==a[ida])ans.pb(3,1);
        else ans.pb(3,2);
    }
    else
    {
        // cerr<<"2:";
        if(ida==2)ans.pb(1,2);
        else if(idb==2)ans.pb(2,1);
    }
    printf("%d\n",(int)ans.size());
    if(typ==1)return;
    for(auto [x,y]:ans)printf("%d %d\n",x,y);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("data.in","r",stdin);
#endif
    int T;scanf("%d",&T);
    while(T--)solve();
    return 0;
}

看在讲的如此详细的份上，点个赞再走吧！