Meow 题解

· · 题解

消除的基本策略

假定当前牌堆顶的牌的种类为 x，现在场上也有至少一张种类为 x 的牌，然后我们想把这张牌直接消掉。

在以下的策略中如果场上有两张相同的牌，我们一定会立刻将它们消掉，所以同种类的牌于此条件下在场上只能出现一次。假定场上另一张种类为 x 的牌位于栈 p_x 中。

（以下同颜色代表同种类的牌）

第一种操作示例：

第二种操作示例：

不难发现如果一个栈里有不少于三张牌的话，那么位于中间的那一张是不容易被消掉的，而 k 的范围在 2n 左右，这启发我们尽可能使每个栈含有不超过两张牌。

k=2n-2

策略1：存在一个编号为 sp 的空栈，且当前牌堆顶的牌在场上存在 或 其余栈中存在至少一个栈大小不超过 1：

由于只有 k=2n-2 种卡牌，我们可以保证即使前 n-1 个栈均含有两张卡牌时，牌堆顶的牌也一定会在场上出现过，可以重复按照策略1执行。令 n 号栈为 sp 空栈，便可保证第二种消除基本策略的执行。

k=2n-1

现在多了一种牌，所以策略1不一定每次都能奏效了。

那么考虑如何安置多出来的这一种牌。我们再看牌堆顶的下一张牌，如果这张牌的同类牌出现在栈底（不妨设对应栈编号为 p），那么不难得出可以将牌堆顶的牌放到栈 p 上，然后将下一张牌放到栈 sp 里，最后对栈 p 和 sp 执行一次操作2便可安置。

但是如果下一张牌的同类牌在栈顶的话，我们可以无脑将牌堆顶的牌放到栈 sp 上吗？显然不可以：

既然消除的关键还是栈底的牌，所以我们可不可以拓宽一下视野，往后看有没有位于底部的牌，然后将牌堆顶的牌放到对应栈顶呢？

貌似很行，对吧。

还是不行。牌堆顶的牌阻挡了原栈顶的牌，使得它们不能互相消除。

但如果我们改为将牌堆顶的牌放到 sp 里....

这样反而行得通了，唯一的区别就是 sp 换了一下。

那么两者的区别是什么呢？仔细观察就可以发现：

什么情况下栈顶元素会被消去？结合上述图思考一下便可得知：

至于这两张牌之间的所有牌，由于它们都出现在栈顶出现，所以直接将其分别放在对应栈上即可。（当然一些牌会出现多次，在这种情况下为了方便，可以每次都将其放在同样的位置。）

于是策略便逐渐明朗起来：

策略 Meow：存在一个编号为 sp 的空栈，且不满足策略1条件。

首先记录此时每类牌所在的栈编号和是否位于栈顶，记 p_i 此时牌 i 同类的牌所位于的栈编号，t_i=1 代表此时牌 i 同类的牌位于栈顶。

然后从牌堆顶的下一张开始，逐个向后判断。设当前判断的牌为 x。

当然，由于将牌加入至栈的过程是有序的，所以在实现上会有些许不同。（例如，可以先找到 x 在哪里，然后根据信息判断牌堆顶的牌应放置在哪里，最后将牌堆顶之后的牌加入栈。）

重复执行策略1和策略 Meow，最终所有的牌均可以被消掉。这样我们也可以证明所有合法的初始配置均有解。

整体操作示例

对于操作次数：我们会执行恰好 m 次操作1，而每次操作2会消除两张牌，由于操作1执行过程中也会消去牌，因此 2m 张牌至多使用 m 次操作2即可全部消除，于是总操作次数不超过 m+m=2m，符合条件。

数据范围较大（\sum m\le 2\times 10^6），所以需要注意复杂度和常数。

代码实现的细节和注意事项

维护信息

你需要维护：

当然你也可以维护更多的信息，例如每种牌是否位于栈顶或栈底等。

操作函数

由于需要涉及到很多情况，所以建议将操作写进一个函数以减少代码量。

以下为一种写法：

void change(int x,int y){
    ans.push_back({x,y});
    if(y==0){//y=0代表为操作1
        ...//操作1
    }
    else{
        ...//操作2
    }
}
...
change(4,0);//将牌堆顶的牌加入栈4
change(1,2);//对栈1和栈2执行操作2

你也可以在这个函数里进行对维护信息的修改。

#include<bits/stdc++.h>
using namespace std;
ifstream fin("meow.in");
ofstream fout("meow.out");
#define cin fin
#define cout fout
int a[2000005],p[1000],b[1005];
deque<int>q[1000];
vector<pair<int,int>>ans;
int pos=1,sz;
int cnt[1005];
queue<int>pq0;
void change(int x,int y){
    ans.push_back({x,y});
    if(y==0){
        pq0.push(x);
        if(!q[x].empty() and q[x].back()==a[pos]){
            q[x].pop_back();
            cnt[a[pos]]--;
            if(cnt[a[pos]]==0)sz--,p[a[pos]]=0;
            if(q[x].empty())b[a[pos]]=0;
        }
        else{
            q[x].push_back(a[pos]);
            if(cnt[a[pos]]==0){
                sz++,p[a[pos]]=x;
            }
            cnt[a[pos]]++;
            if(q[x].size()==1)b[a[pos]]=1;
        }
        pos++;
    }
    else{
        pq0.push(x);
        pq0.push(y);
        if(q[x].front()==q[y].front()){
            b[q[x].front()]=0;
            cnt[q[x].front()]-=2;
            if(cnt[q[x].front()]==0){
                sz--,p[q[x].front()]=0;
                b[q[x].front()]=0;
            }
            q[x].pop_front();
            q[y].pop_front();

            if(!q[x].empty())b[q[x].front()]=1;
            if(!q[y].empty())b[q[y].front()]=1;
        }
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        pos=1;
        sz=0;
        memset(p,0,sizeof p);
        memset(b,0,sizeof b);
        ans.resize(0);
        int n,m,k;
        cin>>n>>m>>k;
        int sp=n;

        while(!pq0.empty())pq0.pop();
        for(int i=1;i<=n;i++){
            if(i!=sp)pq0.push(i);
        }
        int ap[k+5]={0};
        for(int i=1;i<=m;i++){
            cin>>a[i];
            a[i+1]=0;
        }
        for(int i=1;i<=m;i++){
            if(sz==2*(n-1) and !cnt[a[i]]){
                int ti=i;
                for(int j=i+1;j<=m;j++){
                    if(a[j]==a[i]){
                        for(int w=i+1;w<=j;w++){
                            ap[a[w]]=p[a[w]];
                        }
                        change(sp,0);
                            for(int w=i+1;w<=j;w++){
                                if(a[w]==a[i])change(sp,0);
                                else change(ap[a[w]],0);
                            }

                        i=j;
                        break;
                    }
                    if(b[a[j]]){
                        if(ap[q[p[a[j]]].back()]){
                            for(int w=i+1;w<=j;w++){
                                ap[a[w]]=p[a[w]];
                            }
                            change(sp,0);
                            sp=p[a[j]];
                            for(int w=i+1;w<=j;w++){
                                change(ap[a[w]],0);
                            }

                        }
                        else{
                            for(int w=i+1;w<=j;w++){
                                ap[a[w]]=p[a[w]];
                            }
                            change(p[a[j]],0);
                            for(int w=i+1;w<j;w++){
                                change(ap[a[w]],0);
                            }
                            change(sp,0);
                            change(sp,p[a[j]]);
                        }
                        i=j;
                        break;
                    }
                    else{
                        ap[a[j]]^=1;
                    }
                }
                for(int j=ti;j<=i;j++){
                    ap[a[j]]=0;
                }
                continue;
            }
            if(p[a[i]]){
                if(q[p[a[i]]].back()==a[i]){
                    change(p[a[i]],0);
                }
                else{
                    change(sp,0);
                    change(sp,p[a[i]]);
                }
            }
            else{
                while(!pq0.empty() and (pq0.front()==sp or q[pq0.front()].size()>=2)){
                    pq0.pop();
                }
                change(pq0.front(),0);
            }
        }

        cout<<ans.size()<<endl;

        for(auto it:ans){
            if(it.second==0)cout<<1<<' '<<it.first<<'\n';
            else cout<<2<<' '<<it.first<<" "<<it.second<<'\n';
        }
        assert(pos==m+1);
        for(int i=1;i<=n;i++){
            assert(q[i].empty());
        }
    }
}