NOIP2017 D1T2 时间复杂度

本题用栈模拟，我感觉会写中缀表达式求值那种难度题的人就可以在NOIP上A了此题了。（虽然我挂了，凉了，我也要用嘶哑的声音呼喊出：这题真水）

用栈pop和push的时候 维护 有效循环层数、无效循环（l>r）层数、相同字母  ，每次退栈时更新答案，就OK了 。

还有就是字符串的读入和处理不能写挂。

（在判定ERR之后把剩下的东西读干净再走）

 

#include
     
      #define INF 1000000007using namespace std;int T,head,N,Map[200],cnt1,cnt2,res,ans;//cnt1有效循环 cnt2无效循环 char s[50];struct Node{    char c;int a,b;}Stack[200];int getint(){    int sum=0,i=0,len=strlen(s);    while(s[i]<'0'||s[i]>'9')i++;    while(s[i]>='0'&&s[i]<='9'&&i<=len){sum=sum*10+s[i]-'0';i++;}    return sum;}void Pop(){    Map[Stack[head].c-'a'+1]=0;    if(Stack[head].a>Stack[head].b)cnt2--;    if(Stack[head].b==INF&&Stack[head].a!=INF&&cnt2==0)cnt1--;    head--;}void Push(Node x){    Map[x.c-'a'+1]=1;    if(x.a>x.b)cnt2++;    else if(x.b==INF&&x.a!=INF&&cnt2==0)cnt1++,res=max(res,cnt1);    Stack[++head]=x;}void ToError(int x){    for(int i=x+1;i<=N;i++){        scanf("%s",s);        if(s[0]=='F'){scanf("%s",s);scanf("%s",s);scanf("%s",s);}    }}int main(){    scanf("%d",&T);    while(T--){        while(head>0)Pop();        res=0;        scanf("%d%s",&N,s);        if(s[2]=='n'){ans=getint();if(!ans)ans=1;}        else ans=0;        for(int i=1;i<=N;i++){            scanf("%s",s);            if(s[0]=='F'){                Node x;                scanf("%s",s);x.c=s[0];                scanf("%s",s);                if(s[0]=='n')x.a=INF;else x.a=getint();                scanf("%s",s);                if(s[0]=='n')x.b=INF;else x.b=getint();                if(Map[x.c-'a'+1]){                    ToError(i);                    puts("ERR");goto New;                }                Push(x);            }            else{                if(head==0){                    ToError(i);                    puts("ERR");goto New;                }                Pop();            }        }        if(head>0)puts("ERR");        else if(ans==res)puts("Yes");        else puts("No");        New:    ;    }    return 0;    }