CodeForces 1011F Mars rover 【模拟】【DFS】

发表于 | 更新于 | 分类于

题目大意：

给出一颗根结点为1的树，每个结点最多有两个叶子结点，每个结点的值非0即1。
现在给出部分结点的值(0或1)，剩余结点告诉你它们值和子结点值的关系(AND、OR、XOR、NOT)。
现在要你求的内容是按照输入顺序依次改变初始时给出的结点的值(0变为1，1变为0)，问每次改变后的根结点的值是多少。

解题思路：

首先根据给出的关系我们可以求出每个结点初始状态的值，后面怎么做呢？我们可以挨个枚举每个点变化后的情况如果枚举变化情况的话TLE无疑。
观察最后的值发现，答案非0即1，每个结点的值都是这样。那么我们可以不用模拟整个过程，而是记录到某个结点时它的值是否改变了，举个例子的话就是当这个结点是由前面两个结点AND得来的，正好有个结点是0，此时1所在结点的那个分支不论怎么变到这个位置出结果都是0。根据这个思想，我们再对这棵树进行一次DFS做下标记就可以了。

Mycode：

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int MAX = 1e6+5;

int n, m;
char s[4];
struct node
{
    char op;
    vector<int> in;
    bool val, flag;
}G[MAX];

bool GetVal(int rt)
{
    char c = G[rt].op;
    if(c == 'A')
        G[rt].val = GetVal(G[rt].in[0]) & GetVal(G[rt].in[1]);
    else if(c == 'X')
        G[rt].val = GetVal(G[rt].in[0]) ^ GetVal(G[rt].in[1]);
    else if(c == 'O')
        G[rt].val = GetVal(G[rt].in[0]) | GetVal(G[rt].in[1]);
    else if(c == 'N')
        G[rt].val = !GetVal(G[rt].in[0]);
    return G[rt].val;
}

void GetFlag(int rt)
{
    if(G[rt].flag == false)
        for(int i = 0; i < G[rt].in.size(); ++i)
            G[G[rt].in[i]].flag = false;
    else
    {
        char c = G[rt].op;
        if(c == 'A')
        {
            if(G[rt].val == (!G[G[rt].in[0]].val & G[G[rt].in[1]].val))
                G[G[rt].in[0]].flag = false;
            else
                G[G[rt].in[0]].flag = true;
            if(G[rt].val == (!G[G[rt].in[1]].val & G[G[rt].in[0]].val))
                G[G[rt].in[1]].flag = false;
            else
                G[G[rt].in[1]].flag = true;
        }
        else if(c == 'O')
        {
            if(G[rt].val == (!G[G[rt].in[0]].val | G[G[rt].in[1]].val))
                G[G[rt].in[0]].flag = false;
            else
                G[G[rt].in[0]].flag = true;
            if(G[rt].val == (!G[G[rt].in[1]].val | G[G[rt].in[0]].val))
                G[G[rt].in[1]].flag = false;
            else
                G[G[rt].in[1]].flag = true;
        }
        else if(c == 'X')
        {
            if(G[rt].val == (!G[G[rt].in[0]].val ^ G[G[rt].in[1]].val))
                G[G[rt].in[0]].flag = false;
            else
                G[G[rt].in[0]].flag = true;
            if(G[rt].val == (!G[G[rt].in[1]].val ^ G[G[rt].in[0]].val))
                G[G[rt].in[1]].flag = false;
            else
                G[G[rt].in[1]].flag = true;
        }
        else if(c == 'N')
        {
            if(G[rt].val == (!!G[G[rt].in[0]].val))
                G[G[rt].in[0]].flag = false;
            else
                G[G[rt].in[0]].flag = true;
        }
    }
    for(int i = 0; i < G[rt].in.size(); ++i)
        GetFlag(G[rt].in[i]);
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%s", s);
        G[i].op = s[0];
        scanf("%d", &m);
        if(s[0] == 'I')
            G[i].val = m;
        else
        {
            G[i].in.push_back(m);
            if(s[0] != 'N')
            {
                scanf("%d", &m);
                G[i].in.push_back(m);
            }
        }
    }

    GetVal(1);

    /*for(int i = 1; i <= n; ++i)
        if(G[i].val)    cout << i << " ";
    cout << endl;*/

    G[1].flag = true;
    GetFlag(1);

    /*for(int i = 1; i <= n; ++i)
        if(G[i].flag)   cout << i << " ";
    cout << endl;*/

    for(int i = 1; i <= n; ++i)
        if(G[i].op == 'I')
            printf("%d", G[1].val ^ G[i].flag);
    return 0;
}
Donate comment here
0%