本文共 2205 字，大约阅读时间需要 7 分钟。
题意:给一个5*6的01矩阵，对一个位置操作(0->1开灯或者1->0关灯)会影响到（包括自己）周边灯状态反转。问最后要使得所有的灯关掉的操作矩阵(1表示该位置的灯操作了)
提示:01矩阵，题目给了说是操作两次就相当于没操作，但是还有隐含的意思就是这就是一个异或操作(就是和mod2);对于01矩阵加上操作矩阵得到0矩阵，可知所作用的矩阵和原矩阵相同；(操作矩阵:如对（0,0）操作就相当于加上只有左上角有3个1的矩阵，但是把这个矩阵转化为了一个维度为30的向量形式，有30栈灯所以下面是一个30*30的矩阵)这是高斯消元列方程的基础；
高斯消元法:最重要的是要想到构造出一个30*30的作用矩阵，第i列数字中(列号0~29表示灯的标号)1表示第i盏灯操作会影响到1所对应的行号的灯，存储在增广矩阵a[][]中;
所谓增广矩阵就是抽象出只含方程组的系数和结果的矩阵（简化书写）。这样第i盏灯最终的状态a[i][30] = Σ(a[i][j]*x[j])(0 <= j < 30)。这就是为什么在最后化成了上三角之后怎么是对行向量操作的原因；(a[i][j] && x[j]表示第j盏灯操作会影响到第i盏灯，并且第j盏灯是开的。还有一个前提就是a[i][i] = 1,所以x[i] = a[i][var])
注:在高斯消元列方程转移到矩阵时，最好直接看每一个系数与变量之间的对应关系，而不是用行向量与列向量来看。
#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define rep0(i,l,r) for(int i = (l);i < (r);i++)#define rep1(i,l,r) for(int i = (l);i <= (r);i++)#define rep_0(i,r,l) for(int i = (r);i > (l);i--)#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)#define MS0(a) memset(a,0,sizeof(a))#define MS1(a) memset(a,-1,sizeof(a))int dir[2][4] = { { 0,1,0,-1},{ 1,0,-1,0}};int a[35][35];int equ,var;int x[35];int Guass(){ int i,j,k,free_var = 0; rep0(i,0,equ){ int mx = i; rep0(j,i+1,equ) if(abs(a[j][i]) > abs(a[mx][i])) mx = j; if(a[mx][i] == 0){ free_var++; continue; } if(mx != i) rep1(k,i,var) swap(a[i][k],a[mx][k]); rep0(j,i+1,equ){ if(a[j][i]){ //第j盏灯也会对第i盏灯产生影响； rep1(k,i,var) a[j][k] ^= a[i][k]; } } } if(free_var != 0) return free_var; rep_1(i,var-1,0){ x[i] = a[i][var]; rep0(j,i+1,equ) x[i] ^= (a[i][j] && x[j]); //第j个灯会影响到第i盏灯，同时第j盏灯也会亮。 }}void init(){ int i,j,k; rep0(i,0,5) rep0(j,0,6){ int x = i*6+j; a[x][x] = 1; rep0(k,0,4){ int nx = i + dir[0][k] ,ny = j + dir[1][k]; int pos = nx*6+ny; if(nx < 0 || nx >= 5 || ny < 0 || ny >= 6) continue; a[pos][x] = 1; //本来是对称的矩阵，因为影响是相互的，但是写成[x][pos]思想就不一样了 } }}int main(){ int T,kase = 1,i; cin>>T; while(T--){ MS0(x);MS0(a); rep0(i,0,30) scanf("%d",&a[i][30]); init(); equ = var = 30; Guass(); printf("PUZZLE #%d\n",kase++); rep0(i,0,30) printf("%d%c",x[i],(i+1)%6?' ':'\n'); } return 0;}
转载于:https://www.cnblogs.com/hxer/p/5179165.html
