线上OJ:
洛谷:https://www.luogu.com.cn/problem/P7073 (opens in a new tab)
acwing:https://www.acwing.com/problem/content/2771/ (opens in a new tab)
一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=2006 (opens in a new tab)
核心思想:
- 建表达式树
- 提前计算好哪些节点变化,会影响最终的值,存储在 isChange[] 数组中。最后查询时只要查询 isChange[] 数组即可
- 如何提前计算“哪些节点变化,会影响最终的值”
a. 0 & 1:左边的 0 如果变成1,会影响这个表达式的值从0 变1。右边的1不会
b. 0 & 0:左右两边任意一个数值变化,都不会影响表达式的值
c. 1 & 0:右边的 0 如果变成1,会影响这个表达式的值从0 变1。左边的1不会
d. 1 & 1:左右两边任意一个数值变化,都会影响表达式的值
e. 0 | 0:左右两边任意一个数值变化,都会影响表达式的值
f. 0 | 1:右边的 1 如果变成0,会影响这个表达式的值从1变0。左边的0不会
g. 1 | 0:左边的 1 如果变成0,会影响这个表达式的值从1变0。右边的0不会
h. 1 | 1:左右两边任意一个数值变化,都不会影响表达式的值
注:对于上述8种情况,如果某一边的数值变化会影响表达式的值,则对这条边进行深搜,继续检查它的左孩子和右孩子,谁会影响表达式的值,直到找到叶子节点做好标记。
因为表达式树,输入的数值都在叶子结点。只有运算符和运算结果才在分支节点。所以只要按照这 8 条规则,深搜到叶子节点即可。
- 核心的四句判断“哪些节点变化,会影响最终的值”的代码:
💡
令 chAnd[i][j][k]:表示 i & j 运算中第 k个数字发生变化能否影响结果
令 chOr[i][j][k]:表示 i | j 运算中第 k个数字发生变化能否影响结果
// & :如果左边的数改变后,表达式的值不同了,则返回true
chAnd[i][j][0] = ((i && j) != (!i && j));
// & :如果右边的数改变后,表达式的值不同了,则返回true
chAnd[i][j][1] = ((i && j) != (i && !j));
// | :如果左边的数改变后,表达式的值不同了,则返回true
chOr[i][j][0] = ((i || j) != (!i || j));
// | :如果右边的数改变后,表达式的值不同了,则返回true
chOr[i][j][1] = ((i || j) != (i || !j));
题解代码:
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
struct Node
{
int n; // n表示该节点的数值。举例 node[i]存储的是 x19的值0,则 node[i].n=0
int x; // x表示该结点对应的变量的编号。举例,存储的是 x19,则 node[i].x=19
char c; // 如果该节点是符号,则 c保存符号
int left, right; // 存储左孩子、右孩子的节点编号,即 node[i]的 i
};
Node node[N];
int p, n, x[100005];
bool isChange[100005]; //isChange[i]:xi变化后会影响整个表达式的值
bool chAnd[2][2][2], chOr[2][2][2];//chAnd[i][j][k]:i & j 运算中第 k个数字发生变化能否影响结果
void init() // 这里存储了规则3的8种情况
{
for(int i = 0; i <= 1; ++i)//i:第1个运算数
for(int j = 0; j <= 1; ++j)//j:第2个运算数
{
chAnd[i][j][0] = ((i && j) != (!i && j)); // & :如果左边的数改变后,表达式的值不同了,则返回true
chAnd[i][j][1] = ((i && j) != (i && !j)); // & :如果右边的数改变后,表达式的值不同了,则返回true
chOr[i][j][0] = ((i || j) != (!i || j)); // | :如果左边的数改变后,表达式的值不同了,则返回true
chOr[i][j][1] = ((i || j) != (i || !j)); // | :如果右边的数改变后,表达式的值不同了,则返回true
}
}
void dfs(int r)
{
if(node[r].left == 0 && node[r].right == 0) // 如果当前是叶子节点,则改变值就肯定改变了值,所以为 true
{
isChange[node[r].x] = true;
return;
}
int ln = node[node[r].left].n, rn = node[node[r].right].n; // 取出左节点的值, 和右节点的值
if(node[r].c == '&')
{
if(chAnd[ln][rn][0])
dfs(node[r].left);
if(chAnd[ln][rn][1])
dfs(node[r].right);
}
else if(node[r].c == '|')
{
if(chOr[ln][rn][0])
dfs(node[r].left);
if(chOr[ln][rn][1])
dfs(node[r].right);
}
else //!
dfs(node[r].right);
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
init(); // 初始化核心的四句判断语句
string s;
getline(cin, s); // 读取字符串
int num = 0, q, j;
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> x[i]; // 读入每一个变量 x[i]
stack<int> stk; // 存储数值的堆栈
for(int i = 0; i < s.length(); ++i)
{
if(s[i] == 'x') continue; // 如果读入的是x,则跳过
else if(s[i] >= '0' && s[i] <= '9') // 如果读入的是数字,则计算并存储至 num
num = num * 10 + s[i] - '0';
else if(s[i] == ' ') // 如果是空格,并且是 x19后面的空格,则存储 x19节点的数据
{
if(num > 0)
{
int np = ++p; // node节点编号
node[np].n = x[num]; // 将x19的值存储到 node[np].n
node[np].x = num; // 将参数索引号19存储到 node[np].x
stk.push(np); // 数值节点没有左右孩子,没有c。所以直接存储至堆栈
num = 0; // num清0
}
}
else // 到此处,s[i]就是符号了
{
int np = ++p; // node节点编号
node[np].c = s[i]; // 将s[i]存储到 node[np].c
node[np].right = stk.top(); // 将堆栈栈顶节点的编号存储到 右孩子
stk.pop(); // 栈顶元素即将被用于计算,故弹出
if(s[i] == '!') // 如果 s[i] 是!
node[np].n = !node[node[np].right].n; // 则将栈顶节点的数值取反
else // 如果是 & 或者 |
{
node[np].left = stk.top(); // 则将新的栈顶节点的编号存储到 左孩子
stk.pop();
if(s[i] == '&') // 如果是 & 或 | ,则重新计算数值后,存储至 n
node[np].n = node[node[np].left].n && node[node[np].right].n;
else
node[np].n = node[node[np].left].n || node[node[np].right].n;
}
stk.push(np); // 新的节点存储至堆栈。这个是分支节点,又有左右孩子,又有符号,也有自身的值
}
}
int root = stk.top(), val = node[root].n; // 栈顶节点的 n即为表达式的值
dfs(root);
cin >> q;
while(q--)
{
cin >> j;
if(isChange[j])
cout << !val << '\n';
else
cout << val << '\n';
}
return 0;
}