噫,我A了!
虽然有题解的帮助
这个题思路不难,但编出来非常难。
题解(正文)
把每个式子想象成一个树的节点,TREE结构。每个变量直接是个数值。
例如:
x1 & x2(这可以想象成一个节点,是tree[i])
把样例一的图画出来是:
建树过程具体看代码。。。
找规律
建树以后,可以轻易求出不改变变量时的答案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;
}
}