题意:给定20个01串(最终的状态)，每个点变化时会影响左右点，问最终是20个0所需最少操作数？
水题。。直接修改增广矩阵即可；看来最优解不是用高斯消元(若是有Gauss消元0ms A的请留言~~)，很多是0ms过的，我用了32ms;
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> 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)) #define inf 0x3f3f3f3f int dir[2][4] = {{0,1,0,-1},{1,0,-1,0}}; int a[23][23]; int equ,var; int x[23],free_var[400]; void debug() { puts("********"); int i,j; rep0(i,0,equ){ rep1(j,0,var) cout<<a[i][j]<<" "; cout<<endl; }puts("********"); } int Gauss() { int i,j,k,row,col,cnt = 0; for(row = 0,col = 0;row < equ && col < var;row++,col++){ int mx = row; rep0(j,row+1,equ) if(abs(a[j][col]) > abs(a[mx][col])) mx = j; if(a[mx][col] == 0){ row--; // 行不变；不能通过这里记录自由变元的个数，只能记录没用的col free_var[cnt++] = col;//记录自由变元的标号； continue; } if(mx != row) rep1(k,col,var) swap(a[row][k],a[mx][k]); rep0(j,row+1,equ){ if(a[j][col]){ rep1(k,col,var) a[j][k] ^= a[row][k]; } } } //debug(); //rep0(i,row,equ) //if(a[i][var] != 0) return -1; //无解 //枚举自由变元,row表示有用的方程数方程,但是要在判断出有解的前提下才能说有多组解； //if(row < var) return var - row; //当不需要枚举时，直接返回自由变元的个数 int ans = inf,tot = 1 <<(var - row); rep0(i,0,tot){ int cnt = 0,tmp = i; rep0(j,0,var - row){ x[free_var[j]] = (tmp&1); if(x[free_var[j]]) cnt++;//** tmp >>= 1; } rep_1(i,row-1,0){ x[i] = a[i][var];//现在赋为a[i][var],若为自由变元之后还是会等于0，不会重复计算； rep0(j,i+1,equ){ x[i] ^= (a[i][j] && x[j]); //第j个灯会影响到第i盏灯，同时第j盏灯也会亮 } if(x[i]) cnt++; } ans = min(ans,cnt); } return ans; } void init(int n) { rep0(i,0,n){ int id = i; a[id][id] = 1; if(id > 0) a[id-1][id] = 1; if(id < var-1) a[id+1][id] = 1; } } int tmp[20]; int main() { int n = 20,i,id = 0; equ = var = n; rep0(i,0,20){ scanf("%d",&a[i][var]); } init(n); //debug(); printf("%d ",Gauss()); return 0; }