算法

(栈，模拟，字符串处理) $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 \le y$，那么会循环 $O(1)$次，如果 $x > y$，那么一次也不执行；

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

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

语法错误有两种：

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

时间复杂度分析

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

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

const int N = 110;

string codes[N];

int get(string x, string y)
{
    if (x == "n" && y == "n") return 0;
    else if (x == "n") return -1;
    else if (y == "n") return 1;
    else if (stoi(x) <= stoi(y)) return 0;
    else return -1;
}

string calc(int L)
{
    int res = 0;
    stack<int> stk;
    string vars;

    for (int i = 0; i < L; i ++ )
    {
        auto& 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()) return "ERR";
            stk.pop();
            vars.pop_back();
        }
    }

    if (stk.size()) return "ERR";

    if (!res) 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();
        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;
}