双栈排序[并查集]

双栈排序[并查集]

分析

网上很多人用二分图染色,但是并查集来判断冲突性也是极好的

首先,单栈排序有这么一个性质

网上有个证明(原网​​javascript:void(0)​​)

能判定之后

我们令x_1表示x放在1里面

如果存在x

我们合并x_1,y_2

如果在合并时发现x_1 y_1在一个集合,那就有冲突了

f[n+1]=0x3fffffff; for(int i=n;i>=1;i--) f[i]=min(f[i+1],a[i]); for(int i=1;if[j+1]){ int x1=find(i),x2=find(i+n),y1=find(j),y2=find(j+n); if(x1==y1){cout<<"0";return 0;} if(x2==y2){cout<<"0";return 0;} fa[x1]=y2,fa[x2]=y1; } }

因为题目要求字典序最小,所以对于没有约束的点,我们把它放在第一个栈(0表示第一个栈)

有约束的点的栈是确定的

#include#define N 1005using namespace std;int fa[N*2],Belong[N];int n,a[N],f[N],now=1;int read(){ int cnt=0;char ch=0; while(!isdigit(ch))ch=getchar(); while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar(); return cnt;}int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}int main(){ n=read(); for(int i=1;i<=2*n;i++) fa[i]=i; for(int i=1;i<=n;i++) a[i]=read(); f[n+1]=0x3fffffff; for(int i=n;i>=1;i--) f[i]=min(f[i+1],a[i]); for(int i=1;if[j+1]){ int x1=find(i),x2=find(i+n),y1=find(j),y2=find(j+n); if(x1==y1){cout<<"0";return 0;} if(x2==y2){cout<<"0";return 0;} fa[x1]=y2,fa[x2]=y1; } } memset(Belong,-1,sizeof(Belong)); Belong[1]=0; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ if(find(i)==find(j)) Belong[j]=Belong[i]; else if(find(i+n)==find(j)||find(j+n)==find(i)) Belong[j]=Belong[i]^1; else if(Belong[j]==-1) Belong[j]=0; } stack S1; stack S2; for(int i=1;i<=n;i++){ if(Belong[i]==0) S1.push(a[i]),cout<<"a "; else S2.push(a[i]),cout<<"c "; while((!S1.empty()&&S1-()==now)||(!S2.empty()&&S2-()==now)){ if(!S1.empty()&&S1-()==now) S1.pop(),cout<<"b "; else S2.pop(),cout<<"d ";now++; } }return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。