P7989 [USACO21DEC] Bracelet Crossings G 题解

Eibon · 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