UVA127
链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=63
一道非常好的栈的模拟题，训练计划又往后推了一周，因为各种事情，不过自己已经做了修改，另外说一下，今晚寝室那两尊神不在，难得的心情好，
这题其实还是看了别人的代码的，大牛博客：http://blog.csdn.net/hyczms/article/details/38009937
我的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=;
struct Card
{
char value,suit;
};
int judge(Card x,Card y)
{
return (x.value==y.value||x.suit==y.suit);
}
int main()
{
stack<Card> s[maxn];
Card card;
int n=,i;
while(scanf("%c%c", &card.value, &card.suit) && card.value != '#')
{
getchar();
s[n++].push(card);
if(n==)
{
int m=,flag;
while(true)
{
for(i=m;i<n;i++)
{
if(i>=&&judge(s[i].top(),s[i-].top()))
{
flag=;
break;
}
else if(i>=&&judge(s[i].top(),s[i-].top()))
{
flag=;
break;
}
}
if(i==n)
break;
if(flag==)
{
s[i-].push(s[i].top());
m=i-;
}
else
{
s[i-].push(s[i].top());
m=i-;
}
s[i].pop();
if(s[i].empty())
{
for(int j=i;j<n-;j++)
s[j]=s[j+];
while(!s[n-].empty())
s[n-].pop();
n--;
}
}
if(n>)
printf("%d piles remaining:",n);
else
printf("%d pile remaining:",n);
for(int i=;i<n;i++)
{
printf(" %d",s[i].size());
while(!s[i].empty())
s[i].pop();
}
printf("\n");
n=;
}
}
return ;
}
开始刷题的第一天，也只是利用晚上复习完考研回寝室的时间做做自己喜欢的事情，希望可以坚持下去
UVA673
一道栈的经典题目
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<algorithm>
#include<cctype>
#include<cstdlib>
using namespace std;
const int maxn=+;
//char s[maxn];
int main()
{
int T;
cin>>T;
getc(stdin);
while(T--)
{
char s[maxn];
gets(s);
stack<char> a;
int str1=']'-'[';
int str2=')'-'(';
int n=strlen(s);
for(int i=;i<n;i++)
{
if(a.empty())
{
a.push(s[i]);
continue;
}
char t=a.top();
if(s[i]-t==str1||s[i]-t==str2)
a.pop();
else
a.push(s[i]);
}
if(a.empty())
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return ;
}
UVA101
这道题目在UVA上面AC率比较低，事实证明也不是一道非常容易的题目，卡了我好久，算是一道恶心的模拟，理解题意就用了好几天，最后也还是参照着题解才过的，不过这类似的题目我一定得多做，对提高代码能力是非常有帮助的。另外就是自己刷题速度实在是太慢了，必须督促自己坚持每天好好刷题，uva虽然略难，但真的是一个靠谱的OJ，不过这题，今晚回宿舍一定要在好好理解一下，总结一下
解题报告来自：http://m.blog.csdn.net/blog/yexiaohhjk/44969131
用了vector，确实大大减少了代码量，也是刘汝佳老师提供的一种写法，和神牛的差距永远那么大
贴一下题目意思：
1.move a onto b，把a和b上面的方块都放回原来位置，然后把a放到b上面；
2.move a over b，把a上面的放回原处，然后把a放在b所在的方块堆的上面；
3.pile a onto b，把b上面的放回原来位置，然后把a和a上面的方块整体放到b上面；
4.pile a over b，把a和a上面的方块整体放到b所在堆的上面。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=;
int n;
vector <int>pile[maxn];
void find_block(int a,int &p,int &h) //找到a在第p堆的第h个
{
for(p=;p<n;p++)
{
for(h=;h<pile[p].size();h++)
if(pile[p][h]==a)
return;
}
}
void clear_block(int p,int h) //将a上面的元素放回原处
{
for(int i=h+;i<pile[p].size();i++)
{
int b;
b=pile[p][i];
pile[b].push_back(b);
}
pile[p].resize(h+);
}
void onto_block(int p,int h,int p2) //将a及上面的元素放在b上
{
for(int i=h;i<pile[p].size();i++)
pile[p2].push_back(pile[p][i]);
pile[p].resize(h);
}
void print() //打印输出
{
for(int i=;i<n;i++)
{
printf("%d:",i);
for(int j=;j<pile[i].size();j++)
printf(" %d",pile[i][j]);
printf("\n");
}
}
int main()
{
cin>>n;
for(int i=;i<n;i++)
pile[i].push_back(i);
string s1,s2;
int a,b;
while(cin>>s1)
{
if(s1=="quit")
break;
cin>>a>>s2>>b;
int pa,pb,ha,hb;
find_block(a,pa,ha);
find_block(b,pb,hb);
if(pa==pb) continue;
if(s2=="onto")
clear_block(pb,hb);
if(s1=="move")
clear_block(pa,ha);
onto_block(pa,ha,pb);
}
print();
return ;
}
uva133
纯种的模拟题，约瑟夫环双向模拟，开始被vector坑了，后来发现这题真的不能用vector，同时也对vector有了更深的认识，还好有大牛提点
链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=69
别人的的博客：http://www.cnblogs.com/xiaobaibuhei/archive/2013/04/17/3026383.html
下面贴一下弱菜的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=;
int a[maxn];
int main()
{
int n,m,k;
while(cin>>n>>m>>k)
{
if(n==&&m==&&k==)
break;
for(int i=;i<n;i++)
a[i]=i+;
int p=n-,q=;
int flag=;
int length=n;
while(length)
{
for(int i=;i<m;)
{
p=(p+)%n;
if(a[p]) i++;
}
for(int i=;i<k;)
{
q=(q-+n)%n;
if(a[q]) i++;
}
if(flag) flag=;
else printf(",");
if(p==q)
{
printf("%3d",a[p]);
a[p]=;
--length;
}
else
{
printf("%3d%3d",a[p],a[q]);
a[p]=a[q]=;
length-=;
}
}
cout<<endl;
}
return ;
}
uva442
这题是用新电脑在自习室做的，吐槽一下，新电脑打代码很难用，这题最值得学习就是类的继承的用法，很经典，这题也是一道很好的栈模拟题，看穿背景以后就是，只需要判断"）".而不用管"("
题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=383
我的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=;
typedef struct Matrix //工程代码的写法还是值得学习
{
int a,b;
Matrix(int a=,int b=):a(a),b(b){};
};
Matrix p[maxn];
int main()
{
int n;
string c;
cin>>n;
for(int i=;i<n;i++)
{
cin>>c;
cin>>p[c[]-'A'].a>>p[c[]-'A'].b;
}
string input;
stack <Matrix> s;
while(cin>>input)
{
int flag=,sum=;
for(int i=;i<input.length();i++)
{
if(input[i]>='A'&&input[i]<='Z')
s.push(p[input[i]-'A']);
else if(input[i]==')')
{
Matrix m2=s.top(); s.pop();
Matrix m1=s.top(); s.pop();
if(m1.b!=m2.a)
{
flag=;
break;
}
sum+=m1.a*m2.a*m2.b;
s.push(Matrix(m1.a,m2.b));
}
}
if(!flag)
cout<<"error"<<endl;
else
cout<<sum<<endl;
}
return ;
}
uva11111
这道题目跟上面的题目几乎类似，但还是搞了半天，就是普普通通的栈模拟，很经典的一道题，现在越来越喜欢uva上面刘汝佳的题目了，确实都很经典，但自己还是太弱了，智商又不够，只能慢慢积累了
链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2052
参看了一下别人的博客，吐槽一下，开始自己犯了低级错误，把int跟char混用
链接：http://m.blog.csdn.net/blog/cgl1079743846/7757457
我的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<stack>
using namespace std;
const int maxn=;
int k[maxn];
int cnt,flag;
typedef struct toy
{
int val,res;
};
stack <toy> s;
void work()
{
while(!s.empty())
s.pop();
toy temp;
temp.val=k[];
temp.res=abs(k[]);
s.push(temp);
for(int i=;i<cnt;i++)
{
if(s.empty())
return;
if(k[i]<)
{
if(abs(k[i])<s.top().res)
{
toy apple;
apple.val=k[i];
apple.res=abs(k[i]);
s.push(apple);
}
else return;
}
if(k[i]>)
{
if(s.top().val+k[i]==)
{
if(i!=cnt-)
{
s.pop();
s.top().res-=k[i];
}
else s.pop();
}
else return;
}
}
if(s.empty())
flag=;
}
int main()
{
int x;
char c;
while(~scanf("%d%c",&x,&c))
{
k[]=x;
cnt=;
flag=;
if(c!='\n')
{
while(scanf("%d%c",&k[cnt++],&c))
{
if(c=='\n')
break;
}
}
if(cnt%==)
work();
if(flag)
cout<<":-) Matrioshka!"<<endl;
else
cout<<":-( Try again."<<endl;
}
return ;
}
uva540
list专题的最后一题，用了模拟+队列
参考了一下这位大神的解题报告：http://blog.csdn.net/mistkafka/article/details/9472643
我的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int maxrank=;
const int maxn=;
int team[maxrank];
queue <int> que[maxn];
queue <int> bigQue;
int main()
{
int T;
int cases=;
while(scanf("%d",&T)!=EOF)
{
if(T==)
break;
while(!bigQue.empty())
bigQue.pop();
for(int i=;i<maxn;i++)
while(!que[i].empty())
que[i].pop();
int n;
memset(team,,sizeof(team));
for(int cas=;scanf("%d",&n)==;cas++)
{
for(int i=;i<n;i++)
{
int num;
scanf("%d%c",&num);
team[num]=cas;
}
}
printf("Scenario #%d\n",++cases);
while(true)
{
string cmd;
cin>>cmd;
if(cmd=="ENQUEUE")
{
int num;
cin>>num;
if(que[team[num]].empty())
bigQue.push(team[num]);
que[team[num]].push(num);
}
else if(cmd=="DEQUEUE")
{
int app=bigQue.front();
cout<<que[app].front()<<endl;
que[app].pop();
if(que[app].empty())
bigQue.pop();
}
else if(cmd=="STOP")
{
cout<<endl;
break;
}
}
}
return ;
}
接下来开始下一个专题Binary Trees，继续加油，总还是有很多不懂的东西，只有从头开始刷题，才能发现当年在刷一些简单数据结构时自己学得不扎实，以及遇到的各种问题
