【洛谷 P7073】【2020 CSP-J】 表达式 题解

【洛谷 P7073】【2020 CSP-J】 表达式 题解

题目

---

解题思路

奇怪小知识
$sscanf$
从空终止字符串读取数据

string s="1 2 3 12 13 123"
int a;
sscanf(s,"%d",&a);

a为1

手写暴力栈
读入的是一个后缀表达式
很明显要用栈
接下来会有q个询问
如果改变其中某个值
是否会改变最终答案

那么我们就是求某个值会不会对最终答案造成影响
定义f[i]为这个值或运算会对那个值或运算造成直接影响
分为三种情况

• 运算符为！
  直接改变当前栈顶的值
  所以f[x]=i
• 运算符为|
  如果另一边的值为1就无法造成影响
  if (!y) f[x]=i;
  if (!x) f[y]=i;
• 运算符为&
  如果另一边的值为0就无法造成影响
  if (y) f[x]=i;
  if (x) f[y]=i;

最后每次回溯一遍
如果最后返回的值为1
说明最终答案会被改变
将最终答案取反

---

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct hhx{
	int id,q;
}st[100010],x,y; 
int n,l,t,res,m,j,k;
int xw[1000010],a[1000010],e[2000010],f[1000010];
char ss[2020];
int main()
{
    while (1)
	{
		  cin>>ss; 
		  if (ss[0]<='9'&&ss[0]>='0') break;  //读完表达式，读到了n
		  l++;
		  if (ss[0]=='x')  //第几个数
		  { 
		  	 sscanf(ss+1,"%d",&e[l]); 
			 xw[e[l]]=l; 
		  }
		  if (ss[0]=='&') e[l]=-1;
		  if (ss[0]=='|') e[l]=-2;
		  if (ss[0]=='!') e[l]=-3;  //运算符
	}	
	sscanf(ss,"%d",&n);  
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);  //读入具体数值 
	for (int i=1;i<=l;i++)
	{ 
		if (e[i]>=0) st[++t].id=i,st[t].q=a[e[i]];  //进栈
	    if (e[i]==-3)  //！
	    {
	    	x=st[t];
	    	st[t].id=i;
	    	st[t].q=!x.q;  //栈顶取反
	    	f[x.id]=i;  //一定会造成影响
		}
		if (e[i]==-2)
		{
			x=st[t]; 
			t--;
			y=st[t];
			st[t].id=i;
			st[t].q=x.q | y.q;   //做运算
			if (!x.q) f[y.id]=i;  
			if (!y.q) f[x.id]=i;  //判断是否会有影响
		}
		if (e[i]==-1)
		{
		   x=st[t];
		   t--;
		   y=st[t];
		   st[t].id=i;
		   st[t].q=x.q & y.q;  //做运算
		   if (x.q)	f[y.id]=i;
		   if (y.q) f[x.id]=i;   //判断是否会有影响
		} 
	}
	res=st[t].q;
	scanf("%d",&m); 
	for (int i=1;i<=m;i++)
	{
		scanf("%d",&j);
		for (k=xw[j];f[k];k=f[k]);  //回溯改变，如果最后返回1，说明最终答案被改
		if (k==l)
		   printf("%d\n",!res);  //取反输出
		   else printf("%d\n",res);  //没有影响
	}
	return 0;
}