POJ1830（异或高斯消元）

对于某个开关，都有n个选项可能影响它的结果，如果会影响，则系数为1，否则系数为0；最后得到自由元的个数，自由元可选0也可选1.

#include <cstdio>

#include <algorithm>

int T, n, a[30], x, y;

int gauss() {

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

		//列主

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

			if (a[j] > a[i]) {

				std::swap(a[i], a[j]);

			}

		}

		if (a[i] == 0)	return 1 << (n - i + 1);

		if (a[i] == 1)	return -1;

		//消元

		for (int k = n; k; k--) {

			if (a[i] & (1 << k)) {

				for (int j = 1; j <= n; j++) {

					if (i != j && a[j] & (1 << k)) {

						a[j] ^= a[i];

					}

				}

				break;

			}

		}

	}

	return 1;

}

int main(int argc, char const *argv[]) {

	scanf("%d", &T);

	while (T--) {

		scanf("%d", &n);

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

			scanf("%d", &a[i]);

		}

		for (int i = 1, j; i <= n; i++) {

			scanf("%d", &j);

			a[i] ^= j;//等号右侧

			a[i] |= 1 << i;//a[i][i] = 1

		}

		while (~scanf("%d %d", &x, &y) && (x | y)) {

			a[y] |= 1 << x;//a[y][x] = 1

		}

		int ans = gauss();

		if (ans > 0)	printf("%d\n", ans);

		else	puts("Oh,it's impossible~!!");

	}

	return 0;

}

巴特西

POJ1830（异或高斯消元）

最新文章

热门文章