[SDOI2010] 外星千足虫-526互联

题意

现在你面前摆有 \(1\ldots N\) 编号的 \(N\) 只千足虫，你的任务是鉴定每只虫子所属的星球，但不允许亲自去数它们的足。

Charles 每次会在这 \(N\) 只千足虫中选定若干只放入“昆虫点足机”（the Insect Feet Counter, IFC）中，“点足机”会自动统计出其内所有昆虫足数之和。Charles 会将这个和数 \(\bmod\) \(2\) 的结果反馈给你，同时告诉你一开始放入机器中的是哪几只虫子。

他的这种统计操作总共进行 \(M\) 次，而你应当尽早得出鉴定结果。

假如在第 \(K\) 次统计结束后，现有数据就足以确定每只虫子的身份，你就还应将这个 \(K\) 反馈给 Charles，此时若 \(K<M\)，则表明那后 \(M-K\) 次统计并非必须的。

如果根据所有 \(M\) 次统计数据还是无法确定每只虫子身份，你也要跟 Charles 讲明：就目前数据会存在多个解。

\(1\leq N\leq 10^3\)，\(1\leq M\leq 2\times 10^3\)

Solution

本题要求求解

\[\begin{cases} a_1 x_1 \ \text{xor} \ a_2 x_2 \dots \text{xor} \ a_n x_n = a_{n+1} \\ b_1 x_1 \ \text{xor} \ b_2 x_2 \dots \text{xor} \ b_n x_n = b_{n+1} \\ \dots \\ c_1 x_1 \ \text{xor} \ c_2 x_2 \dots \text{xor} \ c_n x_n = c_{n+1} \\ \end{cases}\]

显然这是一个类似于高斯消元的方程组，可以考虑使用高斯消元解决，只不过由原来的加减消元转化为异或消元即可。

对于无解判断，跟原高斯消元一致，只需要判断是否存在新的 \(x_i\) 来进行消元。

而考虑到需要多少组统计数据，我们发现在高斯消元的时候会尽量的选择可供消元的 \(n\) 的方程，只需要记录下这些方程原来是第几组，然后统计最大值即可。

不幸的是，我们发现整个过程为 \(O(n^3)\) ，我们的算法不能通过。

考虑使用 bitset ，其具有更加优秀的异或时间复杂度，或者是比较原始的说，用二进制数来表示出这些01位，然后对这些二进制进行异或运算，可以有效降低时间复杂度。

幸运的是，这个题的数据很水，我们不需要 bitset 也可以通过。

Code

点击查看代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e3 + 50;

inline int read() {
	register int w = 0, f = 1;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-')  f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		w = w * 10 + c - '0';
		c = getchar();
	}
	return w * f;
}

int n, m;
int a[N << 1][N];

int main() {
	n = read(), m = read();
	for (register int i = 1; i <= m; ++i) {
		for (register int j = 1; j <= n; ++j)
			scanf("%1d", &a[i][j]);
		scanf("%d", &a[i][n + 1]);
		a[i][0] = i;
	}

	for (register int i = 1; i <= n; ++i) {
		register bool flag = false;
		for (register int j = i; j <= m; ++j)
			if (a[j][i]) {
				swap(a[i], a[j]);
				flag = true;
				break;
			}	
		if (!flag) {
			puts("Cannot Determine");
			return 0;
		}
		for (register int j = i + 1; j <= m; ++j)
			if (a[j][i])
				for (register int k = i; k <= n + 1; ++k)
					a[j][k] ^= a[i][k];
	}

	for (register int i = n ; i >= 1; --i)
		for (register int j = i - 1; j >= 1; --j)
			if (a[j][i])
				for (register int k = i; k <= n + 1; ++k)
					a[j][k] ^= a[i][k];
			
	register int ans = a[1][0];
	for (register int i = 2; i <= n; ++i)
		ans = max(ans, a[i][0]);
	
	printf("%d\n", ans);
	for (register int i = 1; i <= n; ++i)
		puts(a[i][n + 1] == 0 ? "Earth" : "?y7M#");
	return 0;
}