POJ - 1830 - 开关问题 ，POJ - 3185 - The Water Bowls，POJ - 1753 -Flip Game - （高斯消元解异或方程组）

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~!!

解析：

高斯消元解异或方程组的题目，还不错的题，此题与POJ 1681 Painter's Problem之间的不同就是，这里末状态是给出的而不是固定的，

那么我们在列异或方程时，其实相当于对于每个点解一个方程：

　　初始的状态  XOR  自己操作没操作 XOR  周围的四个点操作没操作 （对本点有影响的点变操作没操作） = 目标状态

两边同时XOR之前的状态。

　　 自己操作没操作  XOR  周围的四个点操作没操作  = 初始的状态 XOR 目标状态

得到关于每个点的一个方程：ai1*x1  xor  ai2*x2  xor ai3*x3  xor ...xor  ain*xn = bi XOR c[i]

这里aij代表j对i的影响，b[i]和c[i]代表每个灯的始末状态。

列出方程后，由于只是求方案数，并不需要求具体方案，所以我们只需化简增广矩阵求出自由变量的个数free_num而不需要枚举自由元回带求解，那么答案就是2^free_num.

不懂异或方程组见高斯消元：

http://blog.csdn.net/sdau20163942/article/details/79182813

http://blog.csdn.net/sdau20163942/article/details/79196657

代码：

#include<iostream> #include<string> #include<cstdio> #include<algorithm> #include<cmath> #include<iomanip> #include<queue> #include<cstring> #include<map> using namespace std; typedef long long ll; #define M 40 int n; int b[M]; //等式右边的常数 int a[M][M]; //系数矩阵 int free_num;//自由元个数 //n个方程，n个变元，增广矩阵n行n+1列 ll Gauss() {free_num=0;int col,row,i,j,max_r;for(col=1,row=1;col<=n;col++,row++) //解X[col]，col是列，row是行{//列主元选取max_r=row;for(i=row;i<=n;i++){if(a[i][col]) {max_r=i; break;}}if(max_r!=row){for(i=col;i<=n+1;i++) swap(a[row][i],a[max_r][i]);}if(!a[row][col]) //X[col]为自由元{row--; //还是看本行的方程，看下一个变量free_num++;continue;}//消元for(i=row+1;i<=n;i++){if(a[i][col]!=0){for(j=col;j<=n+1;j++)a[i][j]^=a[row][j];}}}for(i=row;i<=n;i++) //判断有无解{if(a[i][n+1]!=0)return -1;}return (1ll<<free_num); //有free_num个方程就有2^free_num种方案 } int main() {int i,T,tmp,s,e;scanf("%d",&T);while(T--){scanf("%d",&n);memset(a,0,sizeof(a));for(i=1;i<=n;i++){scanf("%d",&b[i]); //输入初始状态a[i][i]=1; //a[i][i]=1代表灯对自身的影响}for(i=1;i<=n;i++){scanf("%d",&tmp); //输入目标状态b[i]=b[i]^tmp; a[i][n+1]=b[i]; //增广矩阵的最后一列即等号右边的赋值}while(scanf("%d%d",&s,&e)!=EOF){if(s==0&&e==0)break;a[e][s]=1; //a[i][j]代表j灯对i灯有影响}ll ans=Gauss();if(ans==-1)printf("Oh,it's impossible~!!\n");elseprintf("%lld\n",ans);}return 0; }

POJ - 3185 - The Water Bowls

题目连接：http://poj.org/problem?id=3185

题意是有20个'01'串在一条直线上，每个点状态可以改变，改变同时影响左右两个点，那么给出初始串，求操作哪些点可以使得这些点最终全为'0'，要求的是最少操作几个点，这个与POJ 1681 Painter's Problem就更相似一些。需要枚举自由元来找最少操作数。

代码：

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
#define M 40
int n=20;
int b[M],x[M];//b是等式右边常数，x存求解的结果
int a[M][M];  //系数矩阵
int free_x[M];//存自由元
int free_num; //自由元个数
//20个方程，20个变元，增广矩阵20行21列
int Gauss()
{free_num=0;int col,row,i,j,max_r;for(col=1,row=1;col<=n;col++,row++) //解X[col]，col是列，row是行{//列主元选取max_r=row;for(i=row;i<=n;i++){if(a[i][col]) {max_r=i; break;}}if(max_r!=row){for(i=col;i<=n+1;i++) swap(a[row][i],a[max_r][i]);}if(!a[row][col]) //X[col]为自由元{row--;       //还是本行的方程，看下一个变量free_x[free_num++]=col;continue;}//消元for(i=row+1;i<=n;i++){if(a[i][col]!=0){for(j=col;j<=n+1;j++)a[i][j]^=a[row][j];}}}ll stat=(1ll<<free_num);ll free_index;int res=0x3fffffff,cnt,tmp;for(i=0;i<stat;i++)         //每种自由元的枚举{cnt=0;free_index=i;for(j=0;j<free_num;j++) //当前枚举下为每个自由元赋值{x[free_x[j]]=(free_index&1);if(x[free_x[j]]) cnt++;free_index>>=1;}//回带求解for(j=row-1;j>=1;j--){tmp=a[j][n+1];for(int k=j+1;k<=n;k++){if(a[j][k]) tmp^=x[k];}x[j]=tmp;if(x[j]) cnt++;}res=min(res,cnt);}return res;
}
void init()
{int i;memset(a,0,sizeof(a));a[1][1]=a[20][20]=1;a[2][1]=a[19][20]=1;for(i=2;i<=19;i++){a[i-1][i]=a[i][i]=a[i+1][i]=1;}
}
int main()
{int i;init(); //初始化增广矩阵for(i=1;i<=20;i++){scanf("%d",&b[i]);a[i][21]=b[i];}int ans=Gauss();printf("%d\n",ans);return 0;
}

题目链接：http://poj.org/problem?id=1753

解析：

题意：给出一个4*4的矩阵，由白块或黑块组成，白块反转的黑块，黑块翻转的白块，操作一块周围受影响，问操作哪些块能使得最终全为白块或全为黑块，求最少操作数几块。
那么这个问题，与POJ 1681 Painter's Problem不同的区别在于，最终状态可以有两种结果（全为白或全为黑），那么可以对两种结果做两次高斯消元，在两次结果中取最小的。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <math.h>
#include <iomanip>
#include <cstring>
using namespace std;
typedef long long ll;
#define M 20
int a[M][M];
int x[M];
int free_x[M];
int free_num;
char ch[M][M]; //存输入的图形//(-1表示无解，大于0表示结果)
//有equ个方程，var个变元。增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var.
int Gauss(int equ,int var)
{int i,j,k;int max_r;int col;int free_index;free_num=0;for(i=0;i<=var;i++){x[i]=0; free_x[i]=0;}for(col=0,k=0;k<equ&&col<var;k++,col++){max_r=k;for(i=k+1;i<equ;i++){if(a[i][col]) {max_r=i;break;}}if(max_r!=k){for(j=k;j<var+1;j++) swap(a[k][j],a[max_r][j]);}if(a[k][col]==0){k--;free_x[free_num++]=col;continue;}for(i=k+1;i<equ;i++) //消元{if(a[i][col]!=0){for(j=col;j<var+1;j++)a[i][j]^=a[k][j];}}}for(i=k;i<equ;i++){if(a[i][col]!=0) return -1;}int stat=1<<(var-k); //自由元个数为var-kint res=0x3fffffff;for(i=0;i<stat;i++){int cnt=0;free_index=i;for(j=0;j<var-k;j++){x[free_x[j]]=(free_index&1);if(x[free_x[j]])cnt++;free_index>>=1;}for(j=k-1;j>=0;j--)//将枚举的值带入其它方程求解{int tmp=a[j][var];for(int l=j+1;l<var;l++)if(a[j][l]) tmp^=x[l];x[j]=tmp;if(x[j]) cnt++;}/*for(j=k-1;j>=0;j--) //将枚举的值带入其它方程求解{int col;for(int l=j;l<var;l++)  if(a[j][l]){col=l;break;}//求出的col即是代表当前第j行该解的非自由元变量X[col]int tmp=a[j][var];for(int l=col+1;l<var;l++)if(a[j][l]) tmp^=x[l];x[col]=tmp;if(x[col])cnt++;}*/res=min(res,cnt);}return res;
}void init()
{memset(a,0,sizeof(a));memset(x,0,sizeof(x));memset(free_x,1,sizeof(free_x)); //1代表是自由元int i,j,t;for(i=0;i<4;i++)for(j=0;j<4;j++){t=i*4+j;a[t][t]=1;if(i>0) a[(i-1)*4+j][t]=1;if(i<3) a[(i+1)*4+j][t]=1;if(j>0) a[t-1][t]=1;if(j<3) a[t+1][t]=1;}
}
int main()
{int i,j;for(i=0;i<4;i++)for(j=0;j<4;j++)cin>>ch[i][j];init();for(i=0;i<4;i++)for(j=0;j<4;j++){if(ch[i][j]=='b')a[i*4+j][16]=0;elsea[i*4+j][16]=1;}int ans1=Gauss(16,16);init();for(i=0;i<4;i++)for(j=0;j<4;j++){if(ch[i][j]=='b')a[i*4+j][16]=1;elsea[i*4+j][16]=0;}int ans2=Gauss(16,16);if(ans1==-1&&ans2==-1){cout<<"Impossible"<<endl;}else{if(ans1==-1)cout<<ans2<<endl;else if(ans2==-1)cout<<ans1<<endl;elsecout<<min(ans1,ans2)<<endl;}return 0;
}