LGP8866 [NOIP 2022] 喵了个喵 学习笔记
\(\texttt{Luogu Link}\)
前言
史。无需多言。
本笔记也许参考了这篇题解。对于一道构造题来说，此解析写的确实认真负责，配最高赞。
题意简述
小 \(\texttt{E}\) 喜欢上了一款叫做《喵了个喵》的游戏。
：小 \(\texttt{E}\) 能别整些有的没的了吗。
：别急，小 \(\texttt{E}\) 的整活（人）巅峰还在 \(\texttt{NOIP 2022}\) 半年之后的省选。
这个游戏有一个初始 \(m\) 张牌的牌堆和 \(n\) 个可以从栈底删除元素的初始为空的栈（即双端队列）。卡牌有 \(k\) 种图案（颜色），牌堆里每种图案的卡都有偶数张。这个游戏有两种操作：
- 选择一个栈，将牌堆顶上的卡牌放入栈的顶部。如果这么操作后，这个栈最上方的两张牌有相同的图案，则会自动将这两张牌消去。
- 选择两个不同的栈，若这两个栈栈底的卡牌图案相同，则可以将这两张牌消去，原来在栈底上方的卡牌会成为新的栈底。
牌堆内的每一张卡牌都是已知的。对于此游戏给出一个合法操作序列可以消去所有卡牌。
多测。\(\sum m\le 2\times 10^6\)，\(n\le 300\)。
特别地，\(15\text{pts}\) 的数据满足 \(k=2n-2\)，其余 \(85\text{pts}\) 的数据满足 \(k=2n-1\)。
做法解析
显然由部分分可得，我们先思考 \(k=2n-2\) 的情形。
\(2n-2\) 这个数字给的就很好。它意味着我们如果给每两个颜色都分配一个栈去处理，最后就刚好还有一个空栈。再考虑到一个栈里能把牌消掉的方式也是刚好两种，操作方案就呼之欲出了：我们把 \(i\) 和 \(i+n-1\) 分配到 \(i\) 号栈。具体来说，对于每次从牌堆顶拿的卡牌，若其分配的栈中不存在和它相同的卡牌，则直接放进去；否则若有和它相同的卡牌在堆底，则将它自身放进空栈并执行栈底消除；否则若有和它相同的卡牌在栈顶，则将它直接放上去执行栈顶消除。所以 \(15\text{pts}\) 是很简单的。
思考 \(k=2n-1\)。此时和 \(k=2n-2\) 的区别在于不一定永远存在一个空栈了，当然我们仍然尝试在大多数时候保持 \(k=2n−2\) 做法的特性，即 \(n−1\) 个栈仅保存两种元素并且剩余一个栈为空，可以吗？
当整个局面已经存在了 \(2n-2\) 个元素，且出现了第 \(2n-1\) 号颜色，我们要把它放哪儿呢？你发现有些情况我们直接把它放辅助栈即可，有时候我们得把它放到某个栈顶以便后续有栈底消执行。也就是说，后面的颜色会影响我们当前对 \(2n-1\) 号颜色的决策，我们得开个辉眼。
一时兴起了。
当然，只要局面上只有不大于 \(2n-2\) 种颜色需要考虑，我们就可以沿用 \(k=2n-2\) 的策略。而当出现了第 \(2n-1\) 种颜色（不一定是编号上的 \(2n-1\)，而是指场面上同时集齐了 \(2n-1\) 种颜色）的一个元素 \(a_l=u\) 时，我们就要看看之后出现的颜色。
首先，我们找到 \(l\) 后第一个满足 \(c_r\) 颜色不在栈顶的元素（显然 \((l,r)\) 中的元素因为有现在栈顶的元素和它同色，所以基本上可以简单消除）。若 \(c_r=c_l=u\)，则我们直接把 \(c_l\) 和 \(c_r\) 都扔辅助栈即可。否则 \(c_r=v\neq u\)，就意味着我们要消掉某个栈 \(s\) 当前栈底的元素。记当前待在 \(s\) 栈顶的元素为 \(a\)，则我们又要根据 \(a\) 在 \((l,r)\) 中出现次数的奇偶性做个分讨（此时 \((l,r)\) 的 \(a\) 不能走简单消）。
此处 \((l,r)\) 即为 \([l+1,r-1]\) 的意思。
如果出现奇数次，说明带上局面中本来就有的 \(a\) 就是偶数个了，可以两两消除，这意味着到了 \(r\) 时 \(a\) 可以被消干净了，我们把 \(c_r\) 往 \(s\) 一扔，就和原本处于栈底的 \(v\) 消掉了，此时 \(s\) 就空出来了，我们又有了一个空栈可作辅助栈，于是就可以放心把 \(c_l=u\) 扔到当前辅助栈里。
如果出现偶数次，说明后来的 \(a\) 可以两两消除，而局面上这个 \(a\) 仍然存在，我们必须走栈底消 \(v\)。于是，我们把 \(c_l=u\) 扔到 \(s\) 上，\((l,r)\) 中那偶数次出现的 \(a\) 扔到辅助栈里。这样考虑 \(c_r\) 时辅助栈仍然是空的，我们把 \(c_r\) 扔进去并栈底消除，之后辅助栈还是空的并且 \(s\) 中的元素数量也回到了两个，保持了可维护的状态。
代码实现
对于 \(k\le 2n-2\) 的局面，我们做简单的处理 regu。用队列存放当前有位置增添颜色的栈，用双端队列模拟栈的真实情况，用数组 id 记录每种颜色存在于哪个栈中。
后面 \(k=2n-1\) 的策略是好写的。
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=3e2+5,MaxM=2e6+5;
int N,M,K,C[MaxM],id[MaxN<<1],ex;
vector<pii> ans;
void apu(int s){ans.push_back({s,0});}
void abo(int s,int t){ans.push_back({s,t});}
queue<int> q;deque<int> stk[MaxN];
bool regu(int u){int s=id[u];if(!s){if(q.empty())return false;id[u]=s=q.front(),q.pop();apu(s),stk[s].push_back(u);}else{id[u]=0;q.push(s);if(u==stk[s].back())apu(s),stk[s].pop_back();else apu(ex),abo(ex,s),stk[s].pop_front();}return true;
}
void befinit(int n){ans.clear();fill(id,id+n*2+1,0);ex=n;while(!q.empty())q.pop();for(int i=1;i<N;i++)q.push(i),q.push(i);
}
void mian(){readis(N,M,K);befinit(N);for(int i=1;i<=M;i++)readi(C[i]);for(int l=1,r,u,v;l<=M;l=r+1){r=l,u=C[l];if(regu(u))continue;do{r++,v=C[r];}while(r<=M&&v!=u&&stk[id[v]].back()==v);if(u==v){apu(ex);for(int i=l+1;i<r;regu(C[i]),i++);apu(ex);continue;}int s=id[v],a=stk[s].back(),kk=0;for(int i=l+1;i<r;i++)kk^=(C[i]==a);if(kk){apu(ex),stk[ex].push_back(u);for(int i=l+1;i<r;i++){if(C[i]==a)apu(s);else regu(C[i]);}apu(s),stk[s].clear();id[a]=id[v]=0,id[u]=ex,q.push(ex),ex=s;}else{apu(s),stk[s].push_back(u);for(int i=l+1;i<r;i++){if(C[i]==a)apu(ex);else regu(C[i]);}apu(ex),abo(ex,s),stk[s].pop_front();id[v]=0,id[u]=s;}}writil(ans.size());for(auto [x,y] : ans){if(y)printf("2 %d %d\n",x,y);else printf("1 %d\n",x);}
}
int Tcn;
int main(){readi(Tcn);while(Tcn--)mian();return 0;
}