欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-04 10:10:29
...

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

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

 

题意:给你一个门电路(包含XOR、OR、AND、NOT、IN五种),这个门电路构成了一棵树,其中1号是输出端(根),所有的叶子都是输入端,给出每个节点(门)的功能以及输入端的输入(是0还是1),求出在只改变任何一个输入端的情况下,输出端分别输出1还是0

 

只关心AND门和OR门,对于AND门,如果左儿子值为0,那么右子树所有叶子值的改变都不会影响输出,如果右儿子值为0,那么左子树所有叶子值的改变都不会影响输出,对于OR门同理

所以只要1~2遍DFS就可以求出每一个叶子的改变是否对答案产生影响

 

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
typedef struct
{
	int x, y, id;
	char str[15];
}Point;
Point s[1000005];
int ans[1000005], flag[1000005];
int Sech(int u)
{
	int i, p1, p2;
	if(s[u].str[1]=='I')
		return s[u].x;
	if(s[u].str[1]=='N')
		return Sech(s[u].x)^1;
	if(s[u].str[1]=='X')
		return Sech(s[u].x)^Sech(s[u].y);
	if(s[u].str[1]=='A')
	{
		p1 = Sech(s[u].x), p2 = Sech(s[u].y);
		if(p1==0)
			flag[s[u].y] = 1;
		if(p2==0)
			flag[s[u].x] = 1;
		return p1&p2;
	}
	if(s[u].str[1]=='O')
	{
		p1 = Sech(s[u].x), p2 = Sech(s[u].y);
		if(p1==1)
			flag[s[u].y] = 1;
		if(p2==1)
			flag[s[u].x] = 1;
		return p1|p2;
	}
	printf("WA\n");
	return -1;
}
void Sech2(int u)
{
	int i, p1, p2;
	if(flag[u])
		return;
	if(s[u].str[1]=='I')
		ans[s[u].id] = 1;
	if(s[u].str[1]=='N')
		Sech2(s[u].x);
	if(s[u].str[1]=='X' || s[u].str[1]=='A' || s[u].str[1]=='O')
	{
		Sech2(s[u].x);
		Sech2(s[u].y);
	}
}
int main(void)
{
	int n, i, now;
	scanf("%d", &n);
	memset(ans, -1, sizeof(ans));
	for(i=1;i<=n;i++)
	{
		scanf("%s", s[i].str+1);
		if(s[i].str[1]=='I' || s[i].str[1]=='N')
			scanf("%d", &s[i].x);
		else
			scanf("%d%d", &s[i].x, &s[i].y);
		s[i].id = i;
		if(s[i].str[1]=='I')
			ans[i] = 0;
	}
	now = Sech(1);
	Sech2(1);
	for(i=1;i<=n;i++)
	{
		if(ans[i]==-1)
			continue;
		printf("%d", now^ans[i]);
	}
	puts("");
	return 0;
}

 

相关标签: codeforces