程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 3503 CQOI 2014 和諧矩陣 高斯消元

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

編輯:C++入門知識

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;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved