题解：CF1010D Mars rover

TimelessWelkin · 2025-08-27 14:32:00 · 题解

在这里分享一种不太一样的做法。

我们可以先 dfs 一遍求出每个节点原来的值（yuan），然后再从头开始再 dfs 一遍求出如果这个点值变为 0 或变为 1 时根节点答案会是什么（_0 和 _1）。

然后就做完了。

解释一下代码： 在 node 中，op 的含义不必多说，其中 _0 和 _1 分别表示如果该节点是 0 或者 1 时根节点的值。 代码的算法适用于只修改一个点且仅查询根节点权值时。

#include<bits/stdc++.h>
using namespace std;
struct node{
    int op;//1--IN 2--AND 3--OR 4--XOR 5--NOT
    int za,zb;
    int z,dep,fa;
    int another;
    int _1,_0;
    int yuan;
}a[1000005];
int isroot[1000005];
int ROOT;
void dfs(int root,int fa){ //第一遍dfs求出原值(.yuan)
    a[root].dep=a[fa].dep+1;
    a[root].fa=fa;
    if(a[root].op==1||a[root].op==5){
        if(a[root].op==5)dfs(a[root].z,root);

        if(a[root].op==1)a[root].yuan=a[root].z;
        else a[root].yuan=1-a[a[root].z].yuan;
    }
    else {
        dfs(a[root].za,root);
        dfs(a[root].zb,root);
        if(a[root].op==2)a[root].yuan=a[a[root].zb].yuan & a[a[root].za].yuan;
        if(a[root].op==3)a[root].yuan=a[a[root].zb].yuan | a[a[root].za].yuan;
        if(a[root].op==4)a[root].yuan=a[a[root].zb].yuan ^ a[a[root].za].yuan; 
    }
}
inline int calc(int op,int za,int zb){
    if(op==5)return 1-za;
    if(op==2)return za&zb;
    if(op==3)return za|zb;
    if(op==4)return za^zb;
}
void dfs2(int root){//._0表示如果这个点值为0根节点的答案，_1亦然

    if(root==ROOT)a[root]._1=1,a[root]._0=0;
    else {
        int t=a[root].op;
        if(calc(a[a[root].fa].op,1,a[a[root].another].yuan)==1)a[root]._1=a[a[root].fa]._1;
        else a[root]._1=a[a[root].fa]._0;

        if(calc(a[a[root].fa].op,0,a[a[root].another].yuan)==1)a[root]._0=a[a[root].fa]._1;
        else a[root]._0=a[a[root].fa]._0;       
    }
    if(a[root].op==1||a[root].op==5){
        if(a[root].op==5)dfs2(a[root].z);
    }
    else {
        dfs2(a[root].za);
        dfs2(a[root].zb);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        string op;
        cin>>op;
        if(op=="IN"){
            a[i].op=1;
            int t;
            cin>>t;a[i].z=t;
        }
        else if(op=="NOT"){
            a[i].op=5;
            int t;
            cin>>t;a[i].z=t;
            isroot[t]=1;
        }
        else {
            if(op=="AND")a[i].op=2;
            if(op=="OR")a[i].op=3;
            if(op=="XOR")a[i].op=4;
            int X,Y;
            cin>>X>>Y;
            a[i].za=X;a[i].zb=Y;
            a[X].another=Y;a[Y].another=X; 
            isroot[Y]=1,isroot[X]=1;
        }
    }
    if(n==1){
        int x=1-a[1].z;
        cout<<x<<'\n';
        return 0;
    }
    for(int i=1;i<=n;i++)if(isroot[i]==0)ROOT=i;
    dfs(ROOT,0);
    dfs2(ROOT);
    for(int i=1;i<=n;i++){
        if(a[i].op==1){
            if(a[i].z==1)cout<<a[i]._0;
            else cout<<a[i]._1;
        }
    }
}