终于过了
查看原帖
终于过了
1154302
Sunrikis楼主2024/12/8 18:28
int L;
string t;
cin >> L >> t;

int cnt = 0;
vector<pair<string, int>> s(L);
vi p(L, -1);
for (int i = 0; i < L; i++) {
    string op, ch, st, ed;
    cin >> op;
    if (op == "F") {
        int o;
        cin >> ch >> st >> ed;

        auto cmp = [&](string a, string b) {
            if (a.size() == b.size()) return a[0] > b[0] ? (a[0] > b[0]) : (a[0] == b[0] ? a[1] > b[1] : false);
            return a.size() > b.size();
        };

        if (st == "n" && ed != "n") o = -1;
        else if (st != "n" && ed != "n" && cmp(st, ed)) o = -1;
        else if (st != "n" && ed == "n") o = 1;
        else o = 0;
        s[i] = {ch, o};
        cnt++;
    } else {
        cnt--;
        if (cnt < 0) cnt = -inf;
        s[i] = {"~", -1};
        for (int j = i - 1; j >= 0; j--) {
            if (s[j].first != "~" && p[j] == -1) {
                p[j] = i;
                p[i] = j;
                break;
            }
        }
    }
}

if (cnt) cout << "ERR\n";
else {
    vi st(L);
    unordered_map<string, int> mp;
    function<int(int, int)> work = [&](int l, int r) -> int {
        st[l] = st[r] = 1;
        if (l + 1 == r) {
            auto [i, o] = s[l];
            if (mp[i]) return -2;
            else return o;
        }

        auto [c, o] = s[l];
        if (mp[c]) return -2;
        mp[c] = 1;

        int res1 = 0, res2 = max(0, o);
        for (int i = l + 1; i < r; i++) {
            if (!st[i] && s[i].first != "~") {
                int f = work(i, p[i]);
                if (f == -2) return -2;
                if (o != -1) res1 = max(res1, f);
                else res1 = 0;
            }
        }
        mp[c] = 0;

        return res2 + res1;
    };

    int ans = 0;
    for (int i = 0; i < L; i++) {
        if (!st[i]) {
            int f = work(i, p[i]);
            if (f == -2) {
                cout << "ERR\n";
                return;
            }
            ans = max(ans, f);
        }
    }

    string O = "O(";
    if (ans == 0) O += "1)";
    else O += "n^" + to_string(ans) + ")";

    if (O == t) cout << "Yes\n";
    else cout << "No\n";
}
2024/12/8 18:28
加载中...