F. Mars rover

题目链接

Codeforces Round #499 (Div. 2)--F. Mars rover

题解

高档题。题意大概是给定一个图,每个节点可能包含 AND (2 inputs), OR (2
inputs), XOR (2 inputs), NOT (1 input) 四种情况,除此之外还有 IN 节点作为输入。所有输入经过一系列逻辑运算后将得到一个输出。现给定这些输入,求改变每个输入节点后输出节点的值。

首先从将每个节点对初始输入的值所表达的值求出来。
之后将输出标记为重要,并从输出节点开始对每个节点标记,标记规则如下:

  • 如果该节点为不重要,则它的输入节点均为不重要
  • 如果该节点为重要,若改变某一输入节点的值该节点的值改变,则这一输入节点为重要,否则这一输入节点为不重要。

最后判断每个输入节点是否为重要节点,如果是则输出输出节点原本的值的否,如果不是则输出输出节点原本的值。

一定要注意逻辑运算符的优先级,我被这个坑了几十分钟。

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int n, k, q1;
struct MyStruct
{
    bool self, isimportant;
    int in1, in2;
    int type;//and=0,or=1,xor=2,not=3,in=4
} a[1000005];
char s[5];
vector<int>inputs;

void pd(int i) {
    if (a[i].type == 4)return;
    if (a[i].isimportant == false) {
        a[a[i].in1].isimportant = false;
        pd(a[i].in1);
        if (a[i].type != 3) {
            a[a[i].in2].isimportant = false;
            pd(a[i].in2);
        }
    }
    else {
        if (a[i].type == 0) {
            if (((!a[a[i].in1].self)&(a[a[i].in2].self)) != a[i].self) {
                a[a[i].in1].isimportant = true;
                pd(a[i].in1);
            }
            else {
                a[a[i].in1].isimportant = false;
                pd(a[i].in1);
            }
            if (((!a[a[i].in2].self)&(a[a[i].in1].self)) != a[i].self) {
                a[a[i].in2].isimportant = true;
                pd(a[i].in2);
            }
            else {
                a[a[i].in2].isimportant = false;
                pd(a[i].in2);
            }
        }
        else if (a[i].type == 1) {
            if (((!a[a[i].in1].self) | (a[a[i].in2].self)) != a[i].self) {
                a[a[i].in1].isimportant = true;
                pd(a[i].in1);
            }
            else {
                a[a[i].in1].isimportant = false;
                pd(a[i].in1);
            }
            if (((!a[a[i].in2].self) | (a[a[i].in1].self)) != a[i].self) {
                a[a[i].in2].isimportant = true;
                pd(a[i].in2);
            }
            else {
                a[a[i].in2].isimportant = false;
                pd(a[i].in2);
            }
        }
        else if (a[i].type == 2) {
            if (((!a[a[i].in1].self) xor (a[a[i].in2].self)) != a[i].self) {
                a[a[i].in1].isimportant = true;
                pd(a[i].in1);
            }
            else {
                a[a[i].in1].isimportant = false;
                pd(a[i].in1);
            }
            if (((!a[a[i].in2].self) xor (a[a[i].in1].self)) != a[i].self) {
                a[a[i].in2].isimportant = true;
                pd(a[i].in2);
            }
            else {
                a[a[i].in2].isimportant = false;
                pd(a[i].in2);
            }
        }
        else if (a[i].type == 3) {
            a[a[i].in1].isimportant = true;
            pd(a[i].in1);
        }
    }
}



bool fill(int i) {
    switch (a[i].type) {
    case 4:
        return a[i].self;
    case 0:
        a[i].self = fill(a[i].in1) & fill(a[i].in2);
        return a[i].self;
    case 1:
        a[i].self = fill(a[i].in1) | fill(a[i].in2);
        return a[i].self;
    case 2:
        a[i].self = fill(a[i].in1) xor fill(a[i].in2);
        return a[i].self;
    case 3:
        a[i].self = !fill(a[i].in1);
        return a[i].self;
    }
}

int main() {
    memset(a, 0, sizeof(a));
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%s", &s);
        if (s[0] == 'A') {
            a[i].type = 0;
            scanf("%d %d", &a[i].in1, &a[i].in2);
        }
        else if (s[0] == 'O') {
            a[i].type = 1;
            scanf("%d %d", &a[i].in1, &a[i].in2);
        }
        else if (s[0] == 'X') {
            a[i].type = 2;
            scanf("%d %d", &a[i].in1, &a[i].in2);
        }
        else if (s[0] == 'N') {
            a[i].type = 3;
            scanf("%d", &a[i].in1);
        }
        else if (s[0] == 'I') {
            a[i].type = 4;
            scanf("%d", &a[i].in1);
            a[i].self = a[i].in1;
            inputs.push_back(i);
        }
    }

    fill(1);
    a[1].isimportant = true;
    pd(1);

    for (auto i : inputs) {
        if (a[i].isimportant) printf("%d", !a[1].self);
        else printf("%d", a[1].self);
    }
}

标签: implementation, dfs and similar, graphs

添加新评论