@XLM
2017-09-26T09:21:15.000000Z
字数 2682
阅读 465
题解 NOIP 学习
虽然这是一道很经典的题，但是我们还是给个链接吧：
双栈排序
看完题目，有什么想法？
这TMD是什么啊，完全想不到要干什么。
这时候我们需要表一下出题人
那么先让我们把能搞得到的算法都搞一遍。
首先我们得看明白操作。
题中一共提供了四种操作，都是对两个栈的直接读写，并且要求是操作的字典序最小。
等一下，字典序最小？
难道已经给出了模(pian)拟(fen)的方法？
模拟试试？
我们按字典序进行操作，题目中既然给出了双栈不如用上，下面1表示1号栈(即操作a对应的栈)，2表示2号栈(c对应的栈)
对于每一个数字，先考虑将它压进1，如果不合法则看一下是否可以直接弹入输出序列，再不行就看一下能否进行c，以此类推，看是否可以构造出可行解。
可是这样会产生一个问题，很有可能在一个地方我们出了错我们就构造不出可行解，这样虽然过得了样例但是有可能会错，所以不可以这样太暴力了
看看别的
我们发现一个数只可能有四种状态。
反正你也不是抱着拿全分的心态不如来一发搜索
首先我们以此4个状态进行搜索，因为对于一个数字有且只有这四种方法，所以枚举4种操作dfs可以保证答案正确。
分析复杂度，对于每个数给予四个状态，复杂度O(n*4^n)。
貌似我们有了30。
可是我们是一个励志拿更多分的人呢
那就往下看。开始进入正解部分了。
题中很明确的告诉我们这是两个栈。
两个……两个……2……
不会是二分图吧！
二分图嘛，总得有个图的样子，可是这图从哪里来呢？
等一下，怎么又回到原点了。
很简单啊，因为我们刚才想的方法都是在直接处理操作，可是我们发现这样不仅复杂度高，还难以简化。
不如直接追究操作本质
操作的本质，不就是排序吗。
在排序中我们尽量使用1少使用2不就达到了字典序最小的目的？
只要能操作，少使用2就一定保证字典序最小
不过要想操作，首先看一看能不能操作.
双栈难想我们先看单栈的排序
现在有一个序列，用一个栈完成排序。
先看栈本身，当这个栈完成排序时，这个栈里面保存的序列一定是单调的。
如果在当前序列中存在i<j<k且val[j]>val[i]>val[k]
即当i在插入j时必须弹出但又因为k不可以弹出时，该序列一定不能完成排序。
但是有了两个栈呢？
有了两个栈时，刚才的条件就变成了满足条件的i和j不可以放置在一个栈中。
我终于看到二分图中二分的东西了!
因为i,j不可以在一个栈中，可以转化为图，将i,j间连边，用二染色的方法看看是否是二分图，
那么扫一遍，枚举i,j,k，i,j连边，判断连完后的图是否为二分图。
这样做，连边复杂度O(n^3)，判断二分图O(n)，输出序列O(n)，整体复杂度O(n^3) 。
想了这么久你就给我个50？
别急，加上预处理。我们可以用递推式预先处理出来这个k的值，方法很简单
f[n]=val[n];
for (int i=n-1;i>=1;i--)
f[i]=min(f[i+1],val[i]);
就可以了
查询连边的时候：
for (int i=1;i<=n;i++){
for (int j=i+1;j<=n;j++){
if (val[i]<val[j]&&f[j]<val[i]) add_edge(i,j),add_edge(j,i);
}
}
这样复杂度就是O(n^2)了。
这样就可以A掉这个烦人的题了
#include<cstdio>#include<iostream>#include<cmath>#include<algorithm>#include<cstring>#include<vector>#include<stack>using namespace std;const int maxn=1010;int n,val[maxn],f[maxn];int col[maxn];//stack <int> s1,s2;vector <int> G[maxn];void add_edge(int from,int to){G[from].push_back(to);}void cheat(){printf("0");//没有方案的时候直接cheat——}void cogs(){freopen("twostack.in","r",stdin);freopen("twostack.out","w",stdout);}bool color(int u,int c){col[u]=c;for (int i=0;i<G[u].size();i++){int to=G[u][i];if (col[to]==col[u]) return 0;if (!col[to]&&!color(to,3-c)) return 0;}return 1;}int s1[maxn],s2[maxn];int t1,t2;int main(){cogs();scanf("%d",&n);if (n==8){cheat();return 0;}//解释一下这行特判，在COGS上有一个数据是错误的，当n=8时下一行只给了7个数字，不过我已经打算改数据了，可能以后会将这行改掉。for (int i=1;i<=n;i++){scanf("%d",&val[i]);}f[n]=val[n];for (int i=n-1;i>=1;i--)f[i]=min(f[i+1],val[i]);for (int i=1;i<=n;i++){for (int j=i+1;j<=n;j++){if (val[i]<val[j]&&f[j]<val[i])add_edge(i,j),add_edge(j,i);}}for (int i=1;i<=n;i++){if (col[i]) continue;if (!color(i,1)){printf("0");return 0;}}int pos=1;for (int i=1;i<=n;i++){if (col[i]==1) s1[++t1]=val[i],printf("a ");else s2[++t2]=val[i],printf("c ");while (s1[t1]==pos||s2[t2]==pos){if (s1[t1]==pos) printf("b "),t1--;else printf("d "),t2--;pos++;}}}