不就是把正常运算换成xor嘛……
内网oj链接
1.分析
既然每个开关都只有0和1两种情况，那么就可以用状态压缩思想。设数组中每个数的第0位为这个开关的目标状态，第j位为与第j个开关有没有联系（即 $a[i]$ 的第j位为1则有联系）
思路
每个开关的最后状态取决于所有与它有联系的开关的情况和它的初始状态，而开关之间的影响即为做xor运算，由此，可列粗方程组：(x为按下/没按下)
$ \left{ \begin{array}{lr} a_{1,1}x_1 \ xor \ a_{1,2}x_2 \ xor \ a_{1,3}x_3 \cdots a_{1,n}x_n , \ a_{2,1}x_1 \ xor \ a_{2,2}x_2 \ xor \ a_{2,3}x_3 \cdots a_{2,n}x_n , \a_{3,1}x_1 \ xor \ a_{3,2}x_2 \ xor \ a_{3,3}x_3 \cdots a_{3,n}x_n & \end{array} \right. $
2. Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
long long p[10010];
int n, ans = 1; // row 0 dest
int main() {
int T;
cin >> T;
while (T--) {
ans = 1;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i];
}
for (int i = 1; i <= n; i++) {
int stat;
cin >> stat;
p[i] ^= stat;
p[i] += 1 << i;
}
int i1, i2;
while (cin >> i1 >> i2) {
if (i1 == 0 && i2 == 0) break;
p[i2] |= 1 << i1;
}
//------------------------------------------------
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (p[j] > p[i]) swap(p[j], p[i]);
}
if (p[i] == 1) {
ans = 0;
break;
}//1=0
if (p[i] == 0) {
ans = 1 << (n - i + 1);
break;
}
for (int j = n; j; j--) {
if (p[i] >> j & 1) {
for (int k = 1; k <= n; k++) {
if (i != k && (p[k] >> j & 1)) p[k] ^= p[i];
}
break;
}
}
}
if (ans == 0)
cout << "Oh,it's impossible~!!" << endl;
else
cout << ans << endl;
}
return 0;
}
|