题解 P8866【[NOIP 2022] 喵了个喵】

周子衡 · 2022-12-02 10:49:29 · 题解

好题，为出题人点赞。这里提供一个稍微不一样的做法。

我们先来考虑 k=2n-2 的情形。一个自然的想法是，我们保留一个栈为空，同时其他的栈都至多放 2 个元素。这样的话，每次处理一张牌时，如果这张牌的图案出现在某个栈的顶部，那么我们可以直接扔到该栈栈顶消掉；如果出现在某个栈的底部，那么把这张牌扔到空栈里，然后把两个栈栈底同时消掉；否则扔到某个某个未满的栈里即可。由于至多只有 2n-2 种图案，这样的方法总是行得通的。

接下来考虑 k=2n-1 的情形。上面的做法直接套用会遇到一个问题：可能当前 2n-2 种图案已经把 n-1 个栈都占满了，接下来又出现了剩下的那种图案（记为 u）。此时如果把它扔到空栈里，会让其他栈的栈底弹不出来；如果扔到满的栈上，又会让这个栈的中间元素处境非常尴尬。我们需要灵活处理这样的情况。

解决方案是这样的。记当前所有在栈顶的 n-1 个元素构成集合 S。我们不断扫描之后的图案，直到遇到第一个不在 S 中的图案为止。（注意到由于每个元素在总操作序列中出现的次数都是偶数，故每个元素之后都还会出现至少一次。）

• 如果这个图案就是 u：我们把之前的 u 和现在的 u 都扔到空栈里，它们就消掉了。中间的所有元素都是栈顶，可以直接扔到对应的栈上。
• 如果这个图案不是 u：那么这个图案 v 是某个栈 P 的栈底。记 P 的栈顶为 w，我们来讨论 w 在刚刚扫描过的所有图案中出现次数的奇偶性：
• • 奇数次：我们把 u 扔到空栈里，所有的 w 都扔到 P 里。这样 v 再次出现的时候，P 上面的 u 被清空了，此时可以直接把 v 消掉，P 变成新的空栈。
  • 偶数次：我们把 u 扔到 P 里，所有的 w 也扔到 P 里。这样 v 再次出现的时候，P 中自顶到底分别是 u,w,v 三个元素。把 v 扔进空栈里，再消掉 P 和空栈的栈底，这样就仍然维持了 P 中只有两个元素的条件。
• 这个过程中，其他栈顶元素扔到对应栈顶即可。

这样我们就解决了此题。时间复杂度 O(m)。

一些题外话：如果游戏更改一下规则，例如

• 玩家必须在读入每个图案后就立即决定该图案应该放进那个栈里。

那么 k=2n-1 时很有可能玩家是必败的。这也启示我们在作当前决策时必须考虑之后的图案。考虑到这一点后本题就不是特别棘手了。

#include<cstdio>
#include<vector>

using namespace std;

int up[3000],down[3000],val[3000][2],sz[3000],a[3000000];
int sta[3000];

int main()
{
    //freopen("meow.in","r",stdin);
    //freopen("meow.out","w",stdout);
    int TT=0;scanf("%d",&TT);
    while(TT--)
    {
        int n=0,m=0,k=0;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++)scanf("%d",&a[i]);
        k=2*n-1;
        vector<int> L;for(int i=1;i<n;i++)L.push_back(i);
        vector<pair<int,int> > V;
        int empty=n;
        for(int l=1,r=0;l<=m;l=r+1)
        {
            r=l;int i=l;
            if(down[a[i]])
            {
                int u=down[a[i]];
                V.push_back(make_pair(empty,0));V.push_back(make_pair(u,empty));
                //printf("1 %d\n",empty);printf("2 %d %d\n",u,empty);
                if(sz[u]==2){int v=val[u][1];val[u][0]=v,val[u][1]=0;sz[u]=1;up[v]=0,down[v]=u;L.push_back(u);}
                else{val[u][0]=0;sz[u]=0;}
                down[a[i]]=0;
            }
            else if(up[a[i]])
            {
                int u=up[a[i]];
                V.push_back(make_pair(u,0));
                //printf("1 %d\n",u);
                up[a[i]]=0;sz[u]=1;val[u][1]=0;
                L.push_back(u);
            }
            else if(!L.empty())
            {
                int u=L.back();L.pop_back();
                V.push_back(make_pair(u,0));
                //printf("1 %d\n",u);
                if(sz[u]==0)
                {
                    val[u][0]=a[i];sz[u]=1;down[a[i]]=u;

                    L.push_back(u);
                }
                else
                {
                    val[u][1]=a[i];sz[u]=2;up[a[i]]=u;
                }
            }
            else
            {
                while(r+1<=m)
                {
                    r++;
                    if(a[r]==a[i])
                    {
                        V.push_back(make_pair(empty,0));
                        //printf("1 %d\n",empty);
                        for(int x=l+1;x<r;x++)
                        {
                            V.push_back(make_pair(up[a[x]],0));
                            //printf("1 %d\n",up[a[x]]);
                        }
                        for(int x=l+1;x<r;x++)if(up[a[x]]&&sta[up[a[x]]])
                        {
                            int u=up[a[x]];
                            sta[u]=0;val[u][1]=0;up[a[x]]=0;sz[u]=1;

                            L.push_back(u);
                        }
                        V.push_back(make_pair(empty,0));
                        //printf("1 %d\n",empty);
                        break;
                    }
                    if(down[a[r]])
                    {
                        int u=down[a[r]];
                        if(sta[u])
                        {
                            V.push_back(make_pair(empty,0));
                        //printf("1 %d\n",empty);
                        }
                        else
                        {
                            V.push_back(make_pair(u,0));
                            //printf("1 %d\n",u);
                        }

                        for(int x=l+1;x<r;x++)
                        {
                            V.push_back(make_pair(up[a[x]],0));
                            //printf("1 %d\n",up[a[x]]);
                        }
                        for(int x=l+1;x<r;x++)if(up[a[x]]&&sta[up[a[x]]]&&up[a[x]]!=u)
                        {
                            int u=up[a[x]];
                            sta[u]=0;val[u][1]=0;up[a[x]]=0;sz[u]=1;

                            L.push_back(u);
                        }

                        if(sta[u])
                        {
                            V.push_back(make_pair(u,0));
                            //printf("1 %d\n",u);

                            sta[u]=0;

                            down[val[u][0]]=up[val[u][1]]=0;
                            val[u][0]=val[u][1]=0;sz[u]=0;

                            down[a[l]]=empty;val[empty][0]=a[l];sz[empty]=1;
                            L.push_back(empty);

                            empty=u;
                        }
                        else
                        {
                            V.push_back(make_pair(empty,0));
                            V.push_back(make_pair(u,empty));
                            //printf("1 %d\n",empty);
                            //printf("2 %d %d\n",u,empty);

                            down[val[u][0]]=0;
                            up[val[u][1]]=0;down[val[u][1]]=u;
                            up[a[l]]=u;

                            val[u][0]=val[u][1];val[u][1]=a[l];
                            sz[u]=2;
                        }

                        break;
                    }
                    sta[up[a[r]]]^=1;
                }
            }
        }
        printf("%d\n",V.size());
        for(int i=0;i<V.size();i++)
        {
            if(V[i].second==0)printf("1 %d\n",V[i].first);
            else printf("2 %d %d\n",V[i].first,V[i].second);
        }
    }
}