我们把循环的嵌套关系看做树形结构，梳理一下\(3\)种情况：
-
直接跳过当前子树：
- \(x,y\in\mathbb{N}\)，且\(x>y\)。
- \(x=\tt{"n"},y\in\mathbb{N}\)。
-
不跳过，并在处理完所有子节点后追加\(n\)的时间复杂度：
- \(x\in\mathbb{N},y=\tt{"n"}\)。
-
不跳过，并不追加复杂度：
- 除上面\(2\)种以外的情况。
直接输入的同时处理即可，跳过子树用的方法是记录一个\(skip\)，当需要跳过某个子树时，就把当前调用深度\(dep\)赋给\(skip\)，在\(dep<skip\)之前，只进行输入和根据函数类型更改\(dep\)。
注意出现错误后仍需完成剩下的输入。
点击查看代码
#include<bits/stdc++.h>
#define L 110
#define int long long
using namespace std;
int t,dep,maxx[L],add[L],n,top;
bitset<26> vis;
char s2,st[L];
string com,s1,s3,s4;
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>t;
while(t--){
bool err=0;
int skip=LLONG_MAX;
maxx[0]=dep=top=0;
vis=0;
cin>>n>>com;
int i=1;
for(;i<=n;i++){
cin>>s1;
if(s1=="E"){
if(!dep){err=1;break;}
if((--dep)>=skip) continue;
if(skip!=LLONG_MAX){
skip=LLONG_MAX;
continue;
}
maxx[dep]=max(maxx[dep],maxx[dep+1]+add[dep+1]);
vis[st[top--]-'a']=0;
}else{
cin>>s2>>s3>>s4;
if(vis[s2-'a']){err=1;break;}
if((++dep)>=skip) continue;//如果dep>=skip则不执行
if((s3=="n"&&s4!="n")||(s3!="n"&&s4!="n"&&stoi(s3)>stoi(s4))){
skip=dep;
continue;
}
vis[s2-'a']=1,st[++top]=s2;
add[dep]=(s3!="n"&&s4=="n"),maxx[dep]=0;
}
}
if(dep) err=1;
if(err){
for(i++;i<=n;i++){
cin>>s1;
if(s1!="E") cin>>s2>>s3>>s4;
}
cout<<"ERR\n";
}else{
string ans=((!maxx[0])?"O(1)":"O(n^"+to_string(maxx[0])+")");
cout<<(ans==com?"Yes\n":"No\n");
}
}
return 0;
}