ARC199A Flip Row or Col 2 做题记录

给定一个 $n\times n$ 的 01 矩阵 $A$，和两个长 $n$ 的非负整数数组 $ca,cb$。请构造两个长 $n$ 的 01 数组 $fa,fb$，满足：

• $\forall i\in [1,n]$ 都有 $ca_i=\sum\limits_{1\le j\le n} A_{i,j}\oplus fa_i\oplus fb_j$；
• $\forall j\in [1,n]$ 都有 $cb_j=\sum\limits_{1\le i\le n} A_{i,j}\oplus fa_i\oplus fb_j$；

$1\le n\le 1000$，$0\le ca_i,cb_i<\frac{n}{4}$。

怎么这么笨。

关键步骤：先通过列翻转将第一行变成 $0$。

不难发现，将 $fa$ 和 $fb$ 全部取反不影响合法性，所以可以钦定 $fa_1=0$。接下来由于 $ca_1<\frac{n}{4}$，所以列翻转次数（$\sum\limits_i fb_i$）也 $<\frac{n}{4}$。

那么对于一行 $i$，若此时 $\frac{n}{2}\le \sum\limits_{j}A_{i,j}$ 则一定有 $fa_i=1$，否则一定有 $fa_i=0$。

故 $fa$ 就确定了，那么 $fb$ 也可以直接确定了。

再判一下合法性即可。

时间复杂度 $O(n^2)$，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=1005;

int n;
char a[S][S];
int cnta[S],cntb[S];
int ra[S],rb[S];

inline void slove()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		for(int j=n;j>=1;j--) a[i][j]=a[i][j-1]-'0';
	}
	for(int i=1;i<=n;i++) cin>>cntb[i];
	for(int i=1;i<=n;i++) cin>>cnta[i];
	for(int i=1;i<=n;i++)
	{
		ra[i]=a[1][i];
		for(int j=1;j<=n;j++) a[j][i]^=ra[i];
	}
	for(int i=1;i<=n;i++)
	{
		int cnt=0;
		for(int j=1;j<=n;j++) cnt+=a[i][j];
		rb[i]=cnt>=(n+1)/2;
		for(int j=1;j<=n;j++) a[i][j]^=rb[i];
	}
	for(int i=1;i<=n;i++)
	{
		int cnt=0;
		for(int j=1;j<=n;j++) cnt+=a[j][i];
		bool fl=cnt!=cnta[i];
		ra[i]^=fl;
		for(int j=1;j<=n;j++) a[j][i]^=fl;
	}
	bool fl=true;
	for(int i=1;i<=n;i++)
	{
		int cnt=0;
		for(int j=1;j<=n;j++) cnt+=a[j][i];
		fl&=cnt==cnta[i];
		cnt=0;
		for(int j=1;j<=n;j++) cnt+=a[i][j];
		fl&=cnt==cntb[i];
	}
	if(!fl) cout<<"No\n";
	else
	{
		cout<<"Yes\n";
		for(int i=1;i<=n;i++) cout<<rb[i];cout<<'\n';
		for(int i=1;i<=n;i++) cout<<ra[i];cout<<'\n';
	}
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T-->0) slove();
	return 0;
}