高斯消元几道入门题总结POJ1222&&POJ1681&&POJ1830&&POJ2065&&POJ3185

最近在搞高斯消元，反正这些题要么是我击败了它们，要么就是这些题把我给击败了。现在高斯消元专题部分还有很多题，先把几道很简单的入门题总结一下吧。

专题：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=29538#overview

专题地址来源于kuangbin大神，多谢kuangbin大神总结的高斯消元的模板，菜鸟在此谢过啊。

POJ1222：http://poj.org/problem?id=1222

题意是有5行六列30个开关，然后每拨动一个开关就会影响到其相邻的开关的状态。给了一个初始01的状态，问最终能否所有的值都为1。

一开始对这个高斯消元真的是相当地难以理解，要把这30个开关想象成是30个方程，第i个开关状态对应于第i个方程的右边的值。左边的是所有能够影响到的开关的值。我自己一开始这块真的很难理解，直到跑了几次程序才弄懂。然后就是高斯消元求解。其实高斯消元解方程本身的原理并不难，但就像图论题一样的，难在于建立方程，并且方程本身有各种幺蛾子，比方说我现在面对的POJ1487。。。跑题了。。。

代码：

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

int res[35];
int val[35][35];
int templat[35][35];

void Gauss()
{
	int row, col, i, j, k;

	for (row = 1, col = 1; col <= 30 && row <= 30; col++, row++)
	{
		k = row;
		while (val[k][col] == 0 && k <= 30)
			k++;

		if (k != row)
		{
			for (i = 1; i <= 31; i++)
			{
				swap(val[k][i], val[row][i]);
			}
		}
		for (i = row + 1; i <= 30; i++)
		{
			if (val[i][col])
			{
				for (j = col; j <= 31; j++)
				{
					val[i][j] = val[i][j] ^ val[row][j];
				}
			}
		}
	}

	for (i = 30; i >= 1; i--)
	{
		res[i] = val[i][31];
		for (j = 30; j > i; j--)
		{
			res[i] ^= (val[i][j] && res[j]);
		}
	}
}

int main()
{
	//freopen("i.txt", "r", stdin);
	//freopen("o.txt", "w", stdout);

	int t, test, i, j, k;
	memset(templat, 0, sizeof(templat));

	for (i = 0; i < 5; i++)
	{
		for (j = 1; j <= 6; j++)
		{
			templat[i * 6 + j][i * 6 + j] = 1;
			if (i - 1 >= 0)
			{
				templat[i * 6 + j][(i - 1) * 6 + j] = 1;
			}
			if (i + 1 < 5)
			{
				templat[i * 6 + j][(i + 1) * 6 + j] = 1;
			}
			if (j - 1 >= 1)
			{
				templat[i * 6 + j][i * 6 + j - 1] = 1;
			}
			if (j + 1 <= 6)
			{
				templat[i * 6 + j][i * 6 + j + 1] = 1;
			}
		}
	}

	scanf("%d", &t);
	for (test = 1; test <= t; test++)
	{
		printf("PUZZLE #%d\n", test);
		memcpy(val, templat, sizeof(templat));
		memset(res, 0, sizeof(res));

		for (i = 0; i < 5; i++)
		{
			for (j = 1; j <= 6; j++)
			{
				scanf("%d", &val[i * 6 + j][31]);
			}
		}
		Gauss();

		for (i = 1; i <= 30; i++)
		{
			if (i % 6 == 1)
			{
				printf("%d", res[i]);
			}
			else
			{
				printf(" %d", res[i]);
			}
			if (i % 6 == 0)
			{
				printf("\n");
			}
		}
	}

	//system("pause");
	return 0;
}

POJ1681：http://poj.org/problem?id=1681

和POJ1222一样的题意，理解POJ1222这个题也就好理解了，求出每一个点的值，查1的个数。

代码：

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

int dir[5][2] = {
	{0,0},
	{-1,0},
	{1,0},
	{0,-1},
	{0,1}
};

int n;
int x[300];
char val_c[300][300];
int val[300][300];

int Gauss()
{
	int row, col, i, j, k, ans;

	ans = 0;
	for (row = 1, col = 1; col <= n&&row <= n; col++, row++)
	{
		k = row;
		while (val[k][col] == 0 && k <= n)
			k++;
		if (k>n)
		{
			row--;
			ans++;
			continue;
		}
		if (k != row)
		{
			for (j = 1; j <= n + 1; j++)
			{
				swap(val[k][j], val[row][j]);
			}
		}
		for (i = row + 1; i <= n; i++)
		{
			if (val[i][col])
			{
				for (j = col; j <= n + 1; j++)
				{
					val[i][j] = val[i][j] ^ val[row][j];
				}
			}
		}
	}
	for (i = row; i <= n; i++)
	{
		if (val[i][n + 1])
			return -1;
	}
	for (i = n - ans; i >= 1; i--)
	{
		x[i] = val[i][n + 1];
		for (j = n; j > i; j--)
		{
			x[i] ^= (val[i][j] && x[j]);
		}
	}
	ans = 0;
	for (i = 1; i <= n; i++)
	{
		if (x[i])
			ans++;
	}
	return ans;
}

int main()
{
	//freopen("i.txt", "r", stdin);
	//freopen("o.txt", "w", stdout);

	int a, b, ans;
	int t, i, j, k;

	scanf("%d", &t);

	while (t--)
	{
		scanf("%d", &n);

		memset(val, 0, sizeof(val));
		memset(val_c, 0, sizeof(val_c));
		memset(x, 0, sizeof(x));

		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				for (k = 0; k <= 4; k++)
				{
					a = i + dir[k][0];
					b = j + dir[k][1];
					if (a >= 1 && a <= n&&b >= 1 && b <= n)
					{
						val[(i - 1)*n + j][(a - 1)*n + b] = 1;
					}
				}
			}
		}
		for (i = 1; i <= n; i++)
		{
			cin >> val_c[i] + 1;
			for (j = 1; j <= n; j++)
			{
				if (val_c[i][j] == 'w')
				{
					val[(i - 1)*n + j][n*n + 1] = 1;
				}
			}
		}
		n = n*n;
		ans = Gauss();
		if (ans == -1)
		{
			printf("inf\n");
		}
		else
		{
			printf("%d\n",ans);
		}
	}
	//system("pause");
	return 0;
}

POJ1830：http://poj.org/problem?id=1830

判断多解、无解的情况。另外这个题目一定要注意i、j的顺序，如果j的开关影响到了i，那么应该是在i的方程里面出现j，所以是val[i][j]=1。放到题目当中，两者顺序要调换！！！

代码：

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

int n;
int s[350], e[350], x[350], x2[350];
int res[350][350], res2[350][350];

int Gauss()
{
	int row, col, i, j, k, ans;

	ans = 0;
	for (row = 1, col = 1; col <= n&&row <= n; col++, row++)
	{
		k = row;
		while (res[k][col] == 0 && k <= n)
			k++;
		if (k>n)
		{
			row--;
			ans++;
			continue;
		}
		if (k != row)
		{
			for (j = 1; j <= n + 1; j++)
			{
				swap(res[k][j], res[row][j]);
			}
		}
		for (i = row + 1; i <= n; i++)
		{
			if (res[i][col])
			{
				for (j = col; j <= n + 1; j++)
				{
					res[i][j] = res[i][j] ^ res[row][j];
				}
			}
		}
	}
	for (i = row; i <= n; i++)
	{
		if (res[i][n + 1])
			return -1;
	}
	if (row <= n)
		return (1 << (n - row+1));
	else
		return 1;
}

int main()
{
	//freopen("i.txt", "r", stdin);
	//freopen("o.txt", "w", stdout);

	int k, i, j, ans;
	scanf("%d", &k);

	while (k--)
	{
		scanf("%d", &n);

		memset(res, 0, sizeof(res));
		memset(res2, 0, sizeof(res2));
		memset(x, 0, sizeof(x));
		memset(x2, 0, sizeof(x2));
		memset(e, 0, sizeof(e));
		memset(s, 0, sizeof(s));
		for (i = 1; i <= n; i++)
		{
			scanf("%d", &s[i]);
			res[i][i] = 1;
		}

		for (i = 1; i <= n; i++)
		{
			scanf("%d", &e[i]);
			res[i][n + 1] = s[i] ^ e[i];
		}
		for (;;)
		{
			scanf("%d%d", &i, &j);
			if (i == 0 && j == 0)
				break;
			res[j][i] = 1;
		}
		memcpy(res2, res, sizeof(res));
		ans = Gauss();
		if (ans == -1)
		{
			printf("Oh,it's impossible~!!\n");
		}
		else
		{
			printf("%d\n", ans);
		}
	}
	//system("pause");
	return 0;
}

POJ2065：http://poj.org/problem?id=2065

题意实在是。。。直接理解成来了一个质数p和一个字符串，这个字符串的长度决定了有多少个方程，每个方程的右边的值是相应的字符的值，a对应0，b对应1。。。z对应26，*对应0。

第i个方程左边第j个变量的系数是pow(i,j)mod p，直接求解。

代码：

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

int p;
char res[75];
int x[305];//解集
int val[305][305];//增广矩阵
bool free_x[305];//标记是否是不确定的变元

inline int gcd(int a, int b)
{
	int t;
	while (b != 0)
	{
		t = b;
		b = a%b;
		a = t;
	}
	return a;
}

inline int lcm(int a, int b)
{
	return a / gcd(a, b)*b;//先除后乘防溢出
}

int Gauss(int equ, int var)
{
	int i, j, k;
	int max_r;//当前这列绝对值最大的行
	int col;//当前处理的列
	int ta, tb;
	int LCM;
	int temp;
	int free_x_num;
	int free_index;

	for (int i = 0; i <= var; i++)
	{
		x[i] = 0;
		free_x[i] = true;
	}
	//转换为阶梯阵
	col = 0;//当前处理的列
	for (k = 0; k < equ&&col < var; k++, col++)
	{
		//枚举当前处理的行
		//找到该col列元素绝对值最大的那行与第k行交换.(为了在除法时减少误差)
		max_r = k;
		for (i = k + 1; i < equ; i++)
		{
			if (abs(val[i][col])>abs(val[max_r][col]))
				max_r = i;
		}
		if (max_r != k)
		{//与第k行交换
			for (j = k; j < var + 1; j++)
				swap(val[k][j], val[max_r][j]);
		}
		if (val[k][col] == 0)
		{
			k--;
			continue;
		}
		for (i = k + 1; i < equ; i++)
		{//枚举要删去的行
			if (val[i][col] != 0)
			{
				LCM = lcm(abs(val[i][col]), abs(val[k][col]));
				ta = LCM / abs(val[i][col]);
				tb = LCM / abs(val[k][col]);
				if (val[i][col] * val[k][col] < 0)
					tb = -tb;
				for (j = col; j < var + 1; j++)
				{
					val[i][j] = ((val[i][j] * ta - val[k][j] * tb) % p + p) % p;
				}
			}
		}
	}
	for (i = var - 1; i >= 0; i--)
	{
		temp = val[i][var];
		for (j = i + 1; j < var; j++)
		{
			if (val[i][j] != 0)
			{
				temp = temp - val[i][j] * x[j];
				temp = (temp % p + p) % p;
			}
		}
		while ((temp % val[i][i]))temp += p;
		x[i] = ((temp / val[i][i]) % p + p) % p;
	}
	return 0;
}

int getresult(int A, int n, int k)
{
	int b = 1;
	while (n > 0)
	{
		if (n & 1)
		{
			b = (b*A) % k;
		}
		n = n >> 1;
		A = (A*A) % k;
	}
	return b;
}

int main()
{
	//freopen("i.txt", "r", stdin);
	//freopen("o.txt", "w", stdout);

	int test, i, j, len;
	scanf("%d", &test);

	while (test--)
	{
		memset(val, 0, sizeof(val));

		scanf("%d%s", &p, res);

		len = strlen(res);
		for (i = 0; i < len; i++)
		{
			if (res[i] == '*')
				val[i][len] = 0;
			else
				val[i][len] = res[i] - 'a' + 1;

			for (j = 0; j < len; j++)
				val[i][j] = getresult(i + 1, j, p);
		}
		Gauss(len, len);
		for (i = 0; i < len; i++)
		{
			if (i == 0)
				printf("%d", x[i]);
			else
				printf(" %d", x[i]);
		}
		printf("\n");
	}

	//system("pause");
	return 0;
}

POJ3185：http://poj.org/problem?id=3185

之前的好歹是个二维的，这次的这个是一维的，每个bowl翻过来影响到周围的两个，没有用高斯消元。。。太麻烦了，直接贪心。

代码：

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

int minn;
int val[25];
int val_c[25];

void dfs1(int i, int a[],int num)
{
	if (i == 22)
	{
		minn = min(minn, num);
		return;
	}
	if (a[i - 1] == 1)
	{
		a[i - 1] = (a[i - 1] + 1) & 1;
		a[i] = (a[i] + 1) & 1;
		a[i + 1] = (a[i + 1] + 1) & 1;
		dfs1(i + 1, a, num + 1);

		a[i - 1] = (a[i - 1] + 1) & 1;
		a[i] = (a[i] + 1) & 1;
		a[i + 1] = (a[i + 1] + 1) & 1;
	}
	else
	{
		dfs1(i + 1, a, num);
	}
}

void dfs2(int i, int a[], int num)
{
	if (i == -1)
	{
		minn = min(minn, num);
		return;
	}
	if (a[i + 1] == 1)
	{
		a[i + 1] = (a[i + 1] + 1) & 1;
		a[i] = (a[i] + 1) & 1;
		a[i - 1] = (a[i - 1] + 1) & 1;
		dfs2(i - 1, a, num + 1);
		a[i + 1] = (a[i + 1] + 1) & 1;
		a[i] = (a[i] + 1) & 1;
		a[i - 1] = (a[i - 1] + 1) & 1;
	}
	else
	{
		dfs2(i - 1, a, num);
	}
}

int main()
{
	//freopen("i.txt", "r", stdin);
	//freopen("o.txt", "w", stdout);

	int i;

	memset(val, 0, sizeof(val));
	for (i = 1; i <= 20; i++)
		scanf("%d", val + i);

	minn = 200;
	dfs1(2,val,0);
	dfs2(19, val, 0);
	cout << minn << endl;
	//system("pause");
	return 0;
}