推蒟蒻 $\color{salmon}{blog}$ ！
原题链接~
有趣的高斯消元解异或方程组题，难点在建模。
这里默认读者都会高消（（（
题意稍加转化：每只鸟取值 0/1 ，需要有偶数个朋友和他取值相同。
偶数且01，这不由得转化到异或的方向。
这样我们就有了一个森破的想法：（设 $pos[i]$ 为 $i$ 号鸟的取值，上游为 1 ，下游为 0；设 $A[i][j]$ 代表 $j$ 是否（0/1）是 $i$ 的朋友）
但是很显然这是错的，因为我们其实只是做到了让上游有偶数个朋友，要是这只鸟本身就在下游呢？
我们改一改思路：
- 如果一只鸟有偶数个朋友，则只需满足上游有偶数个，下游必然也会有偶数个。
- 如果一只鸟有奇数个朋友，若当前为上游，则需要偶数个在上游；若当前为下游，则需要奇数个在上游，这样一来下游就有偶数个。
然后把每只鸟对应的方程都列出来，高消解异或方程组即可。
代码实现：
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| #include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int MAX = 2e3 + 7;
const int MOD = 1e9 + 7;
void print(bool a)
{
cout << (a ? "YES" : "NO") << endl;
}
int N;
int n;
struct matrix
{
bitset<MAX> num[MAX];
bitset<MAX> &operator[](int id)
{
return num[id];
}
void SWAP(int x, int y)
{
swap(num[x], num[y]);
}
void XOR(int x, int y)
{
num[x] = num[x] ^ num[y];
}
} ORZ, RBQ;
void gauss()
{
for (int i = 1; i <= N; i++)
{
int k = i;
for (int j = i; j <= N; j++)
{
if (ORZ[j][i])
{
k = j;
break;
}
}
if (ORZ[k][i] == 0)
{
continue;
}
ORZ.SWAP(k, i);
for (int j = 1; j <= N; j++)
{
if (ORZ[j][i] && j != i)
{
ORZ.XOR(j, i);
}
}
}
}
vector<int> v;
signed main()
{
cin >> N;
n = N;
memset(ORZ.num, 0, sizeof(ORZ.num));
for (int i = 1; i <= N; i++)
{
int tot = 0;
cin >> tot;
for (int j = 1; j <= tot; j++)
{
int k;
cin >> k;
ORZ[i][k] = 1;
}
if (tot & 1)
{
ORZ[i][i] = 1;
ORZ[i][N + 1] = 1;
}
}
gauss();
for (int i = N; i >= 1; i--)
{
if (ORZ[i][i])
{
if (ORZ[i][N + 1])
v.push_back(i);
}
else if (ORZ[i][N + 1])
{
cout << "Impossible\n";
return 0;
}
}
cout << v.size();
cout << endl;
for (int i : v)
{
cout << i << ' ';
}
}
|
