无心来刷令人发指的网络流的我今天终于填好了这个万人坑……
链接：https://www.luogu.org/problemnew/show/P3952
NOIP2017原题，各大针对OIer的OJ上应该都会出现。
这是一道数据多样化的模拟题……
用标准输入边输入边判错的代码量是很恐怖的。我辛辛苦苦地尝试了接近1.5h然后爆零。（Noip当天的情况）
今天最后决定采用字符串大法。把程序存下来先一遍判错然后才开始计算。同样也可以省掉程序错误时跳过一堆输入的判断。
1 #include2 char prog[101][100];//存放比对答案和程序3 stack hascomp;//循环是否使复杂度爬升（判断退出循环时是否需要减当前复杂度）
判错：只有两种错误情况，可以针对性地写。
1 bool errordeal(int &l){ 2 stack varin; 3 bool chuse[26];//变量判重 4 memset(chuse,0,sizeof(chuse)); 5 char ch; 6 for(int i=0;i<=l;++i){ //从1开始循环，因为prog[0]放了比对用的答案 7 switch(prog[i][0]){ 8 case'F': 9 sscanf(prog[i],"%*c %c",&ch);//（题面上说是一个小写字母）读变量10 if(chuse[ch-'a']){ //变量重复11 printf("ERR\n");12 return 1;13 }14 else{15 varin.push(ch);16 chuse[ch-'a']=1;//标记17 }18 break;19 case'E':20 if(varin.size()==0){ //F和E不匹配21 printf("ERR\n");22 return 1;23 }24 else{25 chuse[varin.top()-'a']=0;26 varin.pop();//清除标记27 }28 }29 }30 if(varin.size()){ //如果还有循环没清完就说明少了E，仍然错误31 printf("ERR\n");32 return 1;33 }34 return 0;35 }36 //有错返回1，无错返回0 判错完了之后就全是合法程序了。
不满足条件（初值比上界大）循环的处理
1 int unloopdeal(int now){ //接受当前行号 2 int need=1;//需要多少个E来结束当前循环块 3 for(int i=now+1;;++i){ 4 switch(prog[i][0]){ 5 case'F': 6 ++need; 7 break; 8 case'E': 9 --need;10 }11 if(!need) return i;//为0就说明到了这个循环块的结束，返回这个结束的行号12 }13 } 主程序：做输入及时间复杂度的统计。
1 int main(){ 2 int t,l,lvalue,rvalue,comp,maxcomp; 3 //t-组数，l-行数，lv-循环的初值，rv-循环的上界，comp-当前复杂度，mc-整体复杂度 4 //都写在这里是因为处理里面简直有够乱了 5 char ch,vari; 6 char ans[100]; 7 //ch-变量名，vari-判断上界和循环是n还是数字 8 scanf("%d",&t); 9 while(t--){10 comp=maxcomp=0;11 scanf("%d ",&l);12 memset(prog,0,sizeof(prog));13 for(int i=0;i<=l;++i) while((ch=getchar())!='\n') prog[i][strlen(prog[i])]=ch;//读入程序，顺便也读了O(balabala)14 if(errordeal(l)) continue;//有错直接读下一组数据；这组数据已经读完15 for(int i=1;i<=l;++i){16 switch(prog[i][0]){17 case'F':18 sscanf(prog[i],"%*c %c ",&ch);//读变量名19 sscanf(prog[i],"%*c %*c %c",&vari);//检查初值20 if(isdigit(vari)) sscanf(prog[i],"%*c %*c%d",&lvalue);21 else lvalue=-1;//是数字就读，如果不是数字（就是n）做标记-122 if(lvalue!=-1) sscanf(prog[i],"%*c %*c %*d %c",&vari);23 else sscanf(prog[i],"%*c %*c %*c %c",&vari);24 if(isdigit(vari)){25 if(lvalue!=-1) sscanf(prog[i],"%*c %*c%*d%d",&rvalue);26 else sscanf(prog[i],"%*c %*c %*c%d",&rvalue);27 } 28 else rvalue=-1;//和上面一个原理，但要判断初值是否为n，不然格式化字符串没法写29 if(lvalue==-1){30 if(rvalue!=-1) i=unloopdeal(i);//处理1：初值为n，上界为常数，无法进入循环31 else hascomp.push(0);//处理2：初值为n，上界为n，常数复杂度32 }33 else if(rvalue==-1){34 maxcomp=max(maxcomp,++comp);35 hascomp.push(1);//处理3：初值为常数，上界为n，复杂度爬升36 }37 else if(lvalue<=rvalue) hascomp.push(0);//处理4：初值为常数，上界为常数，且初值小于上界，常数复杂度38 else i=unloopdeal(i);//处理4：初值为常数，上界为常数，且初值大于上界，无法进入循环39 //无法进入循环，就跳行号40 break;41 case'E':42 if(hascomp.top()) --comp;43 hascomp.pop();//出乎意料的简单，只需要判断是否是常数复杂度，以确定减不减当前复杂度44 }45 }46 if(!maxcomp) sprintf(ans,"O(1)");47 else sprintf(ans,"O(n^%d)",maxcomp);48 if(!strcmp(ans,prog[0])) printf("Yes\n");49 else printf("No\n");//字符串比对，判断答案对错50 }51 exit(0);52 }