P7073 表达式 题解

噫,我A了!

虽然有题解的帮助

这个题思路不难,但编出来非常难。

题解(正文)


把每个式子想象成一个树的节点,TREE结构。每个变量直接是个数值。

例如:

​ x1 & x2(这可以想象成一个节点,是tree[i])

P7073 表达式 题解

把样例一的图画出来是:

P7073 表达式 题解

建树过程具体看代码。。。


找规律

建树以后,可以轻易求出不改变变量时的答案ans

x1|1=0; x1&0=0; 当x1,x2的初始值为零时,x1&x2=0(改变任何一个都没用);

  • 上面的式子显而易见,每个变量修改后都有可能对答案没用。

  • 如果把每个式子都看作一个数值或变量时,上面所列出的可以囊括所有情况。

我们还可以法现,若是一个节点是固定值(即式子的值恒定),那么,它的子树上的节点对答案也不会有影响。所以可以把它的子树标记一下。


看代码

#include<bits/stdc++.h>
using namespace std;
struct TREE
{
	int l,r,m;
}tree[1000005];
char s[1000005];
int vv[1000005];
int a[1000005];
int n;
bool d[1000005];
int DFS(int x)
{
	if(x<=n)
	 return vv[x]^a[x];

	int l1=DFS(tree[x].l);
	int r1=DFS(tree[x].r);
	
	//cout<<tree[x].m<<" >";
	if(tree[x].m==1)//&
	{
		if(l1==0) d[tree[x].r]=1;
		if(r1==0) d[tree[x].l]=1;
		return vv[x]^(l1&r1);
	}
	else//|
	{
		if(l1==1) d[tree[x].r]=1;
		if(r1==1) d[tree[x].l]=1;
		return vv[x]^(l1|r1);
	}
}
void DFSS(int x) 
{
	if(x<=n)
	 return ;	
	d[tree[x].l]|=d[x];
	d[tree[x].r]|=d[x];
	DFSS(tree[x].l);
	DFSS(tree[x].r);
}
int main() 
{
	gets(s);
	cin>>n;
	for(int i=1;i<=n;i++)
	 cin>>a[i];
	 
	int cr=n+1;
    stack<int> z;
    for(int i=0;s[i];i+=2)
     if(s[i]=='x')
     {
     	int zzz=0;
     	while(s[++i]!=' ')
   		 zzz=zzz*10+s[i]-'0';
   		i--;
   		z.push(zzz);
	 }
	 else
	  if(s[i]!='!')
	  {
	  	tree[cr].l=z.top(); z.pop();
	  	tree[cr].r=z.top(); z.pop();
	  	tree[cr].m=(s[i]=='&');z.push(cr); cr++;
	  }
	  else
	   vv[z.top()]^=1;
	
	int ans=DFS(z.top());
	DFSS(z.top());
	//cout<<ans<<endl<<endl;
	int q;
	cin>>q;
	while(q--)
	{
		int aa;
		cin>>aa;
		//cout<<vv[aa]<<"  "; 
		cout<<((1^d[aa])^ans)<<endl;
	}
}

上一篇:glibc中stl list::size()实现的延伸问题


下一篇:django 执行原生的sql