建议访问原文出处,获得更佳浏览体验。
原文出处:https://hyp1231.github.io/2018/07/28/20180728-cf1010d/
给出一个以
1
1
为根的有 个节点的树,树的每个节点表示一个输入,或者一个逻辑关系。每个逻辑关系根据儿子节点的值,套入逻辑关系式,计算出当前节点的值。
现在让你求出,只改变任一个输入节点的值,根节点的取值。
首先我们可以规定一个结构体 State
,定义如下:
struct State {
char s[4]; // 代表逻辑关系(或输入)的字符串
int next[2]; // 儿子节点标号
State() {
memset(s, 0, sizeof(s));
next[0] = next[1] = 0;
}
};
当逻辑关系为
AND,OR,XOR
A
N
D
,
O
R
,
X
O
R
时,next[0]
代表左儿子,next[1]
代表右儿子。
当逻辑关系为
NOT
N
O
T
时,next[0]
代表儿子。
当表示输入
IN
I
N
时,next[0]
代表输入的值(
0
0
或 )。
我们可以一次
dfs
d
f
s
求出每个节点的值,把它们记录在 ori[N]
数组中。
下面考虑怎么计算改变单一输入后根节点的值。
当一个输入改变时,它可以导致一系列节点的取值发生改变。而我们可以从根节点逆推,假设根节点的值改变了,考虑需要的条件。
先只考虑某个单一节点
u
u
,假设 的值改变了,分下面几种情况讨论:
u
u
是
如果节点
u
u
原来的取值是 ,说明两个儿子节点都是
1
1
。根据假设,节点 的值改变了,那么势必是因为两个儿子之一的值改变了。因此递归搜索两个儿子。(假设某个儿子的值改变了)
如果节点
u
u
原来的取值是 ,那么说明两个儿子节点至少有一个是
0
0
。根据假设,节点 的值改变了,如果两个儿子节点都是
0
0
,这个搜索分支结束(因为只改变一个输入无法使两个儿子节点的值全部改变);否则只有一个儿子节点是 ,递归搜索原来取值为
0
0
的那个儿子。
是
OR
O
R
和第一种情况同理,只需要根据逻辑表达式稍作修改。
u
u
是
说明两个儿子节点一个是
1
1
,另一个是 。根据假设,节点
u
u
的值改变了,那么势必因为两个儿子之一的值改变了。递归搜索两个儿子。
是
NOT
N
O
T
儿子的值改变了,递归搜索儿子节点。
u
u
是
输入改变了,记录这个
u
u
<script type="math/tex" id="MathJax-Element-35">u</script>,说明这个输入改变可以导致根节点的值发生改变。
这样我们就可以从根节点开始搜索,一步步假设某节点的值发生改变,推算出哪个输入的改变会导致根节点值的改变。输出时只要对于有标记的节点,改变根节点的输出即可;否则输出 ori[1]
。
#include <cstdio>
#include <cstring>
const int N = 1000010;
struct State {
char s[4];
int next[2];
State() {
memset(s, 0, sizeof(s));
next[0] = next[1] = 0;
}
} a[N];
int n, ori[N], vis[N]; // vis[i] 为 1,表示改变 i 节点会改变根节点的值
int dfs(int u) {
int l = a[u].next[0], r = a[u].next[1];
char op = a[u].s[0];
if (op == 'A') { // AND
return ori[u] = dfs(l) & dfs(r);
} else if (op == 'O') { // OR
return ori[u] = dfs(l) | dfs(r);
} else if (op == 'X') { // XOR
return ori[u] = dfs(l) ^ dfs(r);
} else if (op == 'N') { // NOT
return ori[u] = !dfs(l);
} else { // IN
return ori[u] = l;
}
}
void solve(int u) {
int l = a[u].next[0], r = a[u].next[1];
char op = a[u].s[0];
if (op == 'A') { // AND
if (ori[u] == 1) {
solve(l); solve(r);
} else {
if (ori[l] == 0 && ori[r] == 0) return;
if (ori[l] == 0) solve(l);
if (ori[r] == 0) solve(r);
}
} else if (op == 'O') { // OR
if (ori[u] == 0) {
solve(l); solve(r);
} else {
if (ori[l] == 1 && ori[r] == 1) return;
if (ori[l] == 1) solve(l);
if (ori[r] == 1) solve(r);
}
} else if (op == 'X') { // XOR
solve(l); solve(r);
} else if (op == 'N') { // NOT
solve(l);
} else { // IN
vis[u] = 1;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%s", a[i].s);
if (a[i].s[0] != 'I' && a[i].s[0] != 'N') scanf("%d%d", &a[i].next[0], &a[i].next[1]);
else scanf("%d", &a[i].next[0]);
}
dfs(1); // 计算原来的取值
solve(1); // 假设根节点的值发生改变
for (int i = 1; i <= n; ++i) if (a[i].s[0] == 'I') {
printf("%d", ori[1] ^ vis[i]);
}
printf("\n");
return 0;
}