专栏文章

题解：P7073 [CSP-J2020] 表达式

eemmoy
P7073题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqnw0hs
此快照首次捕获于
2025/12/04 07:52
3 个月前
此快照最后确认于
2025/12/04 07:52
3 个月前
查看原文

题目大意

给你一个后缀表达式，每个数都是 0 或 1，运算只有 |、& 和 !，即与、或、非。
然后有 qq 个询问，每个询问给出一个 ii，求出将第 ii 个元素取反后表达式的值。

思路

读入

题目十分良心，直接给了我们后缀表达式，所以我们可以边读入边转换，不用考虑优先级。
会后缀表达式的朋友可以直接跳到下一步。

后缀表达式的计算规则

后缀表达式的计算通常使用栈这种数据结构来实现，计算过程遵循以下规则：
当遇到数字时，直接将其推入栈中。
当遇到运算符时，从栈中弹出两个元素，先弹出的元素作为右操作数，后弹出的元素作为左操作数，执行运算后，将结果再次推入栈中。
例如，后缀表达式 1 0 & 1 ! | 1 0 | & 的计算过程如下：
从左到右扫描，首先将 1 和 0 依次推入栈中。
遇到并运算 &，弹出 1 和 0，计算 1&0 得 0，将 0 推入栈中。
接下来是 1，推入栈中。
遇到非运算 !，弹出 1，计算 !1 得 0，将 0 推入栈中。
遇到或运算 |，弹出 0 和 0，计算 0|0 得 0，将 0 推入栈中。
接着是 1 和 0，依次推入栈中。
遇到或运算 |，弹出 1 和 0，计算 1|0 得 1，将 1 推入栈中。
最后一个运算符是并运算 &，弹出 0 和 1，计算 0&1 得 0，将 0 推入栈中。
最终，栈中只剩下一个元素 0，这就是后缀表达式的计算结果。

询问

求出表达式的值就十分简单了，但是每一个元素都跑一次表达式复杂度会到达 O(q∣s∣)\mathcal{O}(q|s|)，是不允许的。
我们考虑将一个值取反后，表达式只会有两种情况，分别是取反和不变。
于是我们可以预处理出每个元素取反后表达式的值会不会取反，单次查询的复杂度就可以变成 O(1)\mathcal{O}(1) 了。
我们可以对其建一棵二叉树，每个节点由两个儿子运算得来，叶子节点即为输入节点。
具体预处理请看代码。

code

CPP
#include<bits/stdc++.h>
using namespace std;
int s[1000008],cnt,p;
// s是栈，cnt是栈内元素个数，p是树的节点个数。
int n,m,b[1000009],flag[1000008],son[1000009][3],k[1000009];
//b[i]表示树上节点i的运算符类型（非叶子结点）或真假（叶子结点）。
//flag[i]表示i点是否取反。
//son[i][1]和son[i][2]分别表示左右儿子。
//k[i]=1表示这个点的变动不会影响结果，k[i]=0反之。
string t;
int dfs(int c,int f)//c是哪个节点，f是是否取反。
{
	b[c]^=f;//表达式a|b取反后是(!a)&(!b)，a&b取反后是(!a)|(!b)，运算符会改变。
    //而由于2^1=3，3^1=2，正好完成取反。
	if(c<=n) return b[c];//如果是叶子结点，则直接返回。
	int x=dfs(son[c][1],f^flag[son[c][1]]);//祖先是否取反和该节点是否取反可能会抵消。
	int y=dfs(son[c][2],f^flag[son[c][2]]);
	if(b[c]==2)
	{
        //当a&0或0&a时，表达式的值绝对与a无关，标记即可。
		if(x==0) k[son[c][2]]=1;
		if(y==0) k[son[c][1]]=1;
		return x&y;
	}
	else
	{
      //同理当a|1或1|a时，表达式的值绝对与a无关，标记即可。
		if(x==1) k[son[c][2]]=1;
		if(y==1) k[son[c][1]]=1;
		return x|y;
	}
}
void dfs2(int c)//下传k，因为如果x的祖先与表达式的值无关，那么x也肯定无关。
{
	if(c<=n) return;
	k[son[c][1]]|=k[c];
	k[son[c][2]]|=k[c];
	dfs2(son[c][1]);
	dfs2(son[c][2]);
}
int main()
{
	getline(cin,t);
	scanf("%d",&n);
	p=n;//原来就有n个点。
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=0;i<t.size();i+=2)//i+=2是因为有空格。
	{
		if(t[i]=='x')
		{
			int x=0;
			i++;
			while(t[i]!=' ') x=x*10+t[i]-'0',i++;
			i--;
			s[++cnt]=x;
		}
		if(t[i]=='&')
		{
			int x=s[cnt];
			cnt--;
			int y=s[cnt];
			cnt--;
			s[++cnt]=++p;
			b[p]=2;//2代表&运算。
			son[p][1]=x,son[p][2]=y;
		}
		if(t[i]=='|')
		{
			int x=s[cnt];
			cnt--;
			int y=s[cnt];
			cnt--;
			s[++cnt]=++p;
			b[p]=3;//3代表|运算。
			son[p][1]=x,son[p][2]=y;
		}
		if(t[i]=='!') flag[s[cnt]]^=1;//取反操作。
	}
	int ans=dfs(p,flag[p]);//ans为原表达式的值。
	dfs2(p);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int x;
		scanf("%d",&x);
		printf("%d\n",(k[x]?ans:!ans));
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...