题解：
对于任意一对i、j (i<j) 如果存在k (k>j) 使得a[k]<a[i]<a[j] 将i、j连线
表示i、j不能在同一个栈
连完后对这个图做二分图染色 如果不能染色则无解
染完色后若颜色为0就表示该点会放在第一个栈 否则在第二个栈
知道每个点在哪个栈后 就能直接模拟了- -
证明：
命题：对于任意一对i、j (i<j) 如果存在k (k>j) 使得a[k]<a[i]<a[j]，是i、j不在同一个栈的充分必要条件
所谓充分必要条件就是
若满足命题则i、j必不能在一个栈 且若不满足命题 i、j能在同一个栈
先证明若满足命题则i、j必不能在一个栈：
因为弹出顺序要有序 所以 当j要进栈时i还没出栈(因为有a[k]<a[i] 而k还没出栈 )
而a[i]<a[j] 所以这时j不能进栈
再证明若不满足命题 i、j能在同一个栈：
不满足命题有两种情况
1.不存在i<j 且a[i]<a[j]
2.对任意i、j、k (i<j<k) a[j]<a[i] 且 a[j]<a[k]
情况1 这是个降序序列 显然能放进同一个栈
情况2 当j要进栈时 显然i已经被弹出或能被弹出了 因为j后面没有比a[i]小的数
所以i不会对j产生影响
代码：
1 #include <cstdio> 2 #include <cstdlib> 3 const int N=1001,M=2000001; 4 struct inli{ 5 int next,data; 6 inli(const int a=0,const int b=0): 7 next(a),data(b){} 8 }line[M]; 9 int n,a[N],col[N],son[N],sta1[N],sta2[N],top1,top2,last[N],nl; 10 void makeline(){ 11 for (int i=1;i<=n;i++){ 12 int k=i; 13 for (int j=i+1;j<=n;j++) 14 if (a[j]<a[i]) k=j; 15 last[i]=k; 16 for (int j=i+1;j<k;j++) 17 if (a[j]>a[i]){ 18 line[++nl]=inli(son[i],j),son[i]=nl; 19 line[++nl]=inli(son[j],i),son[j]=nl; 20 } 21 } 22 } 23 void print(){ 24 puts("0"); 25 exit(0); 26 } 27 void search(int t){ 28 for (int i=son[t];i;i=line[i].next) 29 if (!col[line[i].data]){ 30 col[line[i].data]=-col[t]; 31 search(line[i].data); 32 }else if (col[t]==col[line[i].data]) 33 print(); 34 } 35 void makecol(){ 36 for (int i=1;i<=n;i++) 37 if (!col[i]){ 38 col[i]=1; 39 search(i); 40 } 41 } 42 void push1(int t){ 43 printf("a "); 44 sta1[++top1]=t; 45 } 46 void pop1(){ 47 printf("b "); 48 --top1; 49 } 50 void push2(int t){ 51 printf("c "); 52 sta2[++top2]=t; 53 } 54 void pop2(){ 55 printf("d "); 56 --top2; 57 } 58 void work(){ 59 for (int i=1;i<=n;i++) 60 if (col[i]==1){ 61 while (top1 && a[sta1[top1]]<a[i]) pop1(); 62 push1(i); 63 }else{ 64 while (top1 && last[sta1[top1]]<i) pop1(); 65 while (top2 && a[sta2[top2]]<a[i]) pop2(); 66 push2(i); 67 } 68 while (top1 || top2){ 69 if (!top1) pop2(); 70 else if (!top2) pop1(); 71 else if (a[sta1[top1]]<a[sta2[top2]]) pop1(); 72 else pop2(); 73 } 74 } 75 int main(){ 76 scanf("%d",&n); 77 for (int i=1;i<=n;i++) scanf("%d",&a[i]); 78 makeline(); 79 makecol(); 80 work(); 81 puts(""); 82 } View Code
转载于:https://www.cnblogs.com/g-word/p/3385182.html
相关资源：JAVA上百实例源码以及开源项目