ACM学习笔记__week3

前言

ACM_week3 这周莫名其妙多了个NECCS竞赛，还是花一点时间准备叭，暂时还没做完，会补题的555

提示：以下是本周训练题目，下面代码可供参考

一、栈

输入输出略
翻译过来的题目大意大概就是给出两个序列A、B，判断是否能通过栈使得A转换成B。
思路：将A的序列存入Stack数组与B序列一一比较。
代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
char in[20000],out[20000];//存入输入、输出字符串
char Stack[20000];//模仿栈的数组
bool Move[50000];//记录进栈出栈 true进false出
int main()
{int n;while(scanf("%d",&n)!=EOF){int top=-1;int pop=0;int len=0;memset(in,0,sizeof(in));memset(out,0,sizeof(out));memset(Stack,0,sizeof(Stack));memset(Move,0,sizeof(Move));scanf("%s %s",&in,&out);for(int i=0; i<n; i++){Stack[++top]=in[i];Move[len++]=true;while(Stack[top]==out[pop]&&top>=0){top--;Move[len++]=false;pop++;}}if(pop==n){printf("Yes.\n");for(int i=0; i<len; i++)if(Move[i]){printf("in\n");}else{printf("out\n");}printf("FINISH\n");}elseprintf("No.\nFINISH\n");}return 0;
}

二、链表

思路：用数组模拟全过程就好啦，但是要注意输出的是最初的编号。
代码如下（示例）：

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;int main()
{int N;int member[5010];scanf("%d",&N);while(N--){int n;scanf("%d",&n);memset(member,0,sizeof(member));for(int i=1;i<=n;i++){member[i]=i;}int len=n;int mod=2;while(len>3){int k=0;if(mod==2){for(int i=1;i<=n;i++){if(member[i]&&++k==2){k=0;member[i]=0;len--;}}mod=3;}else{for(int i=1;i<=n;i++){if(member[i]&&++k==3){k=0;member[i]=0;len--;}}mod=2;}}int cnt=0;for(int i=1;i<=n;i++){if(member[i]){if(cnt==0){cout<<i;cnt=1;}else{cout<<" "<<i;}}}cout<<endl;}return 0;
}

三、栈

思路：一组一组存入进行计算，遇到加减cnt自增后直接保存，遇到乘除就cnt不自增对上一个数进行计算。题倒不难，但是真的卡了我好久，最后发现是编译器版本的问题…
代码如下（示例）：

#include <iostream>
#include<cstdlib>
#include<cstring>
using namespace std;int main()
{double str[205];double a;char op;double num;char space;int cnt=0;while(scanf("%lf",&a)!=EOF){char ch=getchar();if(a==0&&ch=='\n'){break;}memset(str,0,sizeof(str));cnt=0;str[++cnt]=a;while(scanf("%c %lf%c",&op,&num,&space)!=EOF){if(op=='+'){cnt++;str[cnt]=num;}else if(op=='-'){cnt++;str[cnt]=-num;}else if(op=='*'){str[cnt]*=num;}else if(op=='/'){str[cnt]/=num;}if(space!=' '){break;}}double ans=0;for(int i=1;i<=cnt;i++){ans+=str[i];}printf("%.2lf\n",ans);}return 0;
}

总结