题解：CF1010D Mars rover

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

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

然后就做完了。

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

CPP


#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;
		}
	}
}

题解：CF1010D Mars rover

文章操作

相关推荐

评论

题解：CF1010D Mars rover