SGU 260.Puzzle (异或高斯消元)

时间:2021-09-28 08:20:22

题意:

  有n(<200)个格子,只有黑白两种颜色.可以通过操作一个格子改变它和其它一些格子的颜色。给出改变的关系和n个格子的初始颜色,输出一种操作方案使所有格子的颜色相同。


Solution:

  很显然的高斯消元。

这里采用了类似SGU275的方法做。

/*
解异或方程组
*/
#include <iostream>
#include <bitset>
#include <cstring>
using namespace std;
const int N = ;
bitset<N> a[N], mask[N];
int base[N];
int Gauss ( int n )
{
for ( int i = ; i <= n; ++i ) {
for ( int j = ; j <= n; ++j ) {
if ( a[i][j] ) {
if ( !~base[j] ) {
mask[i][i] = ;
base[j] = i;
break;
}
a[i] ^= a[base[j]];
mask[i] ^= mask[base[j]];
}
}
}
} int n, m;
int main()
{
ios::sync_with_stdio ( );
cin >> n;
for ( int i = , k; i <= n; ++i ) {
cin >> k;
for ( int j = , t; j <= k; ++j ) {
cin >> t;
a[i][t] = ;
}
}
memset ( base, -, sizeof base );
Gauss ( n );
for ( int i = , k; i <= n; ++i ) {
cin >> k;
a[n + ][i] = k;
a[n + ][i] = k ^ ;
}
int k;
for ( k = ; k <= n; ++k ) {
if ( a[n + ][k] == ) {
if ( !~base[k] ) {
break;
}
a[n + ] ^= a[base[k]];
mask[n + ] ^= mask[base[k]];
}
}
if ( k > n ) {
cout << mask[n + ].count() << endl;
for ( int i = ; i <= n; ++i ) {
if ( mask[n + ][i] )
cout << i << " ";
}
} else {
for ( k = ; k <= n; ++k ) {
if ( a[n + ][k] ) {
if ( !~base[k] ) {
break;
}
a[n + ] ^= a[base[k]];
mask[n + ] ^= mask[base[k]];
}
}
if ( k > n ) {
cout << mask[n + ].count() << endl;
for ( int i = ; i <= n; ++i ) {
if ( mask[n + ][i] )
cout << i << " ";
}
} else {
cout << - << endl;
}
}
}