��վ�ܷ�������

堆栈模拟——时间复杂度

昨日终于把去年毒瘤模拟打了一下,真的是一生的痛。。。。

解法参考dimension tripper

实际是不改的和他一模一样就无法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;
}