这道题的错误做法很多,但是实际在考场上，大多数人拿到了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的题解
/*
* 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;
}
上次修改时间 2017-02-03