【洛谷P3952】[NOIP2017]时间复杂度-白红宇

【洛谷P3952】[NOIP2017]时间复杂度

阅读量：4946 次

发布时间：2019-06-11

本文共 2548 字，大约阅读时间需要 8 分钟。

时间复杂度

对于 100%的数据：

很明显的模拟题

然而考试时还是爆炸了。。

调了一下午。。

蒟蒻表示不会离线操作。。

直接贴代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int t,m,ans,p,q,topc,topt,stack[110]; 6 string a,s1,s2,s3,s4,stackc[110]; 7 bool dayu(string x,string y) 8 { 9     if(x.length()
        
         y.length()) return 1;11     else return x>y;12 }13 int main()14 {15     scanf("%d",&t);16     while(t--)17     {18         topc=0;topt=0;19         bool f=1;20         ans=0;p=0;q=0;21         scanf("%d",&m);22         cin>>s1;23         int lens1=s1.length();    24         int i=4;25         if(lens1==4) q=0;26         else while(s1[i]!=')')27         {28             q=q*10+s1[i]-'0';29             i++;30         }31         while(m--)32         {33             cin>>a;34             if(a=="E")35             {36                 if(stack[topc]) p--;37                 topc--;38             }39             if(topc<0)40                 f=0;41             if(a=="F")42             {43                 cin>>s2>>s3>>s4;44                 if((s3=="n"&&s4!="n")||(s3!="n"&&s4!="n"&&dayu(s3,s4)))45                 {46                     topt=1;47                     while(m&&topt&&f)48                     {49                         cin>>a;50                         if(a=="F"){51                             topt++;52                             cin>>s2>>s3>>s4;53                             for(int j=1;j<=topc;j++)54                             if(stackc[j]==s2&&f) f=0;55                         }56                         else topt--;57                         m--;58                     }59                     if(topt) f=0;60                 }61                 else62                 {63                     for(int j=1;j<=topc;j++)64                     if(stackc[j]==s2&&f) f=0;65                     if(f)66                     {67                         stackc[++topc]=s2;68                         if(s3!="n"&&s4=="n")69                         {70                             stack[topc]=1;71                             p++;72                             ans=max(ans,p);73                         }74                         else stack[topc]=0;75                     }76                 }77             }78         }79         if(topc!=0||!f)80         {81             f=0;82             puts("ERR");83         }84         if(f&&ans==q)85          puts("Yes");86         else if(f)87          puts("No");88     }89     return 0;90 }