昨日终于把去年毒瘤模拟打了一下,真的是一生的痛。。。。
实际是不改的和他一模一样就无法AC垃圾洛谷竟无法AC,反正lojA了
思路
对于时间复杂度的计算,显然只用普通的模拟一定会爆炸
所以我们需要一个高级的模拟思路
循环的嵌套很麻烦于是需要用到队列或栈来搞一下
用一个队列或栈记录这层循环的变量
再用两个栈/队列记录这层循环的深度,就是到现在为止嵌套了几层
其中一个用来记录现在的深度。需用pop()/top–
另一个严格记录每层循环的深度,不用任何–操作,一直加就行
每读到一个E
就变量名出栈,一个记录现在深度的栈top–
最后跑一遍深度去max就行
代码
有很多细节需要注意!!!
特判要打好要么就是A不了
用来一个队列两个栈
#include <bits/stdc++.h>
using namespace std;
const int N=10000+110;
const int inf=(1<<30);
int n,m,stac[N],cnt,Case,o,flag,vis[N],len[N],cir[N],top,cir2[N],top1;
char ch[15],s[1200][20];
void get(char *a,int k)//手写gets
{
char ch=getchar();
len[k]=0;
while(ch!='\n')
{
s[k][++len[k]]=ch;
ch=getchar();
}
}
void getnum(int &a,int &b,int k)
{
int x;
for(int i=5;i<=len[k];i++)
{
if(s[k][i]==' '){x=i+1;break;}
if(s[k][i]=='n'){a=inf;break;}
a=a*10+s[k][i]-'0';
}
for(int i=x;i<=len[k];i++)
{
if(s[k][i]=='n'){b=inf;break;}
b=b*10+s[k][i]-'0';
}
}
int getnum2(char *s)
{
int ans=0;
for(int i=4;i<=strlen(s)-1;i++)
{
if(s[i]==')')break;
ans=ans*10+s[i]-'0';
}
return ans;
}
int main()
{
scanf("%d",&Case);
while(Case--)
{
queue<int>q;
flag=0;top=0;top1=0;
memset(s,0,sizeof(s));
memset(vis,0,sizeof(vis));
memset(cir,0,sizeof(cir));
memset(cir2,0,sizeof(cir2));
scanf("%d",&n);getchar();
scanf("%s",ch);getchar();
if(ch[2]=='1')o=0;
else o=getnum2(ch);
for(int i=1;i<=n;i++)
{
get(s[i],i);
if(flag)continue;
if(s[i][1]=='F')
{
if(vis[s[i][3]]){flag=1;continue;}
vis[s[i][3]]=1;
q.push(s[i][3]);
int up=0,down=0;
getnum(down,up,i);
if((down&&up&&down>up)||((s[i][5]=='n'&&s[i][len[i]]!='n')))//circulation is not existed
cir2[++top1]= cir[++top]=-inf;
else if(up==inf&&down!=inf)//o(n)
cir2[++top1]= cir[++top]=cir[top-1]+1;
else cir2[++top1]=cir[++top]=cir[top-1];//o(1)
}
else
{
if(q.empty())flag=1;
else vis[q.front()]=0,q.pop(),top--;
}
}
if(!q.empty())flag=1;
int ans=0;
for(int i=1;i<=top1;i++)
ans=max(ans,cir2[i]);
if(flag)
printf("ERR\n");
else if(ans==o)printf("Yes\n");
else printf("No\n");
}
return 0;
}