2020 表达式 · 方案二建树加关键性传播

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 3037 字
先算每个子树的值，再判断翻转它会不会影响根
2020
栈
正文

// CSP-J 2020 复赛 T3 · 表达式（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/CSPJ2020C
//
// 方案二 · 建表达式树，只算一次 + 判断「这个变量说了算不算」
// 每次都重算太浪费了。真正要回答的其实是：翻转这个变量，根的值会不会跟着翻？
// 于是建一棵表达式树，做两遍遍历：
//   第一遍（自底向上）：算出每个子树的值 val。
//   第二遍（自顶向下）：传播「关键性」crit —— 这个子树的值一变，根的值会不会变。
//     · 与节点 a & b：只有当另一边是 1 时，这边的变化才会影响结果；
//     · 或节点 a | b：只有当另一边是 0 时，这边的变化才会影响结果；
//     · 非节点 !a：这边一变结果必变，直接传下去。
// 根的 crit 设成 true（根变，答案当然变）。
// 最后：变量 xi 的答案 = 根的值 异或 (xi 所在节点是否关键)。
// 小技巧：节点是按「后序」创建的，子节点编号一定小于父节点，
// 所以顺着编号正着扫一遍算 val、倒着扫一遍传 crit 就够了，不用递归也不会爆栈。

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

const int MAXNODE = 1000005;

struct Node {
    int op;      // 0 变量，1 与，2 或，3 非
    int idx;     // 变量下标（op 为 0 时有效）
    int l, r;    // 左右儿子编号
    int val;
    bool crit;
} tr[MAXNODE];

int cnt = 0;
int varNode[1000005];

int newNode() {
    tr[cnt].op = 0;
    tr[cnt].idx = 0;
    tr[cnt].l = tr[cnt].r = -1;
    tr[cnt].val = 0;
    tr[cnt].crit = false;
    return cnt++;
}

int main() {
    freopen("expr.in", "r", stdin);
    freopen("expr.out", "w", stdout);

    string line;
    getline(cin, line);
    vector<string> tok;
    stringstream ss(line);
    string s;
    while (ss >> s) tok.push_back(s);

    stack<int> st;
    for (const string& t : tok) {
        if (t == "&" || t == "|") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            int u = newNode();
            tr[u].op = (t == "&" ? 1 : 2);
            tr[u].l = a;
            tr[u].r = b;
            st.push(u);
        } else if (t == "!") {
            int a = st.top(); st.pop();
            int u = newNode();
            tr[u].op = 3;
            tr[u].l = a;
            st.push(u);
        } else {
            int u = newNode();
            tr[u].op = 0;
            tr[u].idx = stoi(t.substr(1));
            varNode[tr[u].idx] = u;
            st.push(u);
        }
    }
    int root = st.top();

    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i];

    for (int u = 0; u < cnt; u++) {          // 自底向上算值
        if (tr[u].op == 0) tr[u].val = v[tr[u].idx];
        else if (tr[u].op == 1) tr[u].val = tr[tr[u].l].val & tr[tr[u].r].val;
        else if (tr[u].op == 2) tr[u].val = tr[tr[u].l].val | tr[tr[u].r].val;
        else tr[u].val = !tr[tr[u].l].val;
    }

    tr[root].crit = true;
    for (int u = cnt - 1; u >= 0; u--) {     // 自顶向下传关键性
        if (!tr[u].crit) continue;
        if (tr[u].op == 1) {
            if (tr[tr[u].r].val == 1) tr[tr[u].l].crit = true;
            if (tr[tr[u].l].val == 1) tr[tr[u].r].crit = true;
        } else if (tr[u].op == 2) {
            if (tr[tr[u].r].val == 0) tr[tr[u].l].crit = true;
            if (tr[tr[u].l].val == 0) tr[tr[u].r].crit = true;
        } else if (tr[u].op == 3) {
            tr[tr[u].l].crit = true;
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int idx;
        cin >> idx;
        int flip = tr[varNode[idx]].crit ? 1 : 0;
        cout << (tr[root].val ^ flip) << "\n";
    }
    return 0;
}
2020 表达式 · 方案二 建树加关键性传播

正文

CSP-J 标程 · 复赛真题的其它内容

2020 表达式 · 方案二建树加关键性传播
