思路:题意是说,火箭这个系统是用一颗树来表示的,树的叶子节点是输入,非叶子节点是一个逻辑判断。然后问你如果修改一个叶子节点的值。结果会变成什么。 叶子节点按从小到大输出修改该节点后 一号节点的值是多少。
其实是一个逻辑题。某一个节点的值会不会受到子节点的值影响,就是看子节点修改后会不会对该节点的值产生影响。如果会产生影响,那么这课子树的叶子节点就有可能产生影响。若不产生影响, 那么这棵子树的叶子节点不会产生影响。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{
int l, r, val;
char op;
}tree[N];
int n;
bool f[N];
int cal(int a, int b, char c){
if(c=='A')
return a&b;
else if(c=='O')
return a|b;
else if(c=='X')
return a^b;
}
int dfs1(int rt){
char ch=tree[rt].op;
if(ch=='I')
return tree[rt].val;
else if(ch=='A' || ch=='O' || ch=='X')
return tree[rt].val=cal(dfs1(tree[rt].l), dfs1(tree[rt].r), ch);
else if(ch=='N')
return tree[rt].val=!dfs1(tree[rt].l);
}
void dfs2(int rt, int cf){
char ch=tree[rt].op;
int l=tree[rt].l, r=tree[rt].r;
if(ch=='I')
f[rt]=cf;
else if(ch=='A' || ch=='O' || ch=='X'){
if(cf==0){
dfs2(l, 0), dfs2(r, 0); return;
}
if(cal(tree[l].val^1, tree[r].val, ch)!=tree[rt].val)
dfs2(l, 1);
else
dfs2(l, 0);
if(cal(tree[l].val, tree[r].val^1, ch)!=tree[rt].val)
dfs2(r, 1);
else
dfs2(r, 0);
}
else
dfs2(l, cf);
}
int main(){
scanf("%d", &n);
char op[10];
int l, r;
for(int i=1; i<=n; i++){
scanf("%s", op);
if(op[0]=='N'){
scanf("%d", &l);
tree[i].op=op[0];
tree[i].l=l;
}
else if(op[0]=='I'){
scanf("%d", &l);
tree[i].val=l; tree[i].op=op[0];
}
else{
scanf("%d %d", &l, &r);
tree[i].op=op[0];
tree[i].l=l; tree[i].r=r;
}
}
int ans=dfs1(1);//算出值;
dfs2(1, 1);//算每个节点的左右子树对该节点是否有影响,从而推出叶子节点是否有影响。
for(int i=1; i<=n; i++)
if(tree[i].op=='I')
printf("%d", f[i]?ans^1:ans);
puts("");
return 0;
}