装压暴力求 SG 不知道为啥 30pts,玄关求条
查看原帖
装压暴力求 SG 不知道为啥 30pts,玄关求条
525375
Richard_Whr楼主2024/7/9 14:54
#include<bits/stdc++.h>
using namespace std;
const int N=21;
int f[1<<N];
int st[1<<N];
int ne[N];
int n,m;
int T;

int sg(int s)
{
	int v=f[s];
	if(~v) return v;
	int res=0;
	if((s>>(m-1))&1) ne[m-1]=m;
	else ne[m-1]=m-1;
	for(int i=m-2;i>=0;i--)
	{
		if((s>>i)&1) ne[i]=ne[i+1];
		else ne[i]=i;
	}
	for(int i=0;i<m;i++)
	{
		if((s>>i)&1) 
		{
			if(ne[i]>=m) continue;
			int t=s^(1<<i)^(1<<ne[i]);
			st[sg(t)]=s; 
		}
	}
	while(st[res]==s) res++;
	return f[s]=res;
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	
	cin>>T;
	memset(f,-1,sizeof f);
	m=20;
	for(int s=0;s<(1<<m);s++) sg(s);
	
	while(T--)
	{
		cin>>n;
		int res=0;
		for(int i=1,k,j;i<=n;i++)
		{
			cin>>k;
			int s=0;
			while(k--) cin>>j,j--,s|=(1<<j);
			res^=sg(s);
		}
		if(res) cout<<"YES\n";
		else cout<<"NO\n";
	}
	
	return 0;
}
2024/7/9 14:54
加载中...