本文正體字版由OpenCC轉換
這道題的錯誤做法很多,但是實際在考場上，大多數人拿到了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