P8866[NOIP2022] 喵了个喵 题解

__vector__ · 2023-05-10 17:55:37 · 个人记录

• 对于 k = 2n - 2

  由于中间的元素很难消掉，考虑维持每个栈大小不超过 $2$。 这样只需要 $\frac{2n-2}{2}=n-1$ 个栈，还空出了一个栈作为备用。 然后依次处理牌堆，设当前牌堆顶为 $x$： 若 $x$ 还没在任何一个栈出现过，那么将 $x$ 随便丢到一个大小不超过 $1$ 的栈。如果 $x$ 已经出现过，那么看 $x$ 的那个同类牌处于栈顶还是栈底，如果处于栈顶，那么将 $x$ 丢到同类牌所在的栈，直接相消，如果处于栈底，则将 $x$ 丢到备用栈，然后 2 操作将备用栈与 $x$ 同类牌所处的栈的底相消。

• 对于 k = 2n-1
  多出了一种颜色，得换换思路。
  可以考虑预知牌堆顶后面的牌，作出决策。
  从上到下依次枚举牌 i， 先尝试按照 k=2n-2 的方法家加入牌 i，如果成功没问题，换下一个，如果失败了，那么使用新的策略。
  设当前牌堆顶为 p（显然 p 就是 i）。
  向后枚举 x。
  若 x 的同类牌在栈顶，那么直接将 x 扔到对应栈顶就行。
  若 x 等于 p，这 x,p 随便消一下就行了，然后从 x 的下一个牌重新开始。
  如果 x 的同类牌在栈底，设 x 的同类牌所在栈为 s，s 栈顶为 y 那么分类讨论以下：
  若 y 在 p 和 x 之间出现了奇数次，那么 y 必然被消掉，所以先把 p 丢进备用栈，然后 p 到 x 之间的牌全丢进对应的栈，最后把 x 丢进栈 s，这样栈 s 就变成了空栈，也就是说备用栈换成了 s。
  若 y 在 sp 和 x 之间出现了偶数次，那么把 p 丢到 s 上，把这偶数个 y 丢到备用栈上全部消掉，然后把 x 放到备用栈上，使用 2 操作将备用栈与 s 的栈底相消。
  执行完以上两种分类讨论任意一种之后，从 x 下一张牌牌重新开始。

本题最后按照 k=2n-1 的方案执行即可。

Code

const int maxn = 305;
const int maxk = maxn*2;
const int maxm = 2e6+5;
int T;
int n,m,k;
int a[maxm];
deque<int> stk[maxn];
int id[maxk];
vector<pii> ans;
int sp;
deque<int> empt;
void op1(int idx)
{
    ans.emplace_back(mkpr(idx,0));
}
void op2(int idx1,int idx2)
{
    ans.emplace_back(mkpr(idx1,idx2));
}
bool add(int x)
{
    int idx=id[x];
    if(!idx)
    {
        if(empt.empty())return false;
        id[x]=idx=empt.front();
        empt.pop_front();
        stk[idx].push_back(x);
        op1(idx);
    }
    else
    {
        id[x]=0;
        empt.push_back(idx);
        if(stk[idx].back()==x)
        {
            stk[idx].pop_back();
            op1(idx);
        }
        else
        {
            stk[idx].pop_front();
            op1(sp);
            op2(sp,idx);
        }
    }
    return true;
}
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        read(m);
        read(k);
        FOR(i,1,m)read(a[i]);
        sp=n;
        FOR(i,1,n-1)
        {
            empt.push_back(i);
            empt.push_back(i);
        }
        int i=1;
        while(i<=m)
        {
            if(!add(a[i]))
            {
                int r=i+1;
                int p=a[i];
                int x=a[r];
                while(1)
                {
                    if(r>m)break;
                    if(x==p)break;
                    if(stk[id[x]].back()!=x)break;
                    r++;
                    x=a[r];
                }
                if(x==p)
                {
                    op1(sp);
                    FOR(j,i+1,r-1)
                    {
                        add(a[j]);
                    }
                    op1(sp);
                }
                else
                {
                    int idx=id[x];
                    int stktop=stk[idx].back();
                    bool even=1;
                    FOR(j,i+1,r-1)
                    {
                        even^=(a[j]==stktop);
                    }
                    if(even)
                    {
                        op1(idx);
                        stk[idx].push_back(p);
                        FOR(j,i+1,r-1)
                        {
                            if(a[j]==stktop)
                            {
                                op1(sp);
                            }
                            else
                            {
                                add(a[j]);
                            }
                        }
                        op1(sp);
                        op2(sp,idx);
                        stk[idx].pop_front();
                        id[x]=0;
                        id[p]=idx;
                    }
                    else
                    {
                        op1(sp);
                        stk[sp].push_back(p);
                        FOR(j,i+1,r-1)
                        {
                            if(a[j]==stktop)
                            {
                                op1(idx);
                            }
                            else add(a[j]);
                        }
                        op1(idx);
                        stk[idx].clear();
                        id[x]=id[stktop]=0;
                        id[p]=sp;
                        empt.push_back(sp);
                        sp=idx;

                    }
                }
                i=r+1;
            }
            else
                i++;
        }
        printf("%d\n",(int)ans.size());
        for(pii v:ans)
        {
            if(v.second)printf("%d %d %d\n",2,v.first,v.second);
            else printf("%d %d\n",1,v.first);
        }
        // clean
        empt.clear();
        ans.clear();
        FOR(i,1,n)
        {
            stk[i].clear();
        }
        FOR(i,1,k)
        {
            id[i]=0;
        }
    }
    return 0;
}