喵了个喵

云浅知处 · 2023-03-07 07:24:54 · 个人记录

做法貌似和题解都不太一样

Switch on the power line

Remember to put on PROTECTION

Lay down your pieces

And let's begin OBJECT CREATION

Fill in my data parameters INITIALIZATION

Set up our new world

And let's begin the

分类讨论

$k=2n-1$ 时，我们构造一种方案，使得： - 每个栈中只可能有不超过 $2$ 个元素。 - 至少有一个空栈。 - 每种元素只出现一次。 - 栈中总有偶数个元素。考察连续的两个数 $x,y$。 - 若 $x=y$：直接消掉这两个数即可。 - 若 $x,y$ 均未出现过且 $x\neq y$，那么剩下的数最多 $2n-3$ 种，由于栈中只有偶数个元素，那么最多 $2n-4$ 个数，只会占住至多 $n-2$ 个栈，或者 $n-3$ 个满栈与两个不满的栈。接下来，把 $x,y$ 都压入一个空栈内或者两个不满的栈即可。 - $x$ 出现过，$y$ 未出现过：若 $x$ 出现在上面，将 $x,y$ 都压入此时 $x$ 所在的栈顶；否则将 $x$ 压入空栈，消掉两个栈底，再将 $y$ 压入 $x$ 之前所在的栈。 - $x$ 出现过，$y$ 也出现过且 $x\neq y$：分别消掉 $x,y$ 即可。显然不管 $x,y$ 在栈顶还是栈底都可以直接消掉。 - $x$ 未出现，$y$ 出现过，但 $y$ 在栈底：将 $x$ 压入 $y$ 所在栈的栈顶，将 $y$ 压入空栈，消一次栈底。 - $x$ 未出现，$y$ 出现过，但 $y$ 在栈顶： - - 若此时仍存在只压进一个元素的栈，或者存在 $\ge 2$ 个空栈：将 $x$ 压入只压进一个元素的栈或者某个空栈的栈顶，再将 $y$ 消去即可。 - 否则，此时的情况必然是栈中填入了 $2n-2$ 种不同元素，它们填满了 $n-1$ 个栈；考虑后面的每一种数，它们要么出现在栈中的栈顶，要么出现在栈中的栈底，要么是 $x$。我们不断考虑连续的两个数 $p,q$，直到 $p\neq q$，且 $p,q$ 中存在某个数 $=x$ 或者出现在栈底为止。设 $S$ 是从第一个 $y$ 开始算，到第一个满足上述条件之前（不包括它）这些数组成的可重集，那么 $S$ 种的数均不为 $x$ 且全部出现在栈顶。 - $p=x$：将 $x$ 第一次出现时压入空栈，$S$ 中的数压入各自所在原栈的栈顶，最后将 $x$ 消掉。考虑 $p$ 后面那个数 $q$，由于有一个空栈，不管怎样都可以轻松消掉它。若 $q$ 没有出现过，那么此时必定存在只压了一个元素的栈，将 $q$ 压入这个栈即可。 - $p$ 出现在栈底：设 $p$ 所在栈的栈顶为 $r$。 - - 若 $r$ 在 $S$ 中出现奇数次，将 $x$ 压入空栈，令 $r$ 自己消掉，再消掉 $p$ 即可留下一个空栈。考虑 $p$ 后面那个数 $q$，由于有一个空栈，不管怎样都可以轻松消掉它。若 $q$ 没有出现过，那么此时必定存在只压了一个元素的栈，将 $q$ 压入这个栈即可。 - - 若 $r$ 在 $S$ 中出现偶数次，我们先将 $x$ 压入空栈，并将 $r$ 的第一次出现压入 $x$ 栈的栈顶；最后我们用新的 $p$ 消掉 $r$ 下面那个 $p$ 得到空栈，此时不管 $q$ 是什么都可以消掉。 - - 若 $r$ 根本就没有出现过，我们将 $x$ 放在 $r$ 上面，将 $q$ 压入空栈栈底，进行一次消栈即可。 - $q=x$：类似于 $p=x$。 - $q$ 出现在栈底：类似。 ## 代码删去了一些调试语句，只剩下了二百多行。 ```cpp //那便是希望。 #include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ int x=0,f=1;char c=getchar(); for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;} for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15); return x*f; } const int mod=998244353; int ksm(int x,int y,int p=mod){ int ans=1; for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p; return ans%p; } int inv(int x,int p=mod){return ksm(x,p-2,p)%p;} int randint(int l,int r){return rand()*rand()%(r-l+1)+l;} void add(int &x,int v){x+=v;if(x>=mod)x-=mod;} const int N=1005; const int M=2e6+5; int pos[N],h[N],n,m,k,a[M],stk[N][10],top[N],now; vector<pair<int,pair<int,int> > >Ans; set<int>S; set<int>T; multiset<int>SS; bool DEBUG=0; #define fi first #define se second #define mk make_pair void Push(int p,int x){ if(DEBUG)cout<<"Push "<<p<<" "<<x<<endl; Ans.emplace_back(mk(1,mk(p,-1)));if(top[p]==0)S.erase(p);if(top[p]==1)T.erase(p); ++top[p];stk[p][top[p]]=x,pos[x]=p,h[x]=top[p]; if(top[p]>1&&x==stk[p][top[p]-1])pos[x]=h[x]=-1,top[p]-=2; if(!top[p])S.insert(p);if(top[p]==1)T.insert(p); } void Erase(int p,int q){ Ans.emplace_back(mk(2,mk(p,q))); if(DEBUG)cout<<"Erase "<<p<<" "<<q<<endl; if(top[p]==1)T.erase(p);if(top[q]==1)T.erase(q); assert(top[p]>=1&&top[q]>=1&&stk[p][1]==stk[q][1]); int x=stk[p][1];top[p]--,top[q]--,pos[x]=-1,h[x]=-1; if(!top[p])S.insert(p);if(!top[q])S.insert(q); if(top[p]==1)T.insert(p);if(top[q]==1)T.insert(q); for(int i=1;i<=top[p];i++)stk[p][i]=stk[p][i+1]; for(int i=1;i<=top[q];i++)stk[q][i]=stk[q][i+1]; for(int i=1;i<=top[p];i++)h[stk[p][i]]=i; for(int i=1;i<=top[q];i++)h[stk[q][i]]=i; } void solve2(){ SS.clear();for(int i=1;i<n;i++)SS.insert(i),SS.insert(i); for(int i=1;i<=n;i++)top[i]=0; now=1;for(int i=1;i<=k;i++)pos[i]=h[i]=-1; while(now<=m){ int x=a[now++]; if(pos[x]!=-1){ int p=pos[x]; if(h[x]==1)Push(n,x),Erase(n,p),SS.insert(p); else Push(p,x),SS.insert(p); } else{ int p=*SS.begin(); Push(p,x);SS.erase(SS.find(p)); } } cout<<Ans.size()<<'\n'; for(auto t:Ans){ cout<<t.fi<<" "<<t.se.fi; if(t.fi==1)puts(""); else cout<<" "<<t.se.se<<'\n'; } } bool vis[N]; vector<pair<int,int> >tmp; void solve(){ Ans.clear();n=read(),m=read(),k=read(); for(int i=1;i<=m;i++)a[i]=read(); if(k==2*n-2){solve2();return ;} S.clear(),T.clear(),Ans.clear(),tmp.clear();for(int i=1;i<=n;i++)S.insert(i); for(int i=1;i<=n;i++)top[i]=0; now=1;for(int i=1;i<=k;i++)pos[i]=h[i]=-1; while(now+1<=m){ assert(T.size()%2==0); int x=a[now++],y=a[now++]; if(x==y){Ans.emplace_back(mk(1,mk(1,-1))),Ans.emplace_back(mk(1,mk(1,-1)));continue;} assert(!S.empty()); if(pos[x]==-1&&pos[y]==-1){assert(S.size()>=2||T.size()>=2); if(S.size()>=2){int p=*S.begin();Push(p,x),Push(p,y);} else if(T.size()>=2){auto q=T.begin();auto r=q;++r;int qq=*q,rr=*r;Push(qq,x),Push(rr,y);} } else if(pos[x]==-1&&pos[y]!=-1){ if(h[y]==1){ Push(pos[y],x);int p=*S.begin(); int q=pos[y];Push(p,y),Erase(p,q); } else if(h[y]==2){ if(S.size()>=2){int p=pos[y],q=*S.begin();Push(q,x),Push(p,y);continue;} else if(T.size()>=2){auto q=T.begin();int qq=*q,rr=pos[y];Push(qq,x),Push(rr,y);continue;} else if(S.size()==1){ tmp.clear();tmp.emplace_back(mk(y,pos[y])),vis[y]^=1; while(1){ int c=a[now++],d=a[now++]; if(c==d){tmp.emplace_back(mk(c,-1)),tmp.emplace_back(mk(d,-1));continue;} if(c==x){ int p=*S.begin();Push(p,x); for(auto t:tmp){ if(t.se==-1)Ans.emplace_back(mk(1,mk(1,-1))); else Push(t.se,t.fi); } Push(p,x);assert(d!=x);assert(top[p]==0); if(pos[d]==-1){assert(!T.empty());int r=*T.begin();Push(r,d);} else if(h[d]==2)Push(pos[d],d); else if(h[d]==1){int q=pos[d];Push(p,d),Erase(p,q);} for(auto t:tmp)vis[t.fi]=0;break; } else if(h[c]==1){ int cc=stk[pos[c]][2]; int p=*S.begin(); bool ext=0;for(auto t:tmp)ext|=(t.fi==cc&&t.se!=-1); if(ext)Push(p,x); else Push(pos[c],x); int chk=0; for(auto t:tmp)if(t.fi==cc&&t.se!=-1&&(!vis[cc]))chk++; for(auto t:tmp){ if(t.se==-1)Ans.emplace_back(mk(1,mk(1,-1))); else if(t.fi==cc&&(!vis[cc])){ chk--; if(chk==0)Push(p,t.fi); else Push(t.se,t.fi); } else Push(t.se,t.fi); } int qq=pos[c]; if(ext)Push(pos[c],c); else Push(p,c),Erase(p,qq); assert(!S.empty());p=*S.begin(); if(pos[d]==-1){assert(!T.empty());int r=*T.begin();Push(r,d);} else if(h[d]==2)Push(pos[d],d); else if(d!=x){int r=pos[d];Push(p,d),Erase(p,r);} else{int r=pos[d];Push(p,d),Erase(p,r);} for(auto t:tmp)vis[t.fi]=0;break; } else if(d==x){ tmp.emplace_back(mk(c,pos[c])),vis[c]^=1; int p=*S.begin();Push(p,x); for(auto t:tmp){ if(t.se==-1)Ans.emplace_back(mk(1,mk(1,-1))); else Push(t.se,t.fi); } Push(p,x); for(auto t:tmp)vis[t.fi]=0;break; } else if(h[d]==1){ tmp.emplace_back(mk(c,pos[c])),vis[c]^=1; int dd=stk[pos[d]][2]; int p=*S.begin(); bool ext=0;for(auto t:tmp)ext|=(t.fi==dd&&t.se!=-1); if(ext)Push(p,x); else Push(pos[d],x); int chk=0; for(auto t:tmp)if(t.fi==dd&&t.se!=-1&&(!vis[dd]))chk++; for(auto t:tmp){ if(t.se==-1)Ans.emplace_back(mk(1,mk(1,-1))); else if(t.fi==dd&&(!vis[dd])){ chk--; if(chk==0)Push(p,t.fi); else Push(t.se,t.fi); } else Push(t.se,t.fi); } int qq=pos[d]; if(ext)Push(pos[d],d); else Push(p,d),Erase(p,qq); for(auto t:tmp)vis[t.fi]=0;break; } else tmp.emplace_back(mk(c,pos[c])),tmp.emplace_back(mk(d,pos[d])),vis[c]^=1,vis[d]^=1; } } } } else if(pos[x]!=-1&&pos[y]==-1){ if(h[x]==1){int p=*S.begin(),q=pos[x];Push(p,x),Erase(p,q),Push(q,y);} else if(h[x]==2){int p=pos[x];Push(p,x),Push(p,y);} } else if(pos[x]!=-1&&pos[y]!=-1){ int p=pos[x],q=pos[y],r=*S.begin(); if(x==y){ if(h[x]==1)Push(r,x),Erase(r,p),Push(p,x); else Push(p,x),Push(p,x); continue; } if(h[x]==1)Push(r,x),Erase(r,p); else if(h[x]==2)Push(p,x); if(h[y]==1)Push(r,y),Erase(r,q); else if(h[y]==2)Push(q,y); } } cout<<Ans.size()<<'\n'; for(auto t:Ans){ cout<<t.fi<<" "<<t.se.fi; if(t.fi==1)puts(""); else cout<<" "<<t.se.se<<'\n'; } } signed main(void){ // freopen("meow.in","r",stdin); // freopen("meow.out","w",stdout); int tt=read();while(tt--)solve(); return 0; } ```