Codeforces 1011F Mars rover
题面在这里
题意：一棵有根树，叶子节点是输入值0/1，其他节点是运算符\(\text{And Or Xor Not}\)，分别询问每个叶子的输入值改变后，根的值变成什么
考虑到一个点的值不变，它到根路径上的值都不变
令\(f_i\)表示点i的值变化，根的值是否变化
初始\(f_1=true\)然后按照运算类型讨论一波就好了
示例程序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<cstdio>
const int maxn=1000006;
int n,son[maxn][2];
char s[maxn][5];
bool w[maxn],f[maxn];
void getw(int x){
if (s[x][0]=='A'){
getw(son[x][0]); getw(son[x][1]);
w[x]=(w[son[x][0]]&&w[son[x][1]]);
}else
if (s[x][0]=='O'){
getw(son[x][0]); getw(son[x][1]);
w[x]=(w[son[x][0]]||w[son[x][1]]);
}else
if (s[x][0]=='X'){
getw(son[x][0]); getw(son[x][1]);
w[x]=(w[son[x][0]]^w[son[x][1]]);
}else
if (s[x][0]=='N'){
getw(son[x][0]); w[x]=(!w[son[x][0]]);
}
}
void dp(int x){
if (!f[x]) return;
if (s[x][0]=='A'){
if (w[son[x][0]]) f[son[x][1]]=1;
if (w[son[x][1]]) f[son[x][0]]=1;
dp(son[x][0]); dp(son[x][1]);
}else
if (s[x][0]=='O'){
if (!w[son[x][0]]) f[son[x][1]]=1;
if (!w[son[x][1]]) f[son[x][0]]=1;
dp(son[x][0]); dp(son[x][1]);
}else
if (s[x][0]=='X'){
f[son[x][1]]=1;f[son[x][0]]=1;
dp(son[x][0]); dp(son[x][1]);
}else
if (s[x][0]=='N'){
f[son[x][0]]=1;
dp(son[x][0]);
}
}
int main(){
scanf("%d",&n);
for (int i=1,x;i<=n;i++){
scanf("%s",s[i]);
if (s[i][0]=='I') scanf("%d",&x),w[i]=(x==1);else
if (s[i][0]=='N') scanf("%d",&son[i][0]);else
scanf("%d%d",&son[i][0],&son[i][1]);
}
getw(1);
f[1]=1; dp(1);
for (int i=1;i<=n;i++)
if (s[i][0]=='I') putchar((f[i]^w[1])?'1':'0');
return 0;
}
|
