开关问题 POJ - 1830

本文主要是介绍开关问题 POJ - 1830，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=1830

构造异或方程组

a11*x1 ^ a12*x2 ^ ... ^ a1m*xm = b1

a21*x1 ^ a22*x2 ^ ... ^ a2m*xm = b2

...

an1*x1 ^ an2*x2 ^ ... ^ anm*xm = bn

高斯消元解异或方程模板题 如果每个灯泡起始与终止状态不同 需要一次调整 相同则不需要 分别在常数矩阵中记为1和0

对于系数矩阵 如果x会影响y 则将a[y][x]记为1 即第y个灯泡对应的方程中第x个灯泡的系数为1 因为系数为零没有意义 任何数与0异或均不变

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int a[50][50];
int s[50],e[50];
int n;int solve(int equ,int var)
{int maxx,row,col,num,i,j;for(row=0,col=0;row<equ&&col<var;row++,col++){maxx=row;for(i=row+1;i<equ;i++) if(a[maxx][col]<a[i][col]) maxx=i;if(maxx!=row) for(i=col;i<var+1;i++) swap(a[row][i],a[maxx][i]);if(a[row][col]==0){row--;continue;}for(i=row+1;i<equ;i++){if(a[i][col]!=0){for(j=col;j<var+1;j++) a[i][j]^=a[row][j];}}}for(i=row;i<equ;i++) if(a[i][col]!=0) return -1;return var-row;
}int main()
{int t,i,x,y,res;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;i++) scanf("%d",&s[i]);for(i=0;i<n;i++) scanf("%d",&e[i]);memset(a,0,sizeof(a));for(i=0;i<n;i++) a[i][n]=s[i]^e[i];for(i=0;i<n;i++) a[i][i]=1;while(1){scanf("%d%d",&x,&y);if(x==0&&y==0) break;a[y-1][x-1]=1;}res=solve(n,n);if(res==-1) printf("Oh,it's impossible~!!\n");else printf("%d\n",(1<<res));}return 0;
}

 

这篇关于开关问题 POJ - 1830的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---