![[POJ1681]Painter's Problem（高斯消元，异或方程组，状压枚举）](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "[POJ1681]Painter's Problem（高斯消元，异或方程组，状压枚举）")
题目链接：http://poj.org/problem?id=1681
题意：还是翻格子的题，但是这里有可能出现*变元，这时候枚举一下就行。。（其实这题直接状压枚举就行）
/*
━━━━━┒ギリギリ♂ eye！
┓┏┓┏┓┃キリキリ♂ mind！
┛┗┛┗┛┃＼○／
┓┏┓┏┓┃ /
┛┗┛┗┛┃ノ)
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┃┃┃┃┃┃
┻┻┻┻┻┻
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std; const int maxn = ;
int equ, var;
int a[maxn][maxn];
int x[maxn];
int free_x[maxn];
int free_num; int gauss() {
int max_r, col, k;
free_num = ;
for(k = , col = ; k < equ && col < var; k++, col++) {
max_r = k;
for(int i = k + ; i < equ; i++) {
if(abs(a[i][col]) > abs(a[max_r][col]))
max_r = i;
}
if(a[max_r][col] == ) {
k--;
free_x[free_num++] = col;
continue;
}
if(max_r != k) {
for(int j = col; j < var + ; j++)
swap(a[k][j], a[max_r][j]);
}
for(int i = k + ; i < equ; i++) {
if(a[i][col] != ) {
for(int j = col; j < var + ; j++) {
a[i][j] ^= a[k][j];
}
}
}
}
for(int i = k; i < equ; i++) {
if(a[i][col] != )
return -;
}
if(k < var) return var - k;
for(int i = var - ; i >= ; i--) {
x[i] = a[i][var];
for(int j = i + ; j < var; j++) {
x[i] ^= (a[i][j] & x[j]);
}
}
return ;
} const int dx[] = {, , , , -};
const int dy[] = {, , -, , };
char G[][];
int tmp[][];
int n; bool ok(int x, int y) {
return x >= && x < n && y >= && y < n;
} int get(int x , int y) {
int c = G[x][y];
for(int i = ; i < ; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if(ok(xx, yy)) c += tmp[xx][yy];
}
return c % ;
} int calc() {
for(int i = ; i < n; i++) {
for(int j = ; j < n; j++) {
if(get(i-, j)) tmp[i][j] = ;
}
}
for(int i = ; i < n; i++) {
if(get(n-, i)) return -;
}
int p = ;
for(int i = ; i < n; i++) {
for(int j = ; j < n; j++) {
p += tmp[i][j];
}
}
return p;
} int solve(int t) {
n = t;
for(int i = ; i < n; i++) {
for(int j = ; j < n; j++) {
if(G[i][j] == 'w') G[i][j] = ;
else G[i][j] = ;
}
}
int ret = -;
int nn = << n;
for(int i = ; i < nn; i++) {
memset(tmp, , sizeof(tmp));
for(int j = ; j < n; j++) tmp[][n-j-] = i >> j & ;
int num = calc();
if(num >= && (ret < || ret > num)) ret = num;
}
return ret;
} int main() {
freopen("in", "r", stdin);
int T, _ = ;
scanf("%d", &T);
while(T--) {
scanf("%d", &var);
memset(a, , sizeof(a));
memset(x, , sizeof(x));
memset(free_x, , sizeof(free_x));
for(int i = ; i < var; i++) {
scanf("%s", G[i]);
}
int cnt = ;
for(int i = ; i < var; i++) {
for(int j = ; j < var; j++) {
if(G[i][j] == 'w') a[cnt][var*var] = ;
cnt++;
}
}
int t = var;
var = var * var;
equ = var;
for(int i = ; i < t; i++) {
for(int j = ; j < t; j++) {
int q = i * t + j;
a[q][q] = ;
if(i > ) a[(i-)*t+j][q] = ;
if(i < t - ) a[(i+)*t+j][q] = ;
if(j > ) a[i*t+j-][q] = ;
if(j < t - ) a[i*t+j+][q] = ;
}
}
// for(int i = 0; i < t; i++) {
// for(int j = 0; j < t; j++) {
// printf("%d ", a[i][j]);
// }
// printf("\n");
// }
int v = gauss();
if(v == -) puts("inf");
else if(v == ) {
int ret = ;
for(int i = ; i < var; i++) ret += x[i];
printf("%d\n", ret);
}
else {
int ret = solve(t);
if(ret < ) puts("inf");
else printf("%d\n", ret);
}
}
return ;
}
什么玩意，在发现有*变元的时候，也求x的解不就好了，反正*变元默认搞成0.
/*
━━━━━┒ギリギリ♂ eye！
┓┏┓┏┓┃キリキリ♂ mind！
┛┗┛┗┛┃＼○／
┓┏┓┏┓┃ /
┛┗┛┗┛┃ノ)
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┃┃┃┃┃┃
┻┻┻┻┻┻
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std; const int maxn = ;
int equ, var;
int a[maxn][maxn];
int x[maxn];
int free_x[maxn];
int free_num;
int ret; int gauss() {
int max_r, col, k;
free_num = ;
for(k = , col = ; k < equ && col < var; k++, col++) {
max_r = k;
for(int i = k + ; i < equ; i++) {
if(abs(a[i][col]) > abs(a[max_r][col]))
max_r = i;
}
if(a[max_r][col] == ) {
k--;
free_x[free_num++] = col;
continue;
}
if(max_r != k) {
for(int j = col; j < var + ; j++)
swap(a[k][j], a[max_r][j]);
}
for(int i = k + ; i < equ; i++) {
if(a[i][col] != ) {
for(int j = col; j < var + ; j++) {
a[i][j] ^= a[k][j];
}
}
}
}
for(int i = k; i < equ; i++) {
if(a[i][col] != )
return -;
}
// if(k < var) return var - k;
for(int i = var - ; i >= ; i--) {
x[i] = a[i][var];
for(int j = i + ; j < var; j++) {
x[i] ^= (a[i][j] & x[j]);
}
}
return ;
} char G[maxn][maxn]; int main() {
// freopen("in", "r", stdin);
int T, _ = ;
scanf("%d", &T);
while(T--) {
scanf("%d", &var);
memset(a, , sizeof(a));
memset(x, , sizeof(x));
memset(free_x, , sizeof(free_x));
for(int i = ; i < var; i++) {
scanf("%s", G[i]);
}
int cnt = ;
for(int i = ; i < var; i++) {
for(int j = ; j < var; j++) {
if(G[i][j] == 'w') a[cnt][var*var] = ;
cnt++;
}
}
int t = var;
var = var * var;
equ = var;
for(int i = ; i < t; i++) {
for(int j = ; j < t; j++) {
int q = i * t + j;
a[q][q] = ;
if(i > ) a[(i-)*t+j][q] = ;
if(i < t - ) a[(i+)*t+j][q] = ;
if(j > ) a[i*t+j-][q] = ;
if(j < t - ) a[i*t+j+][q] = ;
}
}
// for(int i = 0; i < t; i++) {
// for(int j = 0; j < t; j++) {
// printf("%d ", a[i][j]);
// }
// printf("\n");
// }
int v = gauss();
ret = ;
if(v == -) puts("inf");
else {
for(int i = ; i < var; i++) ret += x[i];
printf("%d\n", ret);
}
}
return ;
}