1812. 【提高组NOIP2008】双栈排序 (twostack.pas/c/cpp)
Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。
操作a
如果输入序列不为空，将第一个元素压入栈S1
操作b
如果栈S1不为空，将S1栈顶元素弹出至输出序列
操作c
如果输入序列不为空，将第一个元素压入栈S2
操作d
如果栈S2不为空，将S2栈顶元素弹出至输出序列
如果一个1~n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列：
当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。
输入
输入文件twostack.in的第一行是一个整数n。
第二行有n个用空格隔开的正整数，构成一个1~n的排列。
输出
输出文件twostack.out共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
样例输入
【输入输出样例1】
4
1 3 2 4
【输入输出样例2】
4
2 3 4 1
【输入输出样例3】
3
2 3 1
样例输出
【输入输出样例1】
a b a a b b a b
【输入输出样例2】
0
【输入输出样例3】
a c a b b d
数据范围限制
【限制】
30%的数据满足： n<=10
50%的数据满足： n<=50
100%的数据满足： n<=1000
一道蛮坑的题目。。。。。
比赛思路：乱打。（三个样例没过）
期望得分：
（最高）：100
（最低）：0
结果出来，
9.1分。呵呵哒…….
转入正题
正解：玄学之二分图染色
具体操作
（1）连边。如果a[k] < a[i] < a[j]且i< j< k,将i与j连边；
（连边的意思是不可以在同一个栈里）
方法：记录一下b[i,j]（i后有没有a[j]),o(2n^2)解决；
（2）入栈：先记录c[i](代表a[i]的状态，0*，1在1栈，2在2栈）如果c[i]=0,c[i]入1栈并将于c[i]连边的点入2栈。
Warning:给出一组数据：
(if c[i]=0 then)
10
10 2 8 1 7 9 3 4 5 6
2-8,8-9,7-9连边
i=1时，10入1栈；
i=2时，2入1栈，8入2栈；
i=3时，8已经在2栈，7入1栈,2不用入1栈（已入）；
i=4时，1入1栈；
i=5时，7入1栈（？），9入2栈！
但，8与9不能进一个栈！
难道输出0？
不对，7可以入2栈，那么9入1栈，成立。
这种”*“入2栈的例子，要判断。
设要入栈的点为i，i的连边点有j。
if c[j]=1 then i入2栈。
如果i入2栈都不行，输出0.
if c[i]=1 then 将i的所有连边点j，c[j]=2;
if c[i]=2 then 将i的所有连边点j，c[j]=1;
（3）出栈。
t=0；
inc(t);if c[t]=0 then break;（if c[t]=1 then s:=s+’b ’ ;if c[t]=2 then s:=s+’d ‘;)
就这样，直到t>=n,退出程序。
做完了。
注意：
1:连双向边；
2：细节！
3：那些字符要用s储存,不要直接输出。
4:字典序时，可能a操作比d先，要判断。（否则90.9)
代码：
请勿抄袭：（6293 bytes)
var
f:array[1..100000,1..2] of longint;
x,y:array[0..10000] of longint;
a,q:array[1..10000] of longint;
b:array[1..1000,1..1000] of longint;
c,d:array[1..100000] of longint;
i,j,k,m,n,o,p,l,s1,t,min:longint;
bz:boolean;
zu:array[1..1000,1..1000] of boolean;
g:array[0..10000] of boolean;
s:ansistring;
procedure insert(x,y:longint);
begin
inc(t);
f[t,1]:=y;
f[t,2]:=q[x];
q[x]:=t;
end;
begin
assign(input,'twostack.in');reset(input);
assign(output,'twostack.out');rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n do begin
min:=maxlongint;
for j:=i+1 to n do
if a[j]<min then begin
min:=a[j];
end;
if min=maxlongint then continue;
for j:=min+1 to n do b[i,j]:=1;
for j:=1 to min do b[i,j]:=0;
end;
fillchar(zu,sizeof(zu),true);
fillchar(g,sizeof(g),true);
for i:=1 to n do begin
for j:=i+1 to n do begin
if a[i]<a[j] then begin
if b[j,a[i]]=1 then begin
insert(a[i],a[j]);
writeln(a[i],' ',a[j]);
zu[a[i],a[j]]:=false;zu[a[j],a[i]]:=false;
end;
end;
end;
end;
s1:=1; t:=0;
for i:=1 to n do begin
if g[i]=false then continue;
if c[a[i]]=0 then begin
d[a[i]]:=x[0];
k:=q[a[i]];
bz:=true;
while k<>0 do begin
if c[f[k,1]]=1 then begin
bz:=false;
end;
if bz=false then break;
k:=f[k,2];
end;
k:=q[a[i]];
if bz=true then begin
s:=s+'a ';
inc(x[0]);
x[x[0]]:=a[i];c[a[i]]:=1;
while k<>0 do begin
if c[f[k,1]]=0 then begin
inc(y[0]);
y[y[0]]:=f[k,1];
c[f[k,1]]:=2;
d[a[i]]:=y[0];
end;
k:=f[k,2];
end;
end else begin
s:=s+'c ';
inc(y[0]);
y[y[0]]:=a[i];c[a[i]]:=2;
while k<>0 do begin
if c[f[k,1]]=0 then begin
inc(x[0]);
x[x[0]]:=f[k,1];
c[f[k,1]]:=1;
end;
k:=f[k,2];
end;
end;
end else if c[a[i]]=1 then begin
s:=s+'a ';
k:=q[a[i]];
while k<>0 do begin
if c[f[k,1]]=1 then begin
writeln(0);
close(input);close(output);
halt;
end;
if c[f[k,1]]=0 then begin
inc(y[0]);
y[y[0]]:=f[k,1];
c[f[k,1]]:=2;
//s:=s+'c ';
end;
k:=f[k,2];
end;
end else begin
k:=q[a[i]];
s:=s+'c ';
while k<>0 do begin
if c[f[k,1]]=2 then begin
writeln(0);
close(input);close(output);
halt;
end;
if c[f[k,1]]=0 then begin
inc(x[0]);
x[x[0]]:=f[k,1];
c[f[k,1]]:=1;
//s:=s+'a ';
end;
k:=f[k,2];
end;
end;
t:=s1;
j:=s1;
repeat
if j=0 then continue;
if c[j]<>0 then begin
if c[j]=1 then begin
s:=s+'b ';
inc(j);
dec(x[0]);
end
else begin
if x[0]=0 then begin
s:=s+'a ';
inc(x[0]);x[x[0]]:=a[i+1];c[i+1]:=1; g[i+1]:=false;
s:=s+'d ';
end else s:=s+'d ';
inc(j);
end;
end;
if c[j]=0 then begin
t:=j;
break;
end;
until j>n;
s1:=t;
//writeln(s);
end;
writeln(s);
close(input);close(output);
end.