自动搬运

查看原文

来自洛谷，原作者为

	Jerrywang09 Пусть сильнее грянет буря!

搬运于2025-08-24 22:55:36，当前版本为作者最后更新于2024-10-06 21:12:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题看上去毫无头绪，其实考察的是乱搞的勇气。

第一步想到去重。然后用三个栈维护三个试管 $a,b,c$。然后怎么搞呢？

先考虑一些平凡的情况。如果 $a$ 的栈顶和 $b$ 的栈顶相同，则根据两个栈的大小，选择消去 $a$ 的栈顶或 $b$ 的栈顶。如果 $c$ 为空，则选择 $a,b$ 中较大的一个栈，弹出栈顶，放入 $c$ 试管中。如果 $a,c$ 或 $a,b$ 的栈顶相同，则可以消去 $a$ 或 $b$ 的栈顶。

不难发现，上述过程只有在 $c$ 为空时才会加入，因此 $c$ 的栈内元素个数不超过 $1$。

再考虑一些边界。如果 $a,b$ 大小都为 $1$ 且两个栈顶元素不同，则要把 $c$ 清空，大功告成。如果 $a,b$ 中有一个为空，假设 $a$ 为空。如果 $b$ 只有一个元素了，把 $c$ 倒给 $a$，大功告成。否则弹出 $b$ 的栈顶给 $a$。$b$ 为空的情况同理。

看上去上述策略都很符合直觉，但我感觉赛时很难写出代码。

// Title:  Test Tubes
// Source: USACO24FEB Silver
// Author: Jerrywang
#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define ll long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cerr<<#x<<":"<<x<<endl;
const int N=1000010;
using namespace std;

int n, p; pii res[N]; int cnt=0;

void solve()
{
    cnt=0; scanf("%d%d", &n, &p);
    stack<int> a, b, c;
    rep(i, 1, n)
    {
        int x; scanf("%1d", &x);
        if(a.empty() || x!=a.top()) a.push(x);
    }
    rep(i, 1, n)
    {
        int x; scanf("%1d", &x);
        if(b.empty() || x!=b.top()) b.push(x);
    }
    while(1)
    {
        if(a.size()==1 && b.size()==1 && a.top()!=b.top())
        {
            if(c.empty()) break;
            if(a.top()==c.top()) res[++cnt]={3, 1};
            if(b.top()==c.top()) res[++cnt]={3, 2};
            break;
        }
        if(a.empty())
        {
            if(b.size()==1) {res[++cnt]={3, 1}; break;}
            a.push(b.top()), b.pop(), res[++cnt]={2, 1};
        }
        else if(b.empty())
        {
            if(a.size()==1) {res[++cnt]={3, 2}; break;}
            b.push(a.top()), a.pop(), res[++cnt]={1, 2};
        }
        else if(a.size() && b.size() && a.top()==b.top())
        {
            if(a.size()>b.size()) a.pop(), res[++cnt]={1, 2};
            else b.pop(), res[++cnt]={2, 1};
        }
        else if(c.empty())
        {
            if(a.size()>b.size()) c.push(a.top()), a.pop(), res[++cnt]={1, 3};
            else c.push(b.top()), b.pop(), res[++cnt]={2, 3};
        }
        else if(a.size() && a.top()==c.top())
            a.pop(), res[++cnt]={1, 3};
        else if(b.size() && b.top()==c.top())
            b.pop(), res[++cnt]={2, 3};
    }
    printf("%d\n", cnt);
    if(p>1) rep(i, 1, cnt) printf("%d %d\n", res[i].F, res[i].S);
}

int main()
{
    #ifdef Jerrywang
    freopen("E:/OI/in.txt", "r", stdin);
    #endif
    int T; scanf("%d", &T);
    while(T--) solve();
    
    return 0;
}