高斯消元球调(悬赏2关注)
查看原帖
高斯消元球调(悬赏2关注)
569235
w9095楼主2024/3/10 11:07

WA on #17

#include <bits/stdc++.h>
using namespace std;
long long n,k,now[2100],y[2100],a[2100][2100],b[2100],ans[2100],sa[2100],sb[2100],cnt=0;
string op;
void ry()
{
	long long m=0,now=0;
	cin>>m;
	for(int i=1;i<=m;i++)
	    {
	    cin>>now;
	    swap(sa[now],sb[now]);
	    }
}

void rb()
{
	long long m=0,now=0;
	cin>>m;
	for(int i=1;i<=m;i++)
		{
		cin>>now;
		sb[now]=sa[now]^sb[now];
	    }
}

void yb()
{
	long long m=0,now=0;
	cin>>m;
	for(int i=1;i<=m;i++)
	    {
	    cin>>now;
	    sa[now]=sa[now]^sb[now];
	    }
}

void mix()
{
	long long m=0,id=0;
	char col=0;
	cin>>m;
	for(int i=1;i<=m;i++)cin>>now[i];
	cin>>col;
	if(col=='W')id=0;
	if(col=='R')id=1;
	if(col=='Y')id=2;
	if(col=='B')id=3;
	cnt++,b[cnt]=id&1;
	for(int i=1;i<=m;i++)
	    {
	    if(sa[now[i]]&1)a[cnt][now[i]]=1;
	    if(sa[now[i]]&2)a[cnt][now[i]+n]=1;
	    }
	cnt++,b[cnt]=(id>>1)&1;
	for(int i=1;i<=m;i++)
	    {
	    if(sb[now[i]]&1)a[cnt][now[i]]=1;
	    if(sb[now[i]]&2)a[cnt][now[i]+n]=1;
	    }
}

bool gauss()
{
	long long now=1,res=0;
    for(int i=1;i<=n*2;i++)
        {
        long long mx=now;
        for(int j=now;j<=n*2;j++)
            if(a[j][i]!=0)
               {
			   mx=j,res=max(res,mx);
			   break;
		       }
        if(a[mx][i]==0)continue;
        if(now!=mx)
           {
           for(int j=1;j<=n*2;j++)swap(a[now][j],a[mx][j]);
           swap(b[now],b[mx]);
           }
        for(int j=now+1;j<=n*2;j++)
            if(a[j][i]==1)
	            {
	                b[j]^=b[now];
	                for(int k=i;k<=n*2;k++)a[j][k]^=a[now][k];
	            }
	    y[now]=i;
	    now++;
		}
	for(int i=now;i<=n*2;i++)
	    if(b[i])return 0;
    return 1;
}

void print(long long p)
{
	if(ans[p]==0&&ans[p+n]==0)printf(".");
	if(ans[p]==1&&ans[p+n]==0)printf("R");
	if(ans[p]==0&&ans[p+n]==1)printf("Y");
	if(ans[p]==1&&ans[p+n]==1)printf("B");
}

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)sa[i]=1,sb[i]=2;
    for(int i=1;i<=k;i++)
        {
        	cin>>op;
        	if(op=="RY")ry();
        	else if(op=="RB")rb();
        	else if(op=="YB")yb();
        	else if(op=="mix")mix();
		}
	if(!gauss())printf("NO\n");
	else
	   {
	   	printf("YES\n");
	   	ans[y[n*2]]=b[n*2];
	   	for(int i=n*2-1;i>=1;i--)
	        {
	        ans[y[i]]=b[i];
	        for(int j=n*2;j>y[i];j--)
			    if(a[i][j])ans[y[i]]^=ans[j];
	        }
	    for(int i=1;i<=n;i++)print(i);
	    printf("\n");
	   }
	return 0;
}
2024/3/10 11:07
加载中...