BZOJ 3503 CQOI 2014 和諧矩陣 高斯消元

BZOJ 3503 CQOI 2014 和諧矩陣 高斯消元

題目大意：給出m和n，求出一種方案使得每一個點和周圍的四個點的1的個數為偶數。

思路：根據題意可以列出m*n個異或方程，然後組成異或方程組。解這個異或方程組然後輸出任意一個解就可以了。

PS：值得注意的是，全是0肯定是一個解，顯然你不能輸出這個解。所以你需要讓一個或一些自由元的值為1，至於怎麼做，隨便yy就行了。

PS2：這個題的樣例吞掉了空格，然而又是SPJ，所以就是wa。。然後我wa了一下午。。

CODE：

#include 
#include 
#include 
#include 
#define MAX 50
using namespace std;
const int dx[] = {0,1,-1,0,0};
const int dy[] = {0,0,0,1,-1};

int num[MAX][MAX];

int arr[MAX * MAX][MAX * MAX],solves;
bool ans[MAX];
int represent[MAX];

void Gauss()
{
	int cnt = m * n,now = 1;
	for(int i = 1; i <= cnt; ++i) {
		for(int j = now + 1; j <= cnt; ++j)
			if(arr[j][i] > arr[now][i])
				for(int k = 1; k <= cnt; ++k)
					swap(arr[now][k],arr[j][k]);
		if(!arr[now][i]) {
			ans[i] = 1;
			for(int j = 1; j <= cnt; ++j)
				if(arr[j][i])
					arr[i][j] = 0,ans[i][cnt + 1] ^= 1;
			continue;
		}
		for(int j = now + 1; j <= cnt; ++j)
			if(arr[j][i])
				for(int k = i; k <= cnt; ++k)
					arr[j][k] ^= arr[now][k];
		represent[now] = i;
		++now;
	}
	for(int i = now; i; --i) {
		int solve = represent[i];
		for(int j = 1; j <= now - 1; ++j)
			if(arr[j][solve])
				arr[j][solve] = 0,arr[j][cnt + 1] ^= arr[i][cnt + 1];
		ans[solve] = arr[i][cnt + 1];
	}
}

int main()
{
	cin >> m >> n;
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			num[i][j] = ++cnt;
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			for(int k = 0; k <= 4; ++k) {
				int fx = i + dx[k],fy = j + dy[k];
				if(!fx || !fy || fx > m || fy > n)	continue;
				arr[num[i][j]][num[fx][fy]] = 1;
			}
	Gauss();
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j) 
			printf("%d",ans[num[i][j]]);
		puts("");
	}
	return 0;
}