看了神犇的题解.
我们可以发现当s[i],s[j]满足一个条件时，s[i],s[j],始终不能进入同一个栈。
这个条件就是存在i<j<k,且s[k]<s[i]<s[j]。将存在该条件的两点连边，构造二分图，之后进行染色，一条边的两端颜色不能相同，否则无解。
判断条件需用DP预处理，否则会TLE，方程为：F[i]=min(s[i],F[i+1]),f[i]为s[i到n]中的最小值，先将f[n+1]设为极大值。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
#define LL long long 
using namespace std;
template <class _T> inline void read(_T &_x) {
    int _t; bool _flag=false;
    while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;
    if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';
    while((_t=getchar())>='0'&&_t<='9') _x=_x*10+_t-'0';
    if(_flag) _x=-_x;
}
const int maxn=2005;
bool Edge[maxn][maxn];
int s[maxn],F[maxn],co[maxn];
stack <int> sa,sb;
int n;
void dfs(int x,int c){
    co[x]=c;
    for(int i=1;i<=n;++i)
        if(Edge[x][i]){
            if(co[i]==c){
                printf("0\n");
                exit(0);
            }
            if(!co[i]) dfs(i,3-c);
        }
}

int main(){
    read(n);
    for(int i=1;i<=n;++i)read(s[i]);
    F[n+1]=0x3f3f3f3f;
    for(int i=n;i>=1;--i)F[i]=min(s[i],F[i+1]);
    
    for(int i=1;i<n;++i)
        for(int j=i+1;j<=n;++j)
            if(s[i]<s[j]&&F[j+1]<s[i])
                Edge[i][j]=Edge[j][i]=true;
    for(int i=1;i<=n;++i)
        if(!co[i])dfs(i,1);
    
    int aim=1;
    for(int i=1;i<=n;++i){
        if(co[i]==1){
            sa.push(s[i]);
            printf("a ");
        }
        else{
            sb.push(s[i]);
            printf("c ");
        }
        while(!sa.empty()&&sa.top()==aim||!sb.empty()&&sb.top()==aim){
            if(!sa.empty()&&sa.top()==aim){
                sa.pop();
                printf("b ");
            }
            else{
                sb.pop();
                printf("d ");
            }
            aim++;
        }
    }
    return 0;
}

var
a,b,co:array [0..1005] of longint;
c:array [0..1005,0..1005] of boolean;
d:array [0..1005] of boolean;
n,i,j,la:longint;
s:array [1..2,0..1005] of longint;
procedure dfs(x:longint);
var i:longint;
begin
for i:=1 to n do
if c[x,i] then begin
if d[i] and (co[i]<>3-co[x]) then begin write(0); halt; end;
if not(d[i]) then begin co[i]:=3-co[x]; d[i]:=true; dfs(i); end;
end;
end;
begin
fillchar(c,sizeof(c),false);
fillchar(d,sizeof(d),false);
read(n);
for i:=1 to n do read(a[i]);
b[n+1]:=100000000;
for i:=n downto 1 do if (a[i]<b[i+1]) then b[i]:=a[i] else b[i]:=b[i+1];
for i:=1 to n do
for j:=i+1 to n do
if (b[j+1]<a[i]) and (a[i]<a[j]) then begin c[i,j]:=true; c[j,i]:=true; end;
for i:=1 to n do if (co[i]=0) then begin co[i]:=1; d[i]:=true; dfs(i); end;
la:=1;
for i:=1 to n do
begin
if (co[i]=1) then write('a ') else write('c ');
inc(s[co[i],0]); s[co[i],s[co[i],0]]:=a[i];
while (s[1,s[1,0]]=la) or (s[2,s[2,0]]=la) do
if (s[1,s[1,0]]=la) then begin write('b'); if (la<>n) then write(' '); dec(s[1,0]); inc(la); end
else begin write('d'); if (la<>n) then write(' '); dec(s[2,0]); inc(la); end;
end;
end.

醉了，不用那个MIN数组都过了九个点，最后一个点加个特判就过了......

首先两个栈中的元素一定是降序排列的，否则某些元素一定无法出栈。所以，当某个元素将要入栈时，它一定不能和“已在栈中”且“小于”它的元素在同一个栈中。参考noip2010年关押罪犯那道题的思路，可以采用并查集来维护元素之间的关系。

下面是代码。

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;

int seg[1005],bc[2005];
char ans[2005],state[2005];
bool instack[1005];

int find(int x){
if(bc[x]==x) return x;
return bc[x] = find(bc[x]);
}

int main(){
freopen("data.txt","r",stdin);
int i,n,curn,ans_cnt,j;
scanf("%d",&n);
for(i = 1;i<=n;i++) {
scanf("%d",&seg[i]);
bc[i] = i;
bc[i+n] = i+n;
}
i = curn = 1;
memset(instack,0,sizeof(instack));
while(curn<=n){
if(instack[curn] == true) {
instack[curn] = false;
curn++;
continue;
}
for(j = 1;j<seg[i];j++) {
if(instack[j] == true) {
if(find(j) == find(seg[i]) || find(j+n) == find(seg[i]+n)) {
printf("0\n");
return 0;
}
bc[find(j)] = n+seg[i];
bc[find(n+j)] = seg[i];
}
}
instack[seg[i]] = true;
i++;
}
i = curn = 1;
ans_cnt = 0;
memset(state,0,sizeof(state));
memset(instack,0,sizeof(instack));
while(curn<=n){
if(instack[curn] == true){
ans[++ans_cnt] = 'b' + state[find(curn)] - 1;
curn++;
continue;
}
if(state[find(seg[i])] == 0) {//当发现此时的元素还没有确定在哪个栈中时，将其分配于s1栈
state[find(seg[i])] = 1;
state[find(seg[i]+n)] = 3;
}
ans[++ans_cnt] = 'a' + state[find(seg[i])] - 1;
instack[seg[i]] = true;
i++;
}
for(i = 1;i<ans_cnt;i++) printf("%c ",ans[i]);
printf("%c\n",ans[i]);
return 0;
}

var
a,b,co:array [0..1005] of longint;
c:array [0..1005,0..1005] of boolean;
d:array [0..1005] of boolean;
n,i,j,la:longint;
s:array [1..2,0..1005] of longint;
procedure dfs(x:longint);
var i:longint;
begin
for i:=1 to n do
if c[x,i] then begin
if d[i] and (co[i]<>3-co[x]) then begin write(0); halt; end;
if not(d[i]) then begin co[i]:=3-co[x]; d[i]:=true; dfs(i); end;
end;
end;
begin
fillchar(c,sizeof(c),false);
fillchar(d,sizeof(d),false);
read(n);
for i:=1 to n do read(a[i]);
b[n+1]:=100000000;
for i:=n downto 1 do if (a[i]<b[i+1]) then b[i]:=a[i] else b[i]:=b[i+1];
for i:=1 to n do
for j:=i+1 to n do
if (b[j+1]<a[i]) and (a[i]<a[j]) then begin c[i,j]:=true; c[j,i]:=true; end;
for i:=1 to n do if (co[i]=0) then begin co[i]:=1; d[i]:=true; dfs(i); end;
la:=1;
for i:=1 to n do
begin
if (co[i]=1) then write('a ') else write('c ');
inc(s[co[i],0]); s[co[i],s[co[i],0]]:=a[i];
while (s[1,s[1,0]]=la) or (s[2,s[2,0]]=la) do
if (s[1,s[1,0]]=la) then begin write('b'); if (la<>n) then write(' '); dec(s[1,0]); inc(la); end
else begin write('d'); if (la<>n) then write(' '); dec(s[2,0]); inc(la); end;
end;
end.

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int p [1010 ],col[1010 ],Min[1010 ],pai[3][1010],l[3],wei[10010],las[10010],too[10010];
int n,t=0,should=1;
void line(int x,int y) {
las[++t] = wei[x]; wei[x] = t; too[t] = y;
las[++t] = wei[y]; wei[y] = t; too[t] = x;
}
void draw(int x,int c) {
if (!col[x] ) col[x]=c; else
if ( col[x]!=c) {printf("0");exit(0);} else return;
for (int i=wei[x]; i; i=las[i]) draw(too[i],3-c);
}
int main() {
scanf("%d",&n); for (int i=1 ; i<=n; i++) scanf("%d",&p[i]);
Min[n] = p[n]; for (int i=n-1; i>=1; i--) Min[i]=min(Min[i+1],p[i]);
pai[1][0]=1002; col[n+1]=1; pai[2][0]=1002; p[n+1]=1001;
for (int i=1 ; i<=n-2; i++)
for (int j=i+1; j<=n-1; j++)
if(p[i]<p[j]&&Min[j+1]<p[i]) line(i,j);
for (int i=1 ; i<=n ; i++)
if ( !col[ i ] ) draw(i,1);
for (int i=1 ; i<=n+1; i++) {
int f=1;
while (f)
if ( pai[1][l[1]] == should ) {should++; l[1]--; printf("b ");} else
if ( pai[2][l[2]] == should ) {should++; l[2]--; printf("d ");} else f=0;
pai[ col[i] ][ ++l[ col[i] ] ]=p[i];
if (i<n+1) printf("%c ", char(2*col[i]+95) );
}
}

AC 100纪念 NOIP RP++

http://www.cnblogs.com/qq359084415/p/3386260.html

var
n,i,top,j,k,s1,s2,min:longint;
fa,s,set2,set1,a,b:array[0..2010] of longint;
function getfather(k:longint):longint;
begin
if fa[k]=k then exit(k);
fa[k]:=getfather(fa[k]);
exit(fa[k]);
end;
procedure union(a,b:longint);
var k1,k2:longint;
begin
k1:=getfather(a); k2:=getfather(b);
if k1<>k2 then fa[k1]:=k2;
end;
function canA:boolean;
begin
if (s1=0) or ((a[k]<set1[s1]) and (s[k]=1)) then exit(true)
else exit(false);
end;
function canB:boolean;
begin
if (s1>0) and (set1[s1]=top+1) then exit(true)
else exit(false);
end;
function canC:boolean;
begin
if ((a[k]<set2[s2]) and (s[k]=2)) or (s2=0) then exit(true)
else exit(false);
end;
function canD:boolean;
begin
if (s2>0) and (set2[s2]=top+1) then exit(true)
else exit(false);
end;
begin
readln(n);
for i:=1 to 2*n do fa[i]:=i;

for i:=1 to n do
read(a[i]);
min:=maxlongint;
for i:=n downto 1 do
begin
if a[i]<min then min:=a[i];
b[i]:=min;
end;
b[n+1]:=maxlongint;
for i:=1 to n-1 do
for j:=i+1 to n do
if (a[i]<a[j]) and (b[j+1]<a[i]) then
begin
union(i,j+n);
union(i+n,j);
end;
for i:=1 to n do
if getfather(i)=getfather(i+n) then begin writeln('0'); exit end;
for i:=1 to n do
if s[i]=0 then
begin
s[i]:=1;
for j:=1 to n do if getfather(i)=getfather(j) then s[j]:=1;
for j:=n+1 to 2*n do if getfather(i)=getfather(j) then s[j-n]:=2;
end;
k:=1;
for i:=1 to 2*n do
begin
if canA then begin write('a '); inc(s1); set1[s1]:=a[k]; inc(k); continue end;
if canB then begin write('b '); dec(s1); inc(top); continue end;
if canC then begin write('c '); inc(s2); set2[s2]:=a[k]; inc(k); continue end;
if canD then begin write('d '); dec(s2); inc(top); continue end;
end;
end.
来个并查集版的题解，我看网上没有pascal的

怎么证明当不存在那个条件的时候 就满足?

弱弱的问句,数据跟当年一样吗- -

为什么用那年数据第十组数据瞬杀

这里挂了- -

用的也是二分图染色-模拟

并查集+模拟=秒杀

DFS是王道

难想.....

不会写的可以认真研读网上的解题报告，比如我就读了整整一天才弄懂......

编程难度很水，问题是能想到这种方法一点也不水！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

#include

using namespace std;

int a[1001],m[1001],c[1001],G[1001][1001],gn[1001];

int Sa[001],Sb[1001],an=0,bn=0,flag=0;

int dye(int i,int color)

{

int f,copie[1001];

memcpy(copie,c,sizeof(copie));

c[i]=color;

for (int j=1;j>n;

for (i=1;i>a[i];

for (i=1;i

一次水过....

构图难想啊,不过后面就还可以了,下面的大部分都用floodfill，不过并查集完全可以代替啊，只要保证每个不同集的最终父亲都是本集中入栈顺序最早的，也即最先读入的，然后把这些父亲入栈１，集中其他的数按对应关系入栈即可．对应关系冲突时就输出０．

AC了

24/100(24%)

也算是100题记录了…………不解释

very difficult

爽！

终于过了！ 100题纪念

本来想作为第888个提交的……

无奈Vj上的牛太多了~就1个来小时 人数就飙上去了~~

var

n,i,j,t,l:longint;

ans:array[1..10000] of char;

color,a,b,s1,s2:array[0..1000] of longint;

g:array[1..1000,1..1000] of boolean;

cf:array[1..1000] of boolean;

function min(a,b:longint):longint;

begin

if a>b then exit(b)

else exit(a);

end;

procedure no_result;

begin

writeln(0);

halt;

end;

procedure makecolor(i,k:longint);

var

j:longint;

begin

cf[i]:=true;

color[i]:=k;

for j:=1 to n do

if ij then

if g and (not cf[j])

then makecolor(j,3-k)

else if (color[j]=color[i])and(g) then no_result;

end;

procedure input;

begin

readln(n);

for i:=1 to n do

read(a[i]);

readln;

end;

procedure prework;

begin

fillchar(b,sizeof(b),$f);

b[n]:=a[n];

for i:=n-1 downto 1 do

b[i]:=min(b,a[i]);

for i:=1 to n do

for j:=i+1 to n do

if (a[i]