[CSP-J 2020] 表达式

GitHub 跳转原题关系图返回列表

先按后缀表达式建树并求当前值，再从根向下传播“能否影响根”的标记，这样每个翻转询问都能 O(1) 回答。

OJ: luogu

题目 ID: P7073

难度:普及+/提高

标签:栈字符串思维

日期: 2026-06-19 21:43

题意

给出一个后缀表达式，以及每个变量的初始 $0/1$ 取值。

每次询问翻转某一个变量的值，其余变量保持初始值不变，问整个表达式的新值。

思路

最直接的办法是每次询问都重新扫一遍整条后缀表达式。

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75#include <bits/stdc++.h>
using namespace std;

vector<string> split_tokens(const string &s) {
    vector<string> tokens;
    int n = (int)s.size();
    int i = 0;
    while (i < n) {
        while (i < n && s[i] == ' ') {
            ++i;
        }
        if (i >= n) {
            break;
        }
        int j = i;
        while (j < n && s[j] != ' ') {
            ++j;
        }
        tokens.push_back(s.substr(i, j - i));
        i = j;
    }
    return tokens;
}

int evaluate_once(const vector<string> &tokens, const vector<int> &value, int flip_id) {
    vector<int> st;
    st.reserve(tokens.size());

    for (const string &token : tokens) {
        if (token[0] == 'x') {
            int id = stoi(token.substr(1));
            st.push_back(value[id] ^ (id == flip_id));
        } else if (token == "!") {
            int x = st.back();
            st.pop_back();
            st.push_back(x ^ 1);
        } else {
            int right = st.back();
            st.pop_back();
            int left = st.back();
            st.pop_back();
            if (token == "&") {
                st.push_back(left & right);
            } else {
                st.push_back(left | right);
            }
        }
    }
    return st.back();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string expr;
    getline(cin, expr);
    vector<string> tokens = split_tokens(expr);

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

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << evaluate_once(tokens, value, x) << '\n';
    }
    return 0;
}

brute.cpp 对每个询问都重新模拟一次后缀表达式求值，逻辑简单，但复杂度是 $O(|s| \times q)$ ，显然不够。

关键观察：所有询问都基于同一组初始赋值，所以我们没必要每次都重算整棵表达式树。

建树

后缀表达式天然对应一棵表达式树，用栈就能建出来：

遇到变量 x_i：创建一个叶子节点，把节点编号入栈。
遇到一元运算符 !：从栈顶弹出一个节点作为孩子，创建非门节点，入栈。
遇到二元运算符 & 或 |：从栈顶弹出两个节点（先右后左），创建对应节点，入栈。

最后栈底剩下的就是根节点。

拿样例 x1 x2 & x3 | 举例，建树过程：

text

1
2
3
4
5读 x1 → 栈: [1]       (节点1 = x1)
读 x2 → 栈: [1,2]     (节点2 = x2)
读 &  → pop 2,1 → 栈: [3]   (节点3 = &, 孩子 left=1, right=2)
读 x3 → 栈: [3,4]     (节点4 = x3)
读 |  → pop 4,3 → 栈: [5]   (节点5 = |, 孩子 left=3, right=4)

最终得到的 节点5 就是根 |，它的左孩子是 & 节点，右孩子是 x3。

第一趟 DFS：自底向上求值

dfs1(u) 递归求节点 u 的值：

叶子节点（变量）：直接返回 init_val[var_id]。
非门：递归求孩子的值，取反。
与门：递归求左右孩子的值，lval & rval。
或门：递归求左右孩子的值，lval | rval。

这一趟结束后，每个节点都知道了自己的当前值，根节点的值就是整个表达式的值。

第二趟 DFS：自顶向下传播影响

核心问题是：翻转某个变量后，根的值会变吗？

答案取决于这个变量的改变能否沿着表达式树一路传到根。这就是 dfs2(u, about) 做的事。

about 表示“当前节点 u 的值发生变化时，是否会影响根节点的值”。

传播规则：

变量节点（叶子）：直接记录 can_affect[u] = about——这就是最终答案。
非门 !u：把 about 原样传递给子节点。因为 ! 只取反，孩子变了，非门的结果一定变。
与门 u & v：这里有关键的短路逻辑：
- 如果 about == false（整个 & 节点不影响根），两个孩子更不可能影响根，直接传 false。
- 如果 about == true，左孩子是否能影响根？答案是：只有当右孩子的当前值为 1 时。因为 0 & x = 0 已经被右路的 0 卡死，只有右路是 1 时 1 & 1 = 1 这个 1 才会随左路翻转。
或门 u | v：逻辑对称：
- 如果 about == false，两个孩子都传 false。
- 如果 about == true，左孩子是否能影响根？答案是：只有当右孩子的当前值为 0 时。因为 1 | x = 1 已经被右路的 1 卡死，只有右路是 0 时 0 | 0 = 0 这个 0 才会随左路翻转。

直观理解：

把 about 理解成一根从根放下来的绳子。每个门要么让绳子穿过去，要么剪断它。

! 永远让绳子通过。
& 只有当另一边是 1 时才让绳子通过。如果另一边是 0，绳子被卡断。
| 只有当另一边是 0 时才让绳子通过。如果另一边是 1，绳子被卡断。

最后一根绳子连到某个变量叶子节点上，就说明翻转这个变量能改变根的结果。

回答询问

预处理出 can_affect[] 后，每个询问就是 O(1)：

text

1
2
3
4如果 can_affect[var_pos[x]] == true:
    输出 root_val ^ 1
否则：
    输出 root_val

因为整个表达式树的所有输入都是确定的，翻转一个变量只会让路径上的节点值取反（如果它确实能影响根的话），所以根的值也一定取反，不存在其他情况。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2025-11-28 15:41
 * update_at: 2025-11-28 15:41
 */
/*
 * 题目：[CSP-J 2020] 表达式 (luogu 7073)
 * 核心思路：
 * 1. 表达式为后缀表达式，通过栈将其转化为表达式树。
 * 2. 第一次 DFS (dfs1)：从下往上求出所有节点原本的值。
 * 3. 第二次 DFS (dfs2)：从上往下传递"当前节点的改变是否会影响最终结果"。
 *    - 对于非门 (!)，影响直接向下传递。
 *    - 对于与门 (&)，如果另一半的值为 1，则本侧的改变会影响整体结果；否则被短路。
 *    - 对于或门 (|)，如果另一半的值为 0，则本侧的改变会影响整体结果；否则被短路。
 * 4. 预处理结束后，针对每个查询只需 O(1) 查表。
 */

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

// ===== 输入数据 =====
const int MAXN = 1e6+5;
int n, q;
int init_val[MAXN];
vector<string> tokens; // 后缀表达式的所有 token

// ===== 表达式树 =====
struct Node {
    char type; // 'x' 变量, '!' 非门, '&' 与门, '|' 或门
    int lch, rch;
    int var_id;
    int val;
} node[MAXN];
int node_cnt = 0;

int var_node[MAXN]; // 变量 x_i 对应的节点编号
stack<int> stk;

// ===== 预处理结果 =====
bool can_affect[MAXN]; // 该节点的变化是否影响根节点

// dfs1: 从下至上求出每个节点的值
int dfs1(int u) {
    if (node[u].type == 'x') {
        return node[u].val = init_val[node[u].var_id];
    }
    if (node[u].type == '!') {
        int child_val = dfs1(node[u].lch);
        return node[u].val = child_val ^ 1;
    }
    int lval = dfs1(node[u].lch);
    int rval = dfs1(node[u].rch);
    if (node[u].type == '&') {
        return node[u].val = lval & rval;
    }
    return node[u].val = lval | rval;
}

// dfs2: 从根向下传播"影响标记"
// affects_root: 当前节点的变化是否会影响根节点
void dfs2(int u, bool affects_root) {
    can_affect[u] = affects_root;
    if (node[u].type == 'x') return;
    if (!affects_root) {
        dfs2(node[u].lch, false);
        if (node[u].type != '!')
            dfs2(node[u].rch, false);
        return;
    }
    if (node[u].type == '!') {
        dfs2(node[u].lch, true);
        return;
    }
    int lch = node[u].lch, rch = node[u].rch;
    if (node[u].type == '&') {
        dfs2(lch, node[rch].val == 1);
        dfs2(rch, node[lch].val == 1);
    } else {
        dfs2(lch, node[rch].val == 0);
        dfs2(rch, node[lch].val == 0);
    }
}

// 读入表达式所有 token 和变量个数 n
void init_tokens() {
    string tok;
    while (cin >> tok) {
        if (tok[0] >= '0' && tok[0] <= '9') {
            n = stoi(tok);
            break; // 表达式 token 只含 x... ! & |，遇到数字就是 n
        }
        tokens.push_back(tok);
    }
}

// 根据全局 tokens 建立表达式树，返回根节点编号
int build_tree() {
    for (const string &tok : tokens) {
        if (tok[0] == 'x') {
            int id = stoi(tok.substr(1));
            node[++node_cnt] = {'x', 0, 0, id, 0};
            var_node[id] = node_cnt;
            stk.push(node_cnt);
        } else if (tok[0] == '!') {
            int child = stk.top(); stk.pop();
            node[++node_cnt] = {'!', child, 0, 0, 0};
            stk.push(node_cnt);
        } else {
            int right = stk.top(); stk.pop();
            int left  = stk.top(); stk.pop();
            node[++node_cnt] = {tok[0], left, right, 0, 0};
            stk.push(node_cnt);
        }
    }
    return stk.top();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init_tokens();
    for (int i = 1; i <= n; i++) {
        cin >> init_val[i];
    }

    int root = build_tree();
    dfs1(root);
    dfs2(root, true);

    cin >> q;
    int root_val = node[root].val;
    while (q--) {
        int x;
        cin >> x;
        if (can_affect[var_node[x]])
            cout << (root_val ^ 1) << '\n';
        else
            cout << root_val << '\n';
    }
    return 0;
}

复杂度

建树、求值、影响传播都是线性的，所以预处理复杂度是 $O(|s|)$ ，每个询问 $O(1)$ ，总复杂度是 $O(|s| + q)$ ，空间复杂度是 $O(|s|)$ 。

总结

这题的难点不在后缀表达式本身，而在看出"翻转一个变量是否有用"可以预处理。把"每次重算整式"改成"先判断哪些变量能影响根"，复杂度就从 $O(|s| \times q)$ 降到 $O(|s| + q)$ 。

另一个重要的思维是短路传播：二叉树中一个节点的值是否受子树影响，往往取决于另一个子树的值。这种"一侧卡死另一侧"的模式在表达式求值、决策树剪枝中都可能出现。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P7073 [CSP-J 2020] 表达式

题目描述

小 C 热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中，所有操作数都是变量，且它们的取值只能为 $0$ 或 $1$ ，运算从左往右进行。如果表达式中有括号，则先计算括号内的子表达式的值。特别的，这种表达式有且仅有以下几种运算：

与运算：a & b。当且仅当 $a$ 和 $b$ 的值都为 $1$ 时，该表达式的值为 $1$ 。其余情况该表达式的值为 $0$ 。
或运算：a | b。当且仅当 $a$ 和 $b$ 的值都为 $0$ 时，该表达式的值为 $0$ 。其余情况该表达式的值为 $1$ 。
取反运算：!a。当且仅当 $a$ 的值为 $0$ 时，该表达式的值为 $1$ 。其余情况该表达式的值为 $0$ 。

小 C 想知道，给定一个逻辑表达式和其中每一个操作数的初始取值后，再取反某一个操作数的值时，原表达式的值为多少。

为了化简对表达式的处理，我们有如下约定：

表达式将采用后缀表达式的方式输入。

后缀表达式的定义如下：

如果 $E$ 是一个操作数，则 $E$ 的后缀表达式是它本身。
如果 $E$ 是 $E_1~\texttt{op}~E_2$ 形式的表达式，其中 $\texttt{op}$ 是任何二元操作符，且优先级不高于 $E_1$ 、 $E_2$ 中括号外的操作符，则 $E$ 的后缀式为 $E_1' E_2' \texttt{op}$ ，其中 $E_1'$ 、 $E_2'$ 分别为 $E_1$ 、 $E_2$ 的后缀式。
如果 $E$ 是 $E_1$ 形式的表达式，则 $E_1$ 的后缀式就是 $E$ 的后缀式。

同时为了方便，输入中：

与运算符（&）、或运算符（|）、取反运算符（!）的左右均有一个空格，但表达式末尾没有空格。
操作数由小写字母 $x$ 与一个正整数拼接而成，正整数表示这个变量的下标。例如：x10，表示下标为 $10$ 的变量 $x_{10}$ 。数据保证每个变量在表达式中出现恰好一次。

输入格式

第一行包含一个字符串 $s$ ，表示上文描述的表达式。

第二行包含一个正整数 $n$ ，表示表达式中变量的数量。表达式中变量的下标为 $1,2, \cdots , n$ 。

第三行包含 $n$ 个整数，第 $i$ 个整数表示变量 $x_i$ 的初值。

第四行包含一个正整数 $q$ ，表示询问的个数。

接下来 $q$ 行，每行一个正整数，表示需要取反的变量的下标。注意，每一个询问的修改都是临时的，即之前询问中的修改不会对后续的询问造成影响。

数据保证输入的表达式合法。变量的初值为 $0$ 或 $1$ 。

输出格式

输出一共有 $q$ 行，每行一个 $0$ 或 $1$ ，表示该询问下表达式的值。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7x1 x2 & x3 |
3
1 0 1
3
1
2
3

输出 #1

text

输入输出样例 #2

输入 #2

text

1
2
3
4
5
6
7x1 ! x2 x4 | x3 x5 ! & & ! &
5
0 1 0 1 1
3
1
3
5

输出 #2

text

说明/提示

样例 1 解释

该后缀表达式的中缀表达式形式为 $(x_1 \operatorname{and} x_2) \operatorname{or} x_3$ 。

对于第一次询问，将 $x_1$ 的值取反。此时，三个操作数对应的赋值依次为 $0$ ， $0$ ， $1$ 。原表达式的值为 $(0\&0)|1=1$ 。
对于第二次询问，将 $x_2$ 的值取反。此时，三个操作数对应的赋值依次为 $1$ ， $1$ ， $1$ 。原表达式的值为 $(1\&1)|1=1$ 。
对于第三次询问，将 $x_3$ 的值取反。此时，三个操作数对应的赋值依次为 $1$ ， $0$ ， $0$ 。原表达式的值为 $(1\&0)|0=0$ 。

样例 2 解释

该表达式的中缀表达式形式为 $(\operatorname{not}x_1)\operatorname{and}(\operatorname{not}((x_2\operatorname{or}x_4)\operatorname{and}(x_3\operatorname{and}(\operatorname{not}x_5))))$ 。

数据规模与约定

对于 $20\%$ 的数据，表达式中有且仅有与运算（&）或者或运算（|）。
对于另外 $30\%$ 的数据， $|s| \le 1000$ ， $q \le 1000$ ， $n \le 1000$ 。
对于另外 $20\%$ 的数据，变量的初值全为 $0$ 或全为 $1$ 。
对于 $100\%$ 的数据， $1 \le |s| \le 1 \times 10^6$ ， $1 \le q \le 1 \times 10^5$ ， $2 \le n \le 1 \times 10^5$ 。

其中， $|s|$ 表示字符串 $s$ 的长度。

[CSP-J 2020] 表达式

目录

题意

思路

建树

第一趟 DFS：自底向上求值

第二趟 DFS：自顶向下传播影响

回答询问

代码

复杂度

总结

一图流解析