自动搬运

查看原文

来自洛谷，原作者为

	Eibon 知晓世界的人，也将拥有世界

搬运于2025-08-24 22:34:57，当前版本为作者最后更新于2024-09-11 16:10:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，每个手链必须为连续的。

接下来，我们需要判断两条手链之间是否会相交。

正难则反，由于直接求相交并不好求，所以考虑求出包含和相离的情况。

设 $c1_{i,x}$ 与 $c2_{i,x}$ 表示在第 $i$ 行颜色 $x$ 出现的上端与下端，如果 $c1_{i,x}$ 为 $0$ 则表示该颜色手链在第 $i$ 行为出现。

设 $l_{x}$ 与 $r_{x}$ 表示 $x$ 颜色出现的最左一行与最右一行。

具体步骤请结合代码食用 TWT。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100+5;
const int inf=1e18;
int T=1,n,m;
int l[maxn],r[maxn],c1[maxn][maxn],c2[maxn][maxn];
bool in(int i,int j)
{
	if(!(l[i]<=l[j]&&r[j]<=r[i])){
		return 0;
	}
	for(int x=l[j];x<=r[j];x++){
		if(!(c1[x][i]<c1[x][j]&&c2[x][j]<c2[x][i])){
			return 0;
		}
	}
	return 1;
}
bool ud(int i,int j)
{
	for(int x=1;x<=m;x++){
		int xi=c2[x][i],xj=c1[x][j];
		if(xi&&xj&&xi>xj){
			return 0;
		}
	}
	return 1;
}
bool VIP()
{
	for(int i=1;i<=n;i++){
		if(!l[i]){
			continue;
		}
		for(int j=l[i];j<=r[i];j++){
			if(!c1[j][i]){
				return 0;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(!in(i,j)&&!in(j,i)&&!ud(i,j)&&!ud(j,i)){
				return 0;
			}
		}
	}
	return 1;
}
void solve()
{
	scanf("%lld%lld",&n,&m);
	memset(l,0,sizeof l);memset(r,0,sizeof r);
	memset(c1,0,sizeof c1);memset(c2,0,sizeof c2);
	for(int i=1;i<=m;i++){
		int k;
		scanf("%lld",&k);
		for(int j=1;j<=k;j++){
			int x;
			scanf("%lld",&x);
			if(!c1[i][x]){
				c1[i][x]=j;
			}
			else{
				c2[i][x]=j;
			}
			if(!l[x]){
				l[x]=i;
			}
			else{
				r[x]=i;
			}
		}
	}
	if(VIP()){
		puts("YES");
	}
	else{
		puts("NO");
	}
}
signed main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	scanf("%lld",&T);
	while(T--){
		solve();
	}
	return 0;
}
//dyyyyds