这道题的错误做法很多,但是实际在考场上，大多数人拿到了30分。错误做法却能得满分的也很多,正确的算法是基于二分图的算法。注意，不是二分图匹配！
分析条件，我们把问题抽象为数学模型。设输入序列为S，考虑S[i],S[j]两个元素不能进入同一个栈的条件.注意,这里所说的"S[i],S[j]两个元素不能进入同一个栈",不是说仅仅不能同时在一个栈中,而是自始至终不能进入一个栈,即如果有解,那么S[i],S[j]一定进入过的栈不同.
结论P: S[i],S[j]两个元素不能进入同一个栈 <=> 存在k,满足i<j<k,使得S[k]<S[i]<S[j].
证明略过,请参考sqybi.尝试后可以发现结论P是正确的.
把每个元素按照输入序列中的顺序编号,看作一个图中的每个顶点.这时,我们对所有的(i,j)满足i<j,判断是否满足结论P,即S[i],S[j]两个元素能否进入同一个栈.如果满足P,则在i,j之间连接一条边.
我们对图染色,由于只有两个栈,我们得到的图必须是二分图才能满足条件.由于要求字典序最小,即尽量要进入栈1,我们按编号递增的顺序从每个未染色的顶点开始染色,相邻的顶点染上不同的色,如果发生冲突,则是无解的.否则我们可以得到每个顶点颜色,即应该进入的栈.
接下来就是输出序列了,知道了每个元素的决策,直接模拟了.
在判断数对(i,j)是否满足P时,枚举检查是否存在k的时间复杂度是O(n),则总的时间复杂度是O(n^3),对于n=1000是太大了.这原因在于过多得枚举了k,我们可以用动态规划把枚举k变为O(1)的算法.
设F[i]为Min{S[i],S[i+1],S[i+2]..S[n-1],S[n]},状态转移方程为F[i]=Min{ S[i] , F[i+1] }.边界为F[N+1]=极大的值.
判断数对(i,j)是否满足P,只需判断(S[i]<S[j] 并且 F[j+1]<S[i])即可.时间复杂度为O(n^2).
参考资料:sqybi的题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
| /*
* Problem: NOIP2008 twostack
* Author: Guo Jiabao
* Time: 2008.12.9 21:22:52
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=1002;
const int INF=0x7FFFFFFF;
class tStack
{
private:
int top;
int S[MAXN];
public:
tStack() : top(0) {}
void ins(int k)
{
S[++top]=k;
}
int tp()
{
return S[top];
}
void pop()
{
top--;
}
};
int S[MAXN],F[MAXN],bel[MAXN];
bool adjm[MAXN][MAXN];
int N,top1,top2;
tStack T[3];
void init()
{
int i;
freopen("twostack.in","r",stdin);
freopen("twostack.out","w",stdout);
scanf("%d",&N);
for (i=1;i<=N;i++)
{
scanf("%d",&S[i]);
}
}
void noanswer()
{
printf("0");
exit(0);
}
void color(int i,int c)
{
bel[i]=c;
int j;
for (j=1;j<=N;j++)
{
if (adjm[i][j])
{
if (bel[j]==c) //conflict : not a bipartite graph
{
noanswer();
}
if (!bel[j])
{
color(j,3-c); // color the opposite color 1<->2
}
}
}
}
void dye()
{
int i,j;
F[N+1]=INF;
for (i=N;i>=1;i--)
{
F[i]=S[i];
if (F[i+1]<F[i])
F[i]=F[i+1];
}
for (i=1;i<=N-1;i++)
{
for (j=i+1;j<=N;j++)
{
if (S[i]<S[j] && F[j+1]<S[i])
{
adjm[i][j]=adjm[j][i]=true;
}
}
}
for (i=1;i<=N;i++)
{
if (!bel[i])
{
color(i,1);
}
}
}
void solve()
{
int i,should=1,s;
for (i=1;i<=N;i++)
{
s=bel[i];
if (s==1)
{
T[1].ins(S[i]);
printf("a ");
}
else
{
T[2].ins(S[i]);
printf("c ");
}
while (T[1].tp()==should || T[2].tp()==should)
{
if (T[1].tp()==should)
{
T[1].pop();
printf("b");
if (should!=N)
printf(" ");
should++;
}
else
{
T[2].pop();
printf("d");
if (should!=N)
printf(" ");
should++;
}
}
}
}
int main()
{
init();
dye();
solve();
return 0;
} |
Recent Comments