HDU 3328 Flipper 棧 模擬，hduflipper
首先想說，英語太爛這題讀了很長時間才讀懂......題意是說輸入有幾張牌，然後輸入這些牌的初始狀態（是面朝上還是面朝下），然後輸入操作方式，R表示翻一下右邊的牌堆，L表示翻一下左邊的牌堆，直到最後摞成了一個牌堆。後面跟著一排問題，輸入i，問從上往下數的第i張牌編號，以及這張牌的狀態。
這題只要讀懂了題意思路也挺清晰的了，用棧進行模擬一步一步走就行了，我的思路是先對牌的狀態進行計算，如果是R，就把這一步右邊所有牌都翻過來，如果是L，就把這一步左邊所有牌都翻過來，這樣先把所有牌編號和狀態都對應好了，這一步不難。
然後再處理牌的上下順序，這一步就要用到棧了，因為每次翻牌牌的順序都會完全翻過來，所以用兩個棧，每翻一次就翻到另一個空棧裡去，因為這題左邊右邊都在翻，所以我開了四個棧，左邊兩個右邊兩個，左邊翻的時候就把左邊非空棧裡的內容一個一個移到左邊的空棧裡，這樣就模擬了翻牌的過程，右邊也是一樣處理。這樣到最後就是左邊一堆牌，右邊一堆牌（左邊剩一個非空棧，右邊剩一個非空棧），然後再考慮最後一步是左翻還是右翻，左翻就把左邊棧裡的清到右邊棧裡，右翻反之。最後剩下的一個棧就是模擬的翻完之後的順序了。然後開一個數組再把這個棧裡的元素按順序存在數組裡以方便查找，這樣四個棧也都清空了，每次跑循環不必再刻意去清空了。
這樣狀態與順序都排好了放進了數組裡，再問哪一個順序的牌，直接把數組拉出來cout就可以了，下面是我寫的代碼，有點長，其實思路挺簡短= =就是再判斷是不是空棧的時候我一直再用if else所以排的情況太多了導致了代碼太長......
![]()
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
char zt[105];
char cz[105];
int a[105];
int res[105];
stack<int>cardl1;
stack<int>cardl2;
stack<int>cardr1;
stack<int>cardr2;
int main()
{
int N,n;
int k=0;
int r,l,t;
int i,j;
while(scanf("%d",&N)!=EOF)
{
if(N==0)
break;
k++;
scanf("%s",zt);
scanf("%s",cz);
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
cout<<"Pile "<<k<<endl;
cardl1.push(1);
cardr1.push(N);
r=N-1;
l=0;
for(i=0;i<N-1;i++)
{
if(cz[i]=='R')
{
for(j=r;j<N;j++)
{
if(zt[j]=='U')
zt[j]='D';
else
zt[j]='U';
}
r=r-1;
if(i==N-2)
break;
if(cardr2.empty())
{
cardr2.push(r+1);
while(!cardr1.empty())
{
t=cardr1.top();
cardr1.pop();
cardr2.push(t);
}
}
else
{
cardr1.push(r+1);
while(!cardr2.empty())
{
t=cardr2.top();
cardr2.pop();
cardr1.push(t);
}
}
}
else
{
for(j=l;j>=0;j--)
{
if(zt[j]=='U')
zt[j]='D';
else
zt[j]='U';
}
l=l+1;
if(i==N-2)
break;
if(cardl2.empty())
{
cardl2.push(l+1);
while(!cardl1.empty())
{
t=cardl1.top();
cardl1.pop();
cardl2.push(t);
}
}
else
{
cardl1.push(l+1);
while(!cardl2.empty())
{
t=cardl2.top();
cardl2.pop();
cardl1.push(t);
}
}
}
}
//cout<<zt<<endl;
//while(!cardl2.empty())
//{
// cout<<cardl2.top()<<endl;
// cardl2.pop();
//}
if(!cardl2.empty())
{
if(!cardr2.empty())
{
if(cz[N-2]=='R')
{
while(!cardr2.empty())
{
t=cardr2.top();
cardr2.pop();
cardl2.push(t);
}
for(i=0;!cardl2.empty();i++)
{
res[i]=cardl2.top();
cardl2.pop();
}
}
else
{
while(!cardl2.empty())
{
t=cardl2.top();
cardl2.pop();
cardr2.push(t);
}
for(i=0;!cardr2.empty();i++)
{
res[i]=cardr2.top();
cardr2.pop();
}
}
}
else
{
if(cz[N-2]=='R')
{
while(!cardr1.empty())
{
t=cardr1.top();
cardr1.pop();
cardl2.push(t);
}
for(i=0;!cardl2.empty();i++)
{
res[i]=cardl2.top();
cardl2.pop();
}
}
else
{
while(!cardl2.empty())
{
t=cardl2.top();
cardl2.pop();
cardr1.push(t);
}
for(i=0;!cardr1.empty();i++)
{
res[i]=cardr1.top();
cardr1.pop();
}
}
}
}
else
{
if(!cardr2.empty())
{
if(cz[N-2]=='R')
{
while(!cardr2.empty())
{
t=cardr2.top();
cardr2.pop();
cardl1.push(t);
}
for(i=0;!cardl1.empty();i++)
{
res[i]=cardl1.top();
cardl1.pop();
}
}
else
{
while(!cardl1.empty())
{
t=cardl1.top();
cardl1.pop();
cardr2.push(t);
}
for(i=0;!cardr2.empty();i++)
{
res[i]=cardr2.top();
cardr2.pop();
}
}
}
else
{
if(cz[N-2]=='R')
{
while(!cardr1.empty())
{
t=cardr1.top();
cardr1.pop();
cardl1.push(t);
}
for(i=0;!cardl1.empty();i++)
{
res[i]=cardl1.top();
cardl1.pop();
}
}
else
{
while(!cardl1.empty())
{
t=cardl1.top();
cardl1.pop();
cardr1.push(t);
}
for(i=0;!cardr1.empty();i++)
{
res[i]=cardr1.top();
cardr1.pop();
}
}
}
}
//for(i=0;i<N;i++)
//{
// cout<<res[i]<<endl;
//}
for(i=0;i<n;i++)
{
cout<<"Card "<<a[i]<<" is a face ";
if(zt[res[a[i]-1]-1]=='U')
cout<<"up ";
else
cout<<"down ";
cout<<res[a[i]-1]<<"."<<endl;
}
}
return 0;
}
View Code
A出來之後和集訓隊裡的大神討論，這題他用的數組模擬寫起來要比我的方法快= ="一般的用數組模擬棧就是int stk[MAXN],top;壓棧的話，比如壓個1就是 stk[top++]=1；退棧就是a=stk[--top];"以上大神原話→_→
