这个题是我$A$的第三百个……那么首先：

$\color{pink}AC300$祭！๑乛◡乛๑

嗯，那么下面开始干正事：

一、对于这个题的概述

先说明一下，这个题虽然我花了大约两个上午——大约$5h$的时间把它连码带调搞出来了，好像看上去很毒瘤，但是其实这个题根本不毒瘤，只是有些细节值得注意罢了。

不得不说，这是道很不错的题，因为既没有多么难，规则浅显易懂，也会有很多的细节不注意导致$GG$（本蒟蒻就几乎把所有这个题能得的分数遍历了一遍$ORZ$,多亏可以下载数据……不过考试的时候好像肯定会$GG$）

那么对于这道题我在做的时候就发现，出题人真的是太良心了，因为以下几点完全就是怕$NOIP$出的太难，来均衡难度的：

1、循环变量的上下界只有一个字母会出现：$$n$$

但是从渐进意义上来讲，任何一个字母都是可以的，而这个地方只出现了$n$,所以这是送分的。

毒瘤版本：

循环的上下界可以有别的字母，那么以下这种情况也需要考虑进总的时间复杂度，按照$O(n)$算：

F i x y
F j 1 i
E
E

那么这个时候就要牵扯到除了$n$以外的其他字母实现有没有被定义（如果未定义输出$ERR$）等诸多问题,比如可能这样：

F i 3 66
F j 1 i-1
F k i j
E
E
E

那么实际上，在上面这组样例中，$k$这层循环是进不去的。

2、所有常数都小于一百

这一点也很良心，由于都小于一百，所以我们在输入或者其他操作里，只用考虑两位就可以。不要小瞧这一点……这直接决定了模拟的难度。

毒瘤版本：

在每个循环中，循环变量的绝对值保证在$int$范围里。

3、时间复杂度方面，不会出现$log$以二为底

嗯，以上就是本蒟蒻$yy$出来的毒瘤版本，那么看起来这道题不算是个毒瘤题……但为什么会做错呢？因为细节不注意啊$ORZ$。

二、这个题的做法

我还是倒着说吧：

满分做法：

读入：

我们先用$while$按字符读入每个程序的第一行，抠出需要检验的复杂度，$O(1)$用$0$来存$[n^0=1 $ $~~~$ $ (n!=0)]$.

注意，有可能有两位数，需要多扣一位……

      while(o!=')'){
            if(o=='1'&&!chk) 
               need_check=0;
            if(o=='n'){
               cin>>o>>o;
               need_check=o-48;
               chk=1;
            }
            o=getchar();
            if(isdigit(o)&&chk)need_check*=10,need_check+=(o-48); 
       }
       getchar();

至于最后为什么要再$gatchar()$一次……自己试试就知道了。

那么接下来就要按行读入循环了，比较简单。

初始化：

为了使码风简洁，所以写到函数里了。这个地方我用到了三个栈，一个用来记录每个循环的答案（因为有可能有多个相互独立的循环），一个用来记录每次$F$时读入的循环上下界。以上两个都是$int$栈,还有一个$char$栈，存储每次定义的循环变量，而这个字符栈搭配一个$bool$性的数组，用于记录是否可用。

#define MAX 1000000
int i,x,y,t,tt,num,cntf,cnte,res,ans[MAX],T,l,now,need_checks,stk[MAX];
bool check[150],flag,spj,chk;
char s[3010],o,stkk[MAX]; 
inline void init(){
    memset(check,0,sizeof(check));
    memset(stkk,0,sizeof(stkk));
    memset(stk,0,sizeof(stk));
    now=t=tt=cntf=cnte=res=flag=spj=chk=0;
}

$ps:$虽然不知道用一个二进制位的$0$来初始化字符数组会怎样……不过好像海星。

$cnte$和$cntf$用来记录$F$和$E$的数量，$num$、$t$、$tt$都是栈的指针，$spj$用来判断一个独立循环是否结束（如果结束就把当前的得到压入栈）,$now$用来搭配$spj$记录当前独立循环体的时间复杂度， $chk$用于读入每个程序的第一行（即含有需要判断的时间复杂度的那一行），$flag$用于判断输出。

主要操作

对于读入的东西，分类讨论，然后$continue$……没什么可说的。

       while(l--){
          gets(s);
          for(i=0;i<strlen(s);){
                while(s[i]==' ')i++;
                if(s[i]=='F'){
                    if(cntf>cnte&&cnte){
                        ans[++num]=now;
                        now=0;
                    }
                    cntf++,i++;
                    continue;
                }
                if(s[i]=='E'){
                    y=stk[t],t--;
                    x=stk[t],t--;
                    cnte++;
                    if(cnte==cntf)spj=1;
                    if(x!=MAX){
                        if(y==MAX)now++;
                        if(y<x)now=0;
                    }
                    else{
                        if(y!=MAX)now=0;
                    }
                    check[stkk[tt]-'a']=0;
                    tt--,i++;
                    if(spj){
                        ans[++num]=now;
                        now=0;
                        spj=0;
                    }
                    continue;
                }
                if(!isdigit(s[i])&&s[i]!='n'){
                    if(check[s[i]-'a']&&!flag){ 
                    cout<<"ERR"<<endl;
                    flag=1;
                    }
                    stkk[++tt]=s[i];
                    check[s[i]-'a']=1;
                }
                else {  
                    if(s[i]=='n'){
                    my_push(s[i],s[i+1]);
                    i+=2;
                }               
                my_push(s[i],s[i+1]);
                }
                i++;
          }
       }

唯一需要注意的是入栈操作，因为要把字符压入整型，所以我又写了个函数来入栈。入栈的时候当然需要注意是不是两位数……

哦，还有，如果这次轮到$n$入栈了，那么就随便入栈一个大于一百的数即可。

inline void my_push(char a,char b){
    if(isdigit(a)){
        if(isdigit(b)){
            stk[++t]=(a-48)*10+b-48;
            i++;
        }
        else stk[++t]=a-48; 
    }
    if(a=='n')stk[++t]=MAX;
}

最后判断一下输入输出即可

       if(!flag&&cntf!=cnte){
          cout<<"ERR"<<endl;
          flag=1;
       }
       while(num){
           res=max(res,ans[num]); 
           num--;
       }
       if(!flag) if(res==need_check) cout<<"Yes"<<endl;
                 else                cout<<"No"<<endl;

嗯~o(￣▽￣)o这就是满分做法了。

$72$分做法

这个很坑爹……输出完直接$break$会导致你虽然在主观上已经不管这个询问接下来如何，但是客观上，你的程序是一边输入一边操作的，所以你接下来的输入就会$GG$，这也就是引入$mark$的原因。

$63$分做法

在72分的基础上，再输入$need_check$忘记判断$O(n^{11})$和$O(1)$了……这就很爆炸。

$45$分做法

没有考虑嵌套在循环中的循环体的独立性，那么我们可以发现，当你在读入一个$F$时，如果现在$F$的数量大于$E$的数量并且$cnte!=0$，就说明是这种情况那么就提前将结果入栈即可。

        if(s[i]=='F'){
            if(cntf>cnte&&cnte){
                ans[++num]=now;//提前入栈
                now=0;
            }
            cntf++,i++;
            continue;
        }

$27$分做法

忘记了自然数可以是两位数……所以赶紧打了个入栈。

$0$分做法

全部的爆零都是因为我忘记了把调试用的$freopen$注释掉ORZ。

总结：我认为这个题我在考场上挂的情有可原……因为我既蒟又不细心$OTZ$

还有，如果那位大佬$hack$掉了我的程序，别忘了通知我哇！

$\color{red}Code:$

#include<bits/stdc++.h>
#define MAX 1000000
using namespace std;
int i,x,y,t,tt,num,cntf,cnte,res,ans[MAX],T,l,now,need_check,stk[MAX];
bool check[150],flag,spj,chk;
char s[3010],o,stkk[MAX]; 
inline void init(){
    memset(check,0,sizeof(check));
    memset(stkk,0,sizeof(stkk));
    memset(stk,0,sizeof(stk));
    now=t=tt=cntf=cnte=res=flag=spj=chk=0;
}
inline void my_push(char a,char b){
    if(isdigit(a)){
        if(isdigit(b)){
            stk[++t]=(a-48)*10+b-48;
            i++;
        }
        else stk[++t]=a-48; 
    }
    if(a=='n')stk[++t]=MAX;
}
int main(){
    cin>>T;
    while(T--){
       init();
       cin>>l>>o;
       while(o!=')'){
            if(o=='1'&&!chk) 
               need_check=0;
            if(o=='n'){
               cin>>o>>o;
               need_check=o-48;//the same as above
               chk=1;
            }
            o=getchar();
            if(isdigit(o)&&chk)need_check*=10,need_check+=(o-48); 
       }
       getchar();
       while(l--){
          gets(s);
          for(i=0;i<strlen(s);){
                while(s[i]==' ')i++;
                if(s[i]=='F'){
                    if(cntf>cnte&&cnte){
                        ans[++num]=now;
                        now=0;
                    }
                    cntf++,i++;
                    continue;
                }
                if(s[i]=='E'){
                    y=stk[t],t--;
                    x=stk[t],t--;
                    cnte++;
                    if(cnte==cntf)spj=1;
                    if(x!=MAX){
                        if(y==MAX)now++;
                        if(y<x)now=0;
                    }
                    else{
                        if(y!=MAX)now=0;
                    }
                    check[stkk[tt]-'a']=0;
                    tt--,i++;
                    if(spj){
                        ans[++num]=now;
                        now=0;
                        spj=0;
                    }
                    continue;
                }
                if(!isdigit(s[i])&&s[i]!='n'){
                    if(check[s[i]-'a']&&!flag){ 
                    cout<<"ERR"<<endl;
                    flag=1;
                    }
                    stkk[++tt]=s[i];
                    check[s[i]-'a']=1;
                }
                else {  
                    if(s[i]=='n'){
                    my_push(s[i],s[i+1]);
                    i+=2;
                }               
                my_push(s[i],s[i+1]);
                }
                i++;
          }
       }
       if(!flag&&cntf!=cnte){
          cout<<"ERR"<<endl;
          flag=1;
       }
       while(num){
           res=max(res,ans[num]);
           num--; 
       }
       if(!flag) if(res==need_check) cout<<"Yes"<<endl;
                 else                cout<<"No"<<endl;
    }
}