话说这题暴力是得不了满分吗
  • 板块P11186 三目运算
  • 楼主_zhang
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/10/13 12:33
  • 上次更新2024/10/13 14:27:07
查看原帖
话说这题暴力是得不了满分吗
556649
_zhang楼主2024/10/13 12:33

RT,还是我家string常数太大了?

#include <iostream>
#include <stack>
using namespace std;
const int N = 2e6 + 5;
int m, q;
string S;
int mat[N];
int to_num(const string &s) {
    int num = 0;
    for (int i = 0; i < s.size(); i++)
        if ('0' <= s[i] && s[i] <= '9')
            num = num * 10 + s[i] - '0';
    return num;
}
int analysis(int x, int l, int r) {
    //cout << "analysis(" << l << ", " << r << "): ";
    //cout << S.substr(l, r - l) << "...\n";
    if (S[l] != 'x')
        return to_num(S.substr(l, r - l));
    string sub;
    int t1 = 0;
    for (int i = l; i < r; i++) {
        if (S[i] == '?') { t1 = i; break; }
        sub += S[i];
    }
    int num = to_num(sub), op = sub[1];
    int t2 = mat[t1];
    if (op == '<' && x < num) return analysis(x, t1 + 1, t2);
    if (op == '>' && x > num) return analysis(x, t1 + 1, t2);
    return analysis(x, t2 + 1, r);
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    //freopen("expr4.in", "r", stdin);
    //freopen("expr.out", "w", stdout);
    cin >> m >> q;
    cin >> S;
    stack<int> sta;
    for (int i = 0; i < S.size(); i++) {
        if (S[i] == '?')
            sta.push(i);
        else if (S[i] == ':')
            mat[sta.top()] = i, sta.pop();
    }
    while (q--) {
        int x;
        cin >> x;
        cout << analysis(x, 0, S.size()) << '\n';
    }
    return 0;
}

2024/10/13 12:33
加载中...