36分TLE求助
查看原帖
36分TLE求助
1387518
Bandysol楼主2024/10/13 12:15
#include <iostream>
using namespace std;

struct node {
    string exp;
    node* l;
    node* r;
};

string s;

int find_match(int n) {
    int dep=0;
    for (int i = n;i < s.size();++i) {
        if (s[i]=='?') dep++;
        else if (s[i]==':') dep--;
        if (dep==-1) return i;
    }
    return -1;
}
node* parse(int h, int l) {
    node* v = new node();
    for (int i = h;i < l;++i) {
        if (s[i]=='?') {
            int found = find_match(i+1);
            v->l = parse(i+1, found);
            v->r = parse(found+1, l);
            break;
        }
        v->exp+=s[i];
    }
    return v;
}

bool expr(string& s, int x) {
    int v = stoi(s.substr(2));
    if (s[1]=='>') {
        return x>v;
    } else {
        return x<v;
    }
}

int answer(node* p, int x) {
    if (p->exp.find('>')!=-1||p->exp.find('<')!=-1) {
        if (expr(p->exp, x)) {
            return answer(p->l, x);
        } else {
            return answer(p->r, x);
        }
    } else {
        return stoi(p->exp);
    }
}

int main() {
    int m, q;cin>>m>>q>>s;
    node* p = parse(0, s.size());
    for (int i = 0;i < q;++i) {
        int x;cin>>x;
        cout<<answer(p, x)<<endl;
    }
}
2024/10/13 12:15
加载中...