当前位置: 首页 > 工具软件 > Mars Rover > 使用案例 >

「Codeforces 1010D」Mars rover - dfs

蔺敏达
2023-12-01

建议访问原文出处,获得更佳浏览体验。
原文出处:https://hyp1231.github.io/2018/07/28/20180728-cf1010d/

题意

给出一个以 1 1 为根的有 n 个节点的树,树的每个节点表示一个输入,或者一个逻辑关系。每个逻辑关系根据儿子节点的值,套入逻辑关系式,计算出当前节点的值。
现在让你求出,只改变任一个输入节点的值,根节点的取值。

链接

Codeforces 1010D

题解

首先我们可以规定一个结构体 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 1)。

我们可以一次 dfs d f s 求出每个节点的值,把它们记录在 ori[N] 数组中。

下面考虑怎么计算改变单一输入后根节点的值。

当一个输入改变时,它可以导致一系列节点的取值发生改变。而我们可以从根节点逆推,假设根节点的值改变了,考虑需要的条件。
先只考虑某个单一节点 u u 假设 u 的值改变了,分下面几种情况讨论:

  1. u u AND
    如果节点 u u 原来的取值是 1,说明两个儿子节点都是 1 1 。根据假设,节点 u 的值改变了,那么势必是因为两个儿子之一的值改变了。因此递归搜索两个儿子。(假设某个儿子的值改变了)
    如果节点 u u 原来的取值是 0,那么说明两个儿子节点至少有一个是 0 0 。根据假设,节点 u 的值改变了,如果两个儿子节点都是 0 0 ,这个搜索分支结束(因为只改变一个输入无法使两个儿子节点的值全部改变);否则只有一个儿子节点是 0,递归搜索原来取值为 0 0 的那个儿子。

  2. u OR O R
    和第一种情况同理,只需要根据逻辑表达式稍作修改。

  3. u u XOR
    说明两个儿子节点一个是 1 1 ,另一个是 0。根据假设,节点 u u 的值改变了,那么势必因为两个儿子之一的值改变了。递归搜索两个儿子。

  4. u NOT N O T
    儿子的值改变了,递归搜索儿子节点。

  5. u u IN
    输入改变了,记录这个 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;
}
 类似资料: