(栈，模拟，字符串处理) (O(TL^2) )

循环的时间复杂度取决于最内层的计算次数，即嵌套最深的一层循环的计算次数。

循环的嵌套和括号序列的嵌套类似，所以我们可以借助栈来遍历整个代码序列。

当遇到FOR语句时，将该循环压入栈顶，当遇到END语句时，将栈顶的循环弹出。那么栈中从底到顶的序列就是当前循环从外到内嵌套的序列。

对于每层循环 FOR i x y，我们先判断它的计算次数cmp：

• (x ) 是 (n ) 时：
• (y ) 也是 (n )，那么循环次数是 (O(1) )；
• (y ) 是正整数，由于 (n ) 远大于100，且 (x, y ) 在100以内，所以这个循环一次也不执行；
• (x ) 是正整数时：
• (y ) 是 (n ), 那么会循环 (O(n) ) 次；
• (y ) 是正整数，如果 (x <= y )，那么会循环 (O(1) ) 次，如果 (x > y )，那么一次也不执行；

然后判断整个循环嵌套序列的计算次数：

• 如果外层循环中的某一层执行次数是0或者当前循环的执行次数是0，那么当前这层的计算次数就是0；
• 否则当前这层的循环次数就是上一层循环的执行次数乘以前面判断出的循环次数 cmp；

语法错误有两种：

1. 对于当前循环创建的变量，如果在栈中已经出现过，说明与外面的某一层循环的循环变量重名了，产生语法错误；
2. 如果遍历过程中对空栈执行弹出操作，或者遍历结束后栈不为空，说明FOR语句与END语句不匹配，产生语法错误。

时间复杂度分析

总共有 (T ) 个测试数据，对于每个测试数据，每个循环会进栈一次，出栈一次，每次进栈之前会循环一遍栈中所有元素，判断是否存在变量重名的情况，所以总时间复杂度是 (O(TL^2) )。

#include<bits/stdc++.h>
using namespace std;
const int N=110;
string codes[N];
int get(string x,string y) //计算当前这一层的时间复杂度
{
    if(x=="n"&&y=="n") return 0; //表示o(1)
    else if(x=="n") return -1;//表示不会执行
    else if(y=="n") return 1;
    else if(stoi(x)<=stoi(y)) return 0;
    return -1;
}
string calc(int L)
{
    int res=0;//最大值
    stack<int> stk;//上一层的时间复杂度
    string vars;//已经有的变量
    for(int i=0;i<L;i++)
    {
        string s=codes[i];
        if(s[0]=='F')
        {
             char var[2],x[4],y[4];
            sscanf(s.c_str(),"F %s %s %s",var,x,y);//读入到字符数组之中
            if(vars.find(var)!=-1) //说明这个变量在前面出现过了
            {
                return "ERR";
            }
            vars+=var;//累加变量
            int t=get(x,y); //计算当前这一层的时间复杂度
            if(stk.empty())
            {
                stk.push(t),res=max(res,t);
            }
            else
            {
                int top=stk.top();
                if(top==-1||t==-1) //没有计算次数
                {
                    stk.push(-1);
                }
                else
                {
                    stk.push(top+t);//累加时间复杂度
                    res=max(res,top+t);
                }
            }
        }
        else
        {
            if(stk.empty())  //没有F可以出去
            {
                return "ERR";
            }
            stk.pop(); //删除当前层
            vars.pop_back();//删除最后一个
        }
    }
    if(stk.size()) //还存在多余的F
    {
        return "ERR";
    }
    if(res==0) return "O(1)";
    return "O(n^"+to_string(res)+")";
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int L;
        string str;
        cin>>L>>str;
        getchar();//过滤str后面的空行
        for(int i=0;i<L;i++)
        {
            getline(cin,codes[i]);
        }
        string res=calc(L);//计算当前表达式的时间复杂度
        if(res=="ERR") cout<<res<<endl;
        else if(res==str) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}