♐ CSP_J 组真题
2020年
3. 表达式

线上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)

核心思想:

  1. 建表达式树
  2. 提前计算好哪些节点变化,会影响最终的值,存储在 isChange[] 数组中。最后查询时只要查询 isChange[] 数组即可
  3. 如何提前计算“哪些节点变化,会影响最终的值”
    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 条规则,深搜到叶子节点即可。

  1. 核心的四句判断“哪些节点变化,会影响最终的值”的代码:
💡

令 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;
}