HDU 3328 Flipper 栈 模拟
2024-08-24 13:35:28
首先想说，英语太烂这题读了很长时间才读懂......题意是说输入有几张牌，然后输入这些牌的初始状态（是面朝上还是面朝下），然后输入操作方式，R表示翻一下右边的牌堆，L表示翻一下左边的牌堆，直到最后摞成了一个牌堆。后面跟着一排问题，输入i，问从上往下数的第i张牌编号，以及这张牌的状态。
这题只要读懂了题意思路也挺清晰的了，用栈进行模拟一步一步走就行了，我的思路是先对牌的状态进行计算，如果是R，就把这一步右边所有牌都翻过来，如果是L，就把这一步左边所有牌都翻过来，这样先把所有牌编号和状态都对应好了，这一步不难。
然后再处理牌的上下顺序，这一步就要用到栈了，因为每次翻牌牌的顺序都会完全翻过来，所以用两个栈，每翻一次就翻到另一个空栈里去，因为这题左边右边都在翻，所以我开了四个栈，左边两个右边两个，左边翻的时候就把左边非空栈里的内容一个一个移到左边的空栈里，这样就模拟了翻牌的过程，右边也是一样处理。这样到最后就是左边一堆牌，右边一堆牌（左边剩一个非空栈，右边剩一个非空栈），然后再考虑最后一步是左翻还是右翻，左翻就把左边栈里的清到右边栈里，右翻反之。最后剩下的一个栈就是模拟的翻完之后的顺序了。然后开一个数组再把这个栈里的元素按顺序存在数组里以方便查找，这样四个栈也都清空了，每次跑循环不必再刻意去清空了。
这样状态与顺序都排好了放进了数组里，再问哪一个顺序的牌，直接把数组拉出来cout就可以了，下面是我写的代码，有点长，其实思路挺简短= =就是再判断是不是空栈的时候我一直再用if else所以排的情况太多了导致了代码太长......
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
char zt[];
char cz[];
int a[];
int res[];
stack<int>cardl1;
stack<int>cardl2;
stack<int>cardr1;
stack<int>cardr2; int main()
{
int N,n;
int k=;
int r,l,t;
int i,j;
while(scanf("%d",&N)!=EOF)
{
if(N==)
break;
k++;
scanf("%s",zt);
scanf("%s",cz);
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%d",&a[i]);
}
cout<<"Pile "<<k<<endl;
cardl1.push();
cardr1.push(N);
r=N-;
l=;
for(i=;i<N-;i++)
{
if(cz[i]=='R')
{
for(j=r;j<N;j++)
{
if(zt[j]=='U')
zt[j]='D';
else
zt[j]='U';
}
r=r-;
if(i==N-)
break;
if(cardr2.empty())
{
cardr2.push(r+);
while(!cardr1.empty())
{
t=cardr1.top();
cardr1.pop();
cardr2.push(t);
}
}
else
{
cardr1.push(r+);
while(!cardr2.empty())
{
t=cardr2.top();
cardr2.pop();
cardr1.push(t);
}
}
}
else
{
for(j=l;j>=;j--)
{
if(zt[j]=='U')
zt[j]='D';
else
zt[j]='U';
}
l=l+;
if(i==N-)
break;
if(cardl2.empty())
{
cardl2.push(l+);
while(!cardl1.empty())
{
t=cardl1.top();
cardl1.pop();
cardl2.push(t);
}
}
else
{
cardl1.push(l+);
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-]=='R')
{
while(!cardr2.empty())
{
t=cardr2.top();
cardr2.pop();
cardl2.push(t);
}
for(i=;!cardl2.empty();i++)
{
res[i]=cardl2.top();
cardl2.pop();
}
}
else
{
while(!cardl2.empty())
{
t=cardl2.top();
cardl2.pop();
cardr2.push(t);
}
for(i=;!cardr2.empty();i++)
{
res[i]=cardr2.top();
cardr2.pop();
}
}
}
else
{
if(cz[N-]=='R')
{
while(!cardr1.empty())
{
t=cardr1.top();
cardr1.pop();
cardl2.push(t);
}
for(i=;!cardl2.empty();i++)
{
res[i]=cardl2.top();
cardl2.pop();
}
}
else
{
while(!cardl2.empty())
{
t=cardl2.top();
cardl2.pop();
cardr1.push(t);
}
for(i=;!cardr1.empty();i++)
{
res[i]=cardr1.top();
cardr1.pop();
}
}
}
}
else
{
if(!cardr2.empty())
{
if(cz[N-]=='R')
{
while(!cardr2.empty())
{
t=cardr2.top();
cardr2.pop();
cardl1.push(t);
}
for(i=;!cardl1.empty();i++)
{
res[i]=cardl1.top();
cardl1.pop();
}
}
else
{
while(!cardl1.empty())
{
t=cardl1.top();
cardl1.pop();
cardr2.push(t);
}
for(i=;!cardr2.empty();i++)
{
res[i]=cardr2.top();
cardr2.pop();
}
}
}
else
{
if(cz[N-]=='R')
{
while(!cardr1.empty())
{
t=cardr1.top();
cardr1.pop();
cardl1.push(t);
}
for(i=;!cardl1.empty();i++)
{
res[i]=cardl1.top();
cardl1.pop();
}
}
else
{
while(!cardl1.empty())
{
t=cardl1.top();
cardl1.pop();
cardr1.push(t);
}
for(i=;!cardr1.empty();i++)
{
res[i]=cardr1.top();
cardr1.pop();
}
}
}
}
//for(i=0;i<N;i++)
//{
// cout<<res[i]<<endl;
//}
for(i=;i<n;i++)
{
cout<<"Card "<<a[i]<<" is a face ";
if(zt[res[a[i]-]-]=='U')
cout<<"up ";
else
cout<<"down ";
cout<<res[a[i]-]<<"."<<endl;
}
}
return ;
}
A出来之后和集训队里的大神讨论，这题他用的数组模拟写起来要比我的方法快= ="一般的用数组模拟栈就是int stk[MAXN],top;压栈的话，比如压个1就是 stk[top++]=1；退栈就是a=stk[--top];"以上大神原话→_→
最新文章
- 启动页面设置，icon图标设置
- motto4
- json和jsonp的使用格式
- java 解惑
- 面试总结之html+css
- visual studio2013 apache cordova基于web的跨平台应用
- JavaWeb框架SSH_Struts2_(二)
- php之插入排序
- [Codeforces Round #438][Codeforces 868C. Qualification Rounds]
- Microsoft SQL Server 【Windows 身份验证】和 【sa】都无法登录的解决方案
- 18.3 #define DM9000_DBG(fmt,args...) printf(fmt, ##args)代表什么
- Shell-14--awk
- luogu1984 烧水问题 (找规律)
- springboot+dubbo+tomcat部署出错问题
- 动态规划DP的优化
- html5 canvas 弧形描边渐变
- CLR via C# 读书笔记-26.线程基础
- linux shell基本知识 sleep命令
- C#程序集系列03,引用多个module
- Winform 加密连接字符串“未能提供RsaProtectedConfigurationProvider加密，对象已存在”的解决方案