P10191 [USACO24FEB] Test Tubes S

Jerrywang09 · 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;
}