73分求调
查看原帖
73分求调
793394
yangxiaohai楼主2025/7/3 14:46

73分求条


#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <unordered_set>
#include <sstream>
using namespace std;

struct Loop {
    char var;
    string x, y;
    bool is_active;
};

int parseComplexity(const string& s) {
    if (s == "O(1)") return 0;
    size_t pos = s.find('^');
    if (pos != string::npos) {
        return stoi(s.substr(pos + 1, s.size() - pos - 2));
    }
    return 1; // O(n)
}

int calculateLoopComplexity(const string& x, const string& y) {
    if (x == "n" && y == "n") return 0;
    if (x == "n") return 0;
    if (y == "n") return 1;
    int xi = stoi(x), yi = stoi(y);
    return (xi <= yi) ? 0 : -1;
}

void processProgram(int L, const string& expected, vector<string>& lines) {
    stack<Loop> loopStack;
    unordered_set<char> activeVars;
    int max_power = 0;
    int current_power = 0;
    bool has_error = false;

    for (int i = 0; i < L; ++i) {
        string line = lines[i];
        if (line[0] == 'F') {
            istringstream iss(line.substr(1));
            char var;
            string x, y;
            iss >> var >> x >> y;

            if (activeVars.count(var)) {
                has_error = true;
            }
            activeVars.insert(var);

            int loop_complexity = calculateLoopComplexity(x, y);
            Loop newLoop{var, x, y, loop_complexity >= 0};
            loopStack.push(newLoop);

            if (newLoop.is_active) {
                current_power += loop_complexity;
                max_power = max(max_power, current_power);
            }
        } else if (line[0] == 'E') {
            if (loopStack.empty()) {
                has_error = true;
                continue;
            }
            Loop top = loopStack.top();
            loopStack.pop();
            activeVars.erase(top.var);
            if (top.is_active) {
                current_power -= calculateLoopComplexity(top.x, top.y);
            }
        }
    }

    if (!loopStack.empty()) {
        has_error = true;
    }

    if (has_error) {
        cout << "ERR" << endl;
        return;
    }

    int expected_power = parseComplexity(expected);
    cout << ((max_power == expected_power) ? "Yes" : "No") << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int L;
        string complexity;
        cin >> L >> complexity;
        vector<string> lines(L);
        cin.ignore();
        for (int i = 0; i < L; ++i) {
            getline(cin, lines[i]);
        }
        processProgram(L, complexity, lines);
    }
    return 0;
}

2025/7/3 14:46
加载中...