CSA Lignts Out

算是热身题吧

如果是每次操作一行或一列,那么无论怎么操作,本质不同的行最多只有两种,本质不同的列也最多只有两种,那么只要把某一种行和某一种列全部翻转使得全为0即可

现在是同时操作一行一列,显然操作一行或一列偶数次等于没操作,所以对于要操作的行如果操作完了,但是还要操作,那么后面只用操作同一行,列的情况类似.这就等价于操作的行列数目的奇偶性要相同,枚举不同情况即可

#include<bits/stdc++.h>

#define LL long long

#define uLL unsigned long long

#define db double

using namespace std;

const int N=500+10;

int rd()

{

    int x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

uLL pw[N],bs=233,aa[N],bb[N];

int n,m,lm,nm,a[N][N],smx,smy,s1[N],t1,s2[N],t2,mx=N*2;

vector<int> a1,a2;

bool sx[N],sy[N],fx,fy;

void wk()

{

    t1=t2=0;

    int co=a[1][1]^(sx[1]^fx)^(sy[1]^fy);

    if(co) return;

    for(int i=1;i<=n;++i)

	if(sx[i]^fx) s1[++t1]=i;

    for(int j=1;j<=m;++j)

	if(sy[j]^fy) s2[++t2]=j;

    if(mx>max(t1,t2))

    {

    	mx=max(t1,t2);

    	a1.clear();

    	for(int i=1;i<=t1;++i) a1.push_back(s1[i]);

    	a2.clear();

    	for(int i=1;i<=t2;++i) a2.push_back(s2[i]);

    }

}

int main()

{

    n=rd(),m=rd();

    for(int i=1;i<=n;++i)

	for(int j=1;j<=m;++j)

	    a[i][j]=rd();

    lm=max(n,m);

    pw[0]=1;

    for(int i=1;i<=lm;++i) pw[i]=pw[i-1]*bs;

    for(int i=1;i<=n;++i)

    {

    	for(int j=1;j<=m;++j) aa[i]+=pw[j]*a[i][j];

    	bb[i]=aa[i];

    }

    sort(bb+1,bb+n+1);

    nm=unique(bb+1,bb+n+1)-bb-1;

    if(nm>2) {puts("-1");return 0;}

    for(int i=1;i<=n;++i) smx+=sx[i]=aa[i]==bb[1];

    for(int j=1;j<=m;++j)

    {

    	aa[j]=0;

    	for(int i=1;i<=n;++i) aa[j]+=pw[i]*a[i][j];

    	bb[j]=aa[j];

    }

    sort(bb+1,bb+m+1);

    nm=unique(bb+1,bb+m+1)-bb-1;

    if(nm>2) {puts("-1");return 0;}

    for(int j=1;j<=m;++j) smy+=sy[j]=aa[j]==bb[1];

    if(!((smx^smy)&1)) wk();

    fx^=1,smx=n-smx;

    if(!((smx^smy)&1)) wk();

    fx^=1,smx=n-smx;

    fy^=1,smy=m-smy;

    if(!((smx^smy)&1)) wk();

    fx^=1,smx=n-smx;

    if(!((smx^smy)&1)) wk();

    if(mx<=lm)

    {

    	printf("%d\n",mx);

    	while(mx--)

    	{

    	    if(!a1.empty()) printf("%d ",a1.back()),a1.pop_back();

    	    else printf("1 ");

    	    if(!a2.empty()) printf("%d\n",a2.back()),a2.pop_back();

    	    else printf("1\n");

    	}

    }

    else puts("-1");

    return 0;

}

巴特西

CSA Lignts Out

最新文章

热门文章