CSP-J 2020 真题精讲(中):表达式

文章首发于公众号 CSP信奥资料交流共享，专注信息学奥赛资料与经验分享。

本期是「CSP-J/S 历年真题精讲」系列第 4 篇，精讲 CSP-J 2020 年 T3「表达式」—— 一道经典的表达式树 + DFS 题。

一、写在前面

CSP-J 2020 T3「表达式」被誉为历史上最难的 CSP-J 表达式题。题目不只考察表达式求值，还要求快速回答「翻转某个变量后，整个表达式的值会变吗」。

二、题目背景（原题精炼）

给定一个后缀表达式（也叫逆波兰表达式），包含：

• n 个布尔变量 x1, x2, ..., xn（取值 0 或 1）
• 逻辑运算符 &（与）、|（或）、!（非）
• 表达式长度可达 10^6

任务：有 q 个询问，每个询问给定一个变量编号 j，问：如果把 xj 的值翻转（0→1 或 1→0），整个表达式的值会变成什么？

数据范围：n <= 10^5，q <= 10^5，表达式长度 <= 10^6。

2.1 为什么不能暴力？

最直接的想法：每次询问就修改 xj，重新求值。但 q 可达 10^5，每次 O(n) 求值会超时。必须找到一种一次预处理、每次 O(1) 回答的方法。

三、考点分析

• 后缀表达式：运算符在操作数之后（如 "x1 x2 &" 表示 x1 & x2）
• 表达式树（二叉树）：用栈从后缀表达式建树，每个运算符是一个内部节点
• DFS（深度优先搜索）：第一次 DFS 求值，第二次 DFS 传播「影响标记」
• 大纲对应：提高级「栈」+「二叉树」+「DFS」

四、解题思路

思路 1：暴力（30 分）

每次询问翻转 xj 的值，用栈重新模拟一次后缀表达式求值。O(q * len)，当 q <= 100 时可过。

思路 2：建树 + 单次求值（50~70 分）

用栈从后缀表达式构建一棵表达式树，然后 DFS 求出整个表达式的值。想回答询问时还是得重新求值，没有本质优化。

思路 3：两次 DFS（100 分）✅

关键洞察：翻转一个变量 = 翻转了以该变量为叶子的子树。我们只需要知道「翻转这个子树会不会影响整棵树的根」。

第一次 DFS（自底向上）：计算每个节点的值。

第二次 DFS（自顶向下）：传播一个布尔标记 —— affected[node] 表示「改变这个节点的值是否会改变根的值」。

传播规则：

一句话理解：AND 是「短板」操作——一边是 1 时，另一边才能影响结果；OR 是「长板」操作——一边是 0 时，另一边才能影响结果。

4.1 影响规则的直观理解

以 AND 为例，x1 & x2 = 0 & 1 = 0：

• 翻转 x1 → 1 & 1 = 1，结果变了！→ x1 是受影响的
• 翻转 x2 → 0 & 0 = 0，结果没变 → x2 不受影响

为什么？因为 AND 结果主要被那个「0」控制（短板效应），只有翻转那个「短板」才影响结果。但如果两边都是 1（1 & 1 = 1），翻转任一边都会让结果变成 0。

4.2 回答询问

建好树后，对于询问「翻转 xj」：

• 如果 affected[xj] = true → 结果 = !root.val（翻转了结果）
• 如果 affected[xj] = false → 结果 = root.val（不变）

每次询问 O(1)！

五、完整代码

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

const int MAXN = 1000005;

// 表达式树节点
struct Node {
    char op;        // 运算符: '&', '|', '!', 'V' (变量), 'C' (常量)
    int val;        // 当前节点的值 (0或1)
    int left, right; // 左右子节点编号 (-1 表示无)
    bool affected;   // 改变此节点的值是否会改变根的值
} tree[MAXN];

int node_cnt = 0;   // 节点计数器
int var_node[MAXN]; // var_node[i]: 变量 xi 对应的节点编号

// 创建新节点
int new_node(char op, int l = -1, int r = -1) {
    tree[node_cnt].op = op;
    tree[node_cnt].left = l;
    tree[node_cnt].right = r;
    tree[node_cnt].affected = false;
    return node_cnt++;
}

// 第一次 DFS：自底向上求值
int dfs_eval(int u) {
    Node& nd = tree[u];
    if (nd.op == 'V' || nd.op == 'C') return nd.val;  // 叶子节点
    if (nd.op == '!') {
        nd.val = !dfs_eval(nd.left);
    } else if (nd.op == '&') {
        nd.val = dfs_eval(nd.left) & dfs_eval(nd.right);
    } else if (nd.op == '|') {
        nd.val = dfs_eval(nd.left) | dfs_eval(nd.right);
    }
    return nd.val;
}

// 第二次 DFS：自顶向下传播「影响标记」
void dfs_affect(int u) {
    Node& nd = tree[u];
    
    if (nd.op == '!') {
        // NOT: 子节点一定受影响
        tree[nd.left].affected = nd.affected;
        dfs_affect(nd.left);
    } else if (nd.op == '&') {
        int lv = tree[nd.left].val;
        int rv = tree[nd.right].val;
        
        if (nd.affected) {
            // AND 的短板效应
            if (lv == 1) tree[nd.right].affected = true;
            if (rv == 1) tree[nd.left].affected = true;
        }
        dfs_affect(nd.left);
        dfs_affect(nd.right);
    } else if (nd.op == '|') {
        int lv = tree[nd.left].val;
        int rv = tree[nd.right].val;
        
        if (nd.affected) {
            // OR 的长板效应
            if (lv == 0) tree[nd.right].affected = true;
            if (rv == 0) tree[nd.left].affected = true;
        }
        dfs_affect(nd.left);
        dfs_affect(nd.right);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string expr;
    getline(cin, expr);  // 读入后缀表达式
    
    int n;
    cin >> n;
    vector<int> val(n + 1);
    for (int i = 1; i <= n; i++) cin >> val[i];
    
    // 用栈构建表达式树
    stack<int> st;
    for (int i = 0; i < (int)expr.size(); i++) {
        char c = expr[i];
        if (c == ' ') continue;
        
        if (c == 'x') {
            // 解析变量编号（可能是多位数）
            i++;
            int num = 0;
            while (i < (int)expr.size() && isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            i--;
            
            int u = new_node('V');
            tree[u].val = val[num];   // 设置初始值
            var_node[num] = u;        // 记录对应节点
            st.push(u);
        } else if (c == '0' || c == '1') {
            int u = new_node('C');
            tree[u].val = c - '0';
            st.push(u);
        } else if (c == '!') {
            int child = st.top(); st.pop();
            int u = new_node('!', child);
            st.push(u);
        } else if (c == '&' || c == '|') {
            int r = st.top(); st.pop();
            int l = st.top(); st.pop();
            int u = new_node(c, l, r);
            st.push(u);
        }
    }
    
    int root = st.top();
    
    // 第一次 DFS：求表达式的值
    int root_val = dfs_eval(root);
    
    // 第二次 DFS：传播影响标记
    tree[root].affected = true;  // 根节点一定受影响
    dfs_affect(root);
    
    // 回答询问
    int q;
    cin >> q;
    while (q--) {
        int j;
        cin >> j;
        // 如果变量 xj 所在的节点受影响，翻转后结果取反
        if (tree[var_node[j]].affected) {
            cout << !root_val << "\n";
        } else {
            cout << root_val << "\n";
        }
    }
    
    return 0;
}

六、部分分策略

七、部分分策略总览

八、易错点与练习

常见失误：

1. 把后缀表达式当成中缀表达式来处理（这是最常见的理解错误）
2. AND 和 OR 的影响规则写反（AND=短板效应 / OR=长板效应）
3. NOT 节点是一元运算符，栈里只弹出一个子节点
4. 变量名可能是多位数（如 x123），需要用循环读完

练习题：

1. 洛谷 P7073 表达式 —— 本题原题，一定要亲手码一遍
2. 洛谷 P1449 后缀表达式 —— 后缀求值模板题
3. 洛谷 P1981 表达式求值 —— 中缀转后缀基础练习
4. 洛谷 P1175 表达式的转换 —— 中缀/后缀/前缀相互转换

九、下一期预告

CSP-J 2020 真题精讲（下）：方格取数

2020 年的压轴题 —— 方格取数是一道经典的 DP 题，涉及两个方向（上和左）的状态转移，更是 CSP-J 中少有的需要优化空间的动规题。下期带你彻底攻克！

关注公众号 CSP信奥资料交流共享，每日推送 CSP-J/S 真题精讲。「表达式」这题学会了，不仅 CSP-J 初赛复赛都受益，连 CSP-S 的表达式题也不怕！