题解 P3952 【时间复杂度 】

· · 题解

这题主要是处理for语句的嵌套，和括号嵌套相似，有关嵌套的问题。可以想到用堆栈实现，这里用3个堆栈，一个处理嵌套，主要处理F和E是否对应。一个处理要增加复杂度（最后一个输入是n）的嵌套，该堆栈达到的最大值就是答案。最后一个堆栈处理不会进入循环的嵌套(for i = n to 1之类的），当这个堆栈大小为0时候。第二个堆栈才有用。具体看注释


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

int t,l;
//判断是否有效循环，能不能进入
bool nengxunhuan(string a,string b) {
  if (b=="n")
    return true;
  if (a=="n")
    return false;
  if (a.size()==b.size())
    return a<=b;
  else
    return a.size()<b.size();
}
int main() {
  scanf("%d", &t);
  for (int j=1;j<=t;j++) {
    int ans=0;
    bool err=false,zimu[200];//err标记是否语法错误，zimu数组用来记录变量是否用过
    stack<char> st,sn,wuxiao;//st处理嵌套，sn处理复杂度，wuxiao处理循环是否有效
    memset(zimu,0,sizeof(zimu));
    char c,i;string fzd,x,y;
    scanf("%d",&l);
    cin>>fzd;
    for (int k=1;k<=l;k++) {
      cin>>c;
      if (c=='E') {
        if (err) continue;
        if (st.empty()) {err=true;}//堆栈空了读入E，语法错误
        else {
          if (!sn.empty() && st.top()==sn.top())//sn同步出栈
            sn.pop();
          if (!wuxiao.empty() && st.top()==wuxiao.top())//wuxiao同步出栈
            wuxiao.pop();
          zimu[st.top()]=false;
          st.pop();
        }
      }
      if (c=='F') {
        cin>>i>>x>>y;
        if (err) continue;
        if (zimu[i]) {err=true;}
        else if (nengxunhuan(x, y)) {
          st.push(i);
          zimu[i]=true;
          if (x!="n" && y=="n" && wuxiao.empty()) {//当有效且右边是n，左边不同时为n，需要增加复杂度
            sn.push(i);
            if (sn.size()>ans) ans=sn.size();
          }
        }
        else {//无效循环，进入标记的堆栈
          st.push(i);
          zimu[i]=true;
          wuxiao.push(i);
        }
      }
    }
    if (!st.empty()) err=true;//缺少E
    if (err) cout<<"ERR"<<endl;
    else {
      if (ans==0 && fzd=="O(1)")
        cout<<"Yes"<<endl;
      else {//处理字符串的方式，主要是数字转字符，和字符串拼接，感觉这样写比较简洁。处理后和输入的复杂度字节字符串比较就可以了
        string ss="";
        while(ans>0) {
          ss+=ans%10+'0';
          ans/=10;
        }
        reverse(ss.begin(),ss.end());
        ss="O(n^"+ss+")";
        if (ss==fzd)
          cout<<"Yes"<<endl;
        else
          cout<<"No"<<endl;
      }
    }

  }
}