简答题
偏难
#7347
开关问题 有N个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,其他的与此开关相关联的开关也会相应地发生变化,即这些相联系的开关的状…
开关问题
有N个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,其他的与此开关相关联的开关也会相应地发生变化,即这些相联系的开关的状态如果原来为开就变为关,如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关,最多只能进行一次开关操作。你的任务是,计算有多少种可以达到指定状态的方法。(不计开关操作的顺序)
时间限制:1000
内存限制:65536
输入
输入第一行有一个数K,表示以下有K组测试数据。 每组测试数据的格式如下: 第一行 一个数N(0 < N < 29) 第二行 N个0或者1的数,表示开始时N个开关状态。 第三行 N个0或者1的数,表示操作结束后N个开关的状态。 接下来 每行两个数I J,表示如果操作第 I 个开关,第J个开关的状态也会变化。每组数据以 0 0 结束。
输出
如果有可行方法,输出总数,否则输出“Oh,it's impossible~!!” 不包括引号
样例输入
2 3 0 0 0 1 1 1 1 2 1 3 2 1 2 3 3 1 3 2 0 0 3 0 0 0 1 0 1 1 2 2 1 0 0
样例输出
4 Oh,it's impossible~!!
提示
第一组数据的说明:一共以下四种方法: 操作开关1 操作开关2 操作开关3 操作开关1、2、3 (不记顺序)
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 35;
bool a[MAXN][MAXN];
inline int read() {
int x;
scanf("%d", &x);
return x;
}
int gauss(int n) {
int rank = 0;
for (int d = 0; d < n; ++d) { /* d for diagonal */
int i;
/* try to find first line whose d'th element = 1 */
for (i = d; i < n; ++i)
if (a[i][d] == 1)
break;
/* not found */
if (i == n)
continue;
/* found */
/* Step 1: make the d'th element of rank'th line to be 1, by swapping i'th
* line and rank'th line, including the rightmost column */
for (int j = 0; j <= n; ++j)
swap(a[rank][j], a[i][j]);
/* Step 2: eliminating the following line if the d'th element = 1, including
* the rightmost column */
for (i = rank + 1; i < n; ++i)
if (a[i][d])
for (int j = 0; j <= n; ++j)
a[i][j] ^= a[rank][j];
++rank;
}
/* up to now, the rank+'th line should be all 0 */
/* if the rightmost column is 1, bad equation, return -1 */
for (int i = rank; i < n; ++i)
if (a[i][n])
return -1;
/* otherwise, return the rank */
return rank;
}
int main() {
int K = read();
for (int k = 0; k < K; ++k) {
memset(a, 0, sizeof(a));
int N = read();
for (int i = 0; i < N; ++i)
a[i][N] ^= read();
for (int i = 0; i < N; ++i)
a[i][N] ^= read();
for (int x = 0; x < N; ++x)
a[x][x] = 1;
for (;;) {
int x = read() - 1, y = read() - 1;
if (x == -1)
break;
a[y][x] = 1;
}
int rank = gauss(N);
if (rank == -1)
printf("Oh,it's impossible~!!\n");
else
printf("%d\n", 1 << (N - rank));
}
system("pause");
return 0;
}</pre>
这道题暂未补解析。