【做题笔记】CF776D The Door Problem

Problem

CF776D The Door Problem

题目大意:

有 \(n\) 扇门和 \(m\) 把钥匙,初始时有些门开着,有些门关着。一把钥匙对应多个门,每个门对应恰好两把钥匙。使用一把钥匙会使该钥匙对应的所有门的状态改变(开变成关,关变成开),问是否有存在一种钥匙的使用方案使得所有门都被打开。

Solution

我们将初始时开着的和关着的门分开讨论。

对于开着的门,两把钥匙要么都用,要么都不用。
对于关着的门,两把钥匙必须使用恰好一把。

也就是说,对于开着的门,两把钥匙的使用情况相同。
对于关着的门,两把钥匙的使用情况不同。

于是我们可以想到扩展域并查集。对于第 \(i\) 扇门,若他对应的钥匙是 \(k_1\) 和 \(k_2\),若他是开着的,则合并 \((k_1,k_2),(k_1+n,k_2+n)\),若他是关着的,则合并 \((k_1,k_2+n),(k_1+n,k_2)\)。

若最终出现一把钥匙 \(j\),\(j\) 和 \(j+n\) 被并在一起,说明 \(j\) 既要被使用,又要不被使用,显然是不合法的。否则就是合法的。

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,lck[100005],key[100005];
struct bin
{
	int f[200005];
	bin(){for(int i=1;i<=200000;i++) f[i]=i;}
	int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
	void merge(int x,int y){f[find(x)]=find(y);return;}
	int query(int x,int y){return find(x)==find(y);}
}b;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&lck[i]);
	for(int i=1;i<=m;i++)
	{
		int k;
		scanf("%d",&k);
		for(int j=1;j<=k;j++)
		{
			int x;
			scanf("%d",&x);
			if(key[x]!=0)
			{
				if(lck[x]==0) b.merge(key[x],i+m),b.merge(key[x]+m,i);
				else b.merge(key[x],i),b.merge(key[x]+m,i+m);
			}
			else key[x]=i;
		}
	}
	for(int i=1;i<=m;i++)
		if(b.query(i,i+m)){puts("NO");return 0;}
	puts("YES");
	return 0;
}
上一篇:An easy problem


下一篇:647. Palindromic Substrings