A1411 [2017 S2] 时间复杂度

#include <bits/stdc++.h>
using namespace std;

// 时间复杂度（A1411，[2017 S2]）
//
// 逐行模拟：F 进栈、E 出栈；同时统计「当前嵌套了几层 n 次的循环」。
// 语法错误：F 与 E 不匹配，或变量在还没销毁时被重复定义。
// 复杂度 = 最大的 n 因子层数；一次都不执行的循环不计入。
struct Frame {
    char var;   // 循环变量
    bool dead;  // 循环体一次都不会执行
    bool addsN; // 这个循环贡献一个 n 因子
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int L;
        string claim;
        cin >> L >> claim;

        // 解析声称的复杂度：O(1) → 0，O(n^w) → w
        int claimed = 0;
        size_t pos = claim.find('^');
        if (pos != string::npos) claimed = stoi(claim.substr(pos + 1));

        vector<Frame> stk;
        vector<bool> alive(26, false);
        int depth = 0;    // 当前嵌套的 n 因子个数
        int maxDepth = 0; // 出现过的最大深度
        bool err = false;

        for (int i = 0; i < L; i++) {
            string op;
            cin >> op;
            if (op == "F") {
                char v;
                string x, y;
                cin >> v >> x >> y;
                if (alive[v - 'a']) err = true; // 变量还没销毁就重复定义
                alive[v - 'a'] = true;

                bool parentDead = !stk.empty() && stk.back().dead;
                bool dead = parentDead;
                if (x == "n") {
                    dead = true; // 起点是 n，终点是常数，一次都不执行
                } else if (y == "n") {
                    // 从常数数到 n，执行 n 次
                } else if (stoi(x) > stoi(y)) {
                    dead = true; // 起点比终点大，一次都不执行
                }
                bool addsN = (!dead) && (y == "n");
                if (addsN) depth++;
                maxDepth = max(maxDepth, depth);
                stk.push_back({v, dead, addsN});
            } else { // E
                if (stk.empty()) {
                    err = true; // 多出来的 E
                } else {
                    Frame f = stk.back();
                    stk.pop_back();
                    alive[f.var - 'a'] = false;
                    if (f.addsN) depth--;
                }
            }
        }
        if (!stk.empty()) err = true; // 还有 F 没有 E 闭合

        if (err) cout << "ERR\n";
        else if (maxDepth == claimed) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}