subject
Problem solution
The key to this problem is to analyze whether two numbers can be on the same stack
According to this logic, the general idea of this topic is:
If a number xxx, 111~(x − 1)(x-1)(x − 1) has been popped up, then xxx will pop up, otherwise xxx will remain in the stack, and all subsequent numbers larger than him cannot enter the stack. If a number yyy wants to enter and finds that the top of both stacks is smaller than him, then this method will not work.
So I < J, AI < Aji < J, a_ {i}<a_ {j} When I < J, AI < AJ , I, Ji, Ji and J can be on the same stack.
So for I < J, AI < Aji < J, a_ {i}<a_ {j} When can I < J, AI < AJ be on the same stack? It is said that the order of stacks decreases, so how can it be on the same stack? The only case is that iii has been out of the stack before jjj enters.
But if there is a number after jjj than aia_{i}ai: I can't do it when I'm young?
So when I < J < K, AK < AI < Aji < J < K, a_ {k}<a_ {i}<a_ {j} When I < J < K, AK < AI < AJ , I, Ji, Ji and j cannot be on the same stack.
At this time, we just need to connect the edges of two points that cannot be on the same stack, and then if there are odd rings, we can't, just a graph with even rings? That's a bipartite graph, so at this time, we just need to use bipartite graph coloring to judge whether it is a bipartite graph.
Bipartite graph coloring?
In fact, it is to choose a random point, paint it red, and then choose the edge adjacent to him, paint it blue, and so on.
If you find a point with two colors, you can't.
Finally, as long as the simulated two points on different sides can no longer be in the stack.
code
#include<cstdio> #include<cstring> #define M 2100000 #define N 1100 using namespace std; struct node { int x,y,next; }tr[M];int len,last[N]; inline void ins(int x,int y) { len++;tr[len].x=x;tr[len].y=y;tr[len].next=last[x];last[x]=len; } int col[N],n,a[N],li[2][N]; char st[2100];int cnt; int f[N]; inline int mymin(int x,int y){return x<y?x:y;} void dp()//Figure out which two positions cannot be on the same stack { f[n]=a[n]; for(int i=n-1;i>=1;i--)f[i]=mymin(f[i+1],a[i]); for(int i=1;i<n;i++) { for(int j=i+1;j<n;j++) { if(a[i]<a[j] && f[j+1]<a[i]) { ins(i,j);ins(j,i); } } } } bool color(int x,int u)//Bipartite graph coloring { col[x]=u; for(int k=last[x];k;k=tr[k].next) { int y=tr[k].y; if(col[x]==col[y])return false; if(!col[y] && !color(y,3-u))return false; } return true; } int main() { int T;scanf("%d",&T); while(T--) { cnt=0;li[0][0]=0;li[1][0]=0; len=0;memset(last,0,sizeof(last)); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); col[i]=0; } dp(); bool bk=true; for(int i=1;i<=n;i++) { if(!col[i] && !color(i,1)){bk=false;break;} } if(bk==false) { printf("0\n"); continue; } int top=1; for(int i=1;i<=n;i++)//Simulate inbound sort { int j=col[i]-1; st[++cnt]=j==0?'a':'c'; li[j][++li[j][0]]=a[i]; while(li[0][li[0][0]]==top || li[1][li[1][0]]==top) { if(li[0][li[0][0]]==top)st[++cnt]='b',li[0][0]--,top++;//Out of stack else if(li[1][li[1][0]]==top)st[++cnt]='d',li[1][0]--,top++;//Out of stack } } for(int i=1;i<(n<<1);i++)printf("%c ",st[i]); printf("%c\n",st[(n<<1)]); } return 0; }