高斯消元练习题集

1.POJ-1222 EXTENDED LIGHTS OUT

---

题意 开关问题，给一个矩阵，每次翻转，上下左右都会一起翻转，问你翻转哪些位置，可以把灯全部关上。

思路

异或运算下的高斯消元

典型的开关问题，和 POJ 1830 开关问题 是一样的属于 XOR 类型的消元。

/*************************** *author:ccf *source:poj-1222- EXTENDED LIGHTS OUT *topic:高斯消元 ****************************/ #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define ll long long using namespace std; const int N = 40; const int inf = 50; int cas,n,icas = 1; int a[N][N];//增广矩阵 int equ,var;//equ：行 var： 列 int free_i[N],free_cnt; int x[N],mp[N];//x[N]自由元数组 //void debug() { // for(int i = 0 ; i < equ; i++) { // for(int j = 0; j <= var; j++) // printf("%d ",a[i][j]); // printf("\n"); // } // //} bool Gauss() { int k,col,max_i;//k是列 col是行 max_i是最大行 //转化为阶梯阵 for(k = col = 0; k < equ && col < var; k++,col++) { //找到最大行 max_i = k; for(int i = k + 1; i < equ; i++) { if(abs(a[i][col]) > abs(a[max_i][col])) max_i = i; } if(a[max_i][col] == 0) { free_i[col] = 1; x[free_cnt++] = col; k--; continue; } if(k != max_i) { for(int j = col; j <= var; j++) { swap(a[max_i][j],a[k][j]); } } //开始化简阶梯阵 for(int i = 0; i < equ; i++) { if(a[i][col] && i != k) for(int j = col; j <= var; j++) a[i][j] ^= a[k][j]; } } //debug(); for(int i = k; i < equ; i++) if(a[i][var]) return false; return true; } int main() { //freopen("date.in","r",stdin); equ = var = 30; scanf("%d",&cas); while(cas--) { int cnt = 0; memset(a,0,sizeof(a)); memset(free_i,0,sizeof(free_i)); memset(x,0,sizeof(x)); memset(mp,0,sizeof(mp)); for(int i = 0; i < equ; i++) { scanf("%d",&mp[i]); a[i][var] = mp[i]; } //方格化成增广矩阵 for(int i = 0 ; i < equ; i++) { a[i][i] = 1; if(i < 24) a[i][i+6] = 1; if(i > 5) a[i][i-6] = 1; if(i % 6 != 0) a[i][i-1] = 1; if(i % 6 != 5) a[i][i+1] = 1; } if(!Gauss()) printf("no solution!\n"); else { printf("PUZZLE #%d\n",icas++); for(int i = 1; i <= 30; i++) { printf("%d",a[i-1][var]); if(i % 6 == 0) printf("\n"); else printf(" "); } } } return 0; }

2.POJ-2947-Widget Factory

题意 有n种饰品，每种的加工时间为3~9天，现在知道m条记录，每条记录形如：开始时间是周几，终止时间是周几，加工出来哪些饰品，各多少件。但是不知道持续了多少周。 求每种饰品的加工时间。

需要判断无解和多解。 思路

高斯消元解同余方程

在原本高斯约旦消元的基础上，加上取模的运算，最后每一行得到一个 $$Ax\equiv C(modp)$$形式的式子，使用扩展欧几里得解同余方程即可，也有直接模拟取余操作的方法。

/*********************** *author:ccf *source:poj-2974 Widget Factory *topic：高斯消元解同余方程 ************************/ #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define ll long long using namespace std; const int N = 600; int cas,n,m,icas; char start[5],fired[5]; int a[N][N],ans[N];//行列式 解集 int equ,var,free_cnt = 0; void debug() { for(int i = 1; i <= equ; i++) { for(int j = 1; j <= var + 1; j++) { printf("%d ",a[i][j]); } printf("\n"); } printf("\n"); } int sti(char *s) { if(strcmp(s, "MON") == 0) return 1; else if(strcmp(s, "TUE") == 0) return 2; else if(strcmp(s, "WED") == 0) return 3; else if(strcmp(s, "THU") == 0) return 4; else if(strcmp(s, "FRI") == 0) return 5; else if(strcmp(s, "SAT") == 0) return 6; else if(strcmp(s, "SUN") == 0) return 7; } int gcd(int a, int b) { return b == 0 ? a : gcd(b,a%b); } int lcm(int a,int b) { return a / gcd(a,b) * b; } int Gauss() { int free_i[N],free_x[N],free_cnt = 0; int k,col,max_i; for(k = col = 1; k <= equ && col <= var; k++,col++) { max_i = k; //找到最大值 for(int i = k + 1; i <= equ; i++) { if(abs(a[i][col]) > abs(a[max_i][col])) max_i = i; } //交换最大值 if(k != max_i) { for(int j = k; j <= var + 1; j++) { swap(a[max_i][j],a[k][j]); } } //确定自由元 if(a[k][col] == 0) { free_x[++free_cnt] = col; k--; continue; } //化简行列式 for(int i = 1; i <= equ; i++) { if(a[i][col] != 0 && i != k) { int LCM = lcm(abs(a[i][col]),abs(a[k][col])); int tmp1 = LCM/abs(a[i][col]),tmp2 = LCM/abs(a[k][col]); if(a[i][col] * a[k][col] < 0) tmp2 = -tmp2; for(int j= 1; j <= var + 1; j++) { a[i][j] = ( (a[i][j] * tmp1 - a[k][j] * tmp2) % 7 + 7) % 7; } }//debug(); } } //无解 for(int i = k ; i <= equ; i++) if(a[i][var+1]) return -1; //存在自由元 多个解 if(k <= var) return var - k + 1; //只有一个解 for(int i = var; i > 0; i--) { int tmp = a[i][var + 1]; for(int j = i + 1; j <= var; j++) { if(a[i][j] != 0) tmp -= a[i][j] * ans[j]; tmp = (tmp % 7 + 7) % 7; } while(tmp % a[i][i] != 0) tmp += 7; ans[i] = (tmp / a[i][i] )% 7; } return 0; } int main() { freopen("data.in","r",stdin); while(scanf("%d %d",&n,&m) && n + m != 0) { memset(a,0,sizeof a); memset(ans,0,sizeof ans); equ = m; var = n; //化为阶梯阵 for(int i = 1,k; i <= m; i++) { scanf("%d %s %s",&k,start,fired); //printf("%d %s %s\n",k,start,fired); a[i][n + 1] =((sti(fired) - sti(start) + 1)%7 + 7) % 7; for(int j = 1,tmp; j <= k; j++) { scanf("%d",&tmp); a[i][tmp]++; a[i][tmp] %= 7; } } //debug(); int res = Gauss(); if(res == -1) printf("Inconsistent data.\n"); else if(res == 0) { for(int i = 1; i <= n; i++) { if(ans[i] < 3) ans[i] += 7; printf("%d",ans[i]); if(i == n) printf("\n"); else printf(" "); } } else { printf("Multiple solutions.\n"); } } return 0; }

3.POJ-1681-Painter’s Problem

题意

异或运算下的高斯消元

给方格染色，原本是白的，可以染成黄色，每次染一个格子，上下左右的方格就都会翻转，问全染成黄色的最小染色次数是多少？

思路

仍属于开关问题，XOR 操作下的高斯消元。

/******************* *author:ccf *source:poj 1681 - Painter's Problem *topic:高斯消元 *******************/ #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define ll long long using namespace std; const int N = 251; int cas,n; int a[N][N], mp[N]; int equ,var,ans = 0; void debug(){ for(int i= 1 ; i <= n*n; i++){ for(int j = 1; j <= n*n + 1; j++) printf("%d ",a[i][j]); printf("\n"); } printf("\n"); } bool Gauss(){ int free_x[N],free_cnt = 0; int k,col,max_i; for(k = col = 1; k <= equ && col <= var; k++,col++){ //找最大值 max_i = k; for(int i = k + 1; i <= equ; i++){ if(a[max_i][col] < a[i][col]) max_i = i; } if(k != max_i){ for(int j = col; j <= var + 1; j++) swap(a[max_i][j],a[k][j]); } //获取自由元 if(a[k][col] == 0){ free_x[++free_cnt] = col; k--; continue; } //化简阶梯阵 for(int i = 1; i <= equ; i++){ if(i != k && a[i][col]){ for(int j = col; j <= var + 1; j++) a[i][j] ^= a[k][j]; } } //debug(); } //存在 0 = 1 的情况，无解 for(int i = k; i <=equ ; i++) if(a[i][var + 1]) return false; //debug(); for(int i = 1; i <= equ; i++) if(a[i][var + 1] ) ans++; return true; } int main(){ //freopen("date.in","r",stdin); scanf("%d",&cas); while(cas--){ int cnt = 0; char c; ans = 0; memset(a,0,sizeof a); scanf("%d",&n); equ = var = n*n; for(int i = 1; i <= n; i++){ getchar(); for(int j = 1; j <= n; j++){ scanf("%c",&c); if(c == 'y') mp[++cnt] = 1; else mp[++cnt] = 0; } } //方格转化为增广矩阵 for(int i = 1; i <= cnt; i++){ a[i][i] = 1; a[i][var + 1] = 1 ^ mp[i]; if(i > n) a[i][i-n] = 1; if(i < n * (n-1) + 1) a[i][i+n] = 1; if(i % n != 0) a[i][i+1] = 1; if(i % n != 1) a[i][i-1] = 1; } //debug(); if(!Gauss()) printf("inf\n"); else{ printf("%d\n",ans); } } return 0; } /* 1 3 yyy yyy yyy */

4.POJ-2065-SETI

题意 思路

高斯消元解同余方程组

和POJ-2947-Widget Factory 是一样的，高斯消元时带上取模运算，最后使用扩展欧几里得算法进行同余方程的求解。

/*********************** *author:ccf *source:POJ-2065-SETI *topic：高斯消元解同余方程 ************************/ #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #define ll long long using namespace std; const int N = 107; int equ,var,cas,p; int a[N][N],ans[N]; char info[N]; void debug() { for(int i = 1; i <=equ; i++) { for(int j = 1; j <= var + 1; j++) printf("%d ",a[i][j]); printf("\n"); } printf("\n"); } int gcd(int a,int b) { return b == 0 ? a : gcd(b,a%b); } int lcm(int a,int b) { return a / gcd(a,b) * b; } int exgcd(int a,int b,int &x,int &y){ if(b == 0){ x = 1;y = 0; return a; } int t = exgcd(b,a%b,x,y); int x0 = x, y0= y; x = y0; y = x0 - a / b * y0; return t; } int qpow(int a, int b,int mod) { int res = 1; while(b) { if(b & 1) { res = res * a % mod; } a = a * a % mod; b >>= 1; } return res; } int sti(char *s) { int len = strlen(s); for(int i = 0; i < len; i++) { if(s[i] == '*') a[i + 1][len + 1] = 0; else a[i + 1][len + 1] = (s[i] - 'a' + 1) % p; } return len; } int Gauss() { int free_x[N],free_i[N],free_cnt = 0; int k,col,max_i; for(k = col = 1; k <= equ && col <= var; k++,col++) { max_i = k; //找出最大值并交换 for(int i = k + 1; i <= equ; i++) if(abs(a[i][col]) > abs(a[max_i][col])) max_i = i; if(k != max_i) { for(int j = col; j <= var + 1; j++) swap(a[k][j],a[max_i][j]); } if(a[k][col] == 0) { free_x[++free_cnt] = col; k--; continue; } //化简阶梯阵 for(int i = 1; i <= equ; i++) { if(i != k && a[i][col]) { int LCM = lcm(abs(a[i][col]),abs(a[k][col])); int tmp1 = LCM / abs(a[i][col]),tmp2 = LCM / abs(a[k][col]); if(a[i][col] * a[k][col] < 0) tmp2 = -tmp2; for(int j = 1; j <= var + 1; j++) { a[i][j] = ((a[i][j] * tmp1 - a[k][j] * tmp2) % p + p) % p; } } //debug(); } } for(int i = k; i <= equ; i++) if(a[i][var + 1])return -1; return 0; } void solve(){ int x,y; for(int i = 1; i <= var; i++){ int A = a[i][i], B = p, C = a[i][var + 1]; int g = exgcd(A,B,x,y); A /= g; B /= g; C /= g; int x0 = x * C; x0 = (x0 % B + B ) % B; ans[i] = x0; } } int main() { //freopen("data.in","r",stdin); scanf("%d",&cas); while(cas--) { memset(a,0,sizeof a); memset(ans,0,sizeof ans); scanf("%d %s",&p,info); int len = sti(info); equ = var = len; for(int i = 1; i <= len; i++) { for(int j = 1; j <= len; j++) { a[i][j] = qpow(i,j-1,p); } } //debug(); if(Gauss() != -1){ solve(); for(int i = 1; i <= len; i++) printf("%d ",ans[i]); }else { printf("No Smoking!"); } puts(""); } return 0; }

5.POJ-1753 - Flip Game

题意

给一个棋盘，可以黑色白色棋子相互翻转，每次翻转一个棋子，其上下左右的棋子也会翻转。变成全白或全黑的时候结束，问结束的最小步数是多少？

思路

高斯消元 + 枚举不定元

开关问题，但有一点不同的是：当存在不定变元的时候，我们要枚举每个不定元的状态来求出最小值，$cnt$ 个不定元一共有$2^{cnt}$种状态，用数组记录不定元，使用二进制来枚举可加快速度。

/******************* *author:ccf *source:poj 1753 - Flip Game *topic:高斯消元 *******************/ #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define ll long long using namespace std; const int N = 20; int cas,n = 4; int a[N][N], mp[N]; int equ,var; //void debug(){ // for(int i= 1 ; i <= n*n; i++){ // for(int j = 1; j <= n*n + 1; j++) // printf("%d ",a[i][j]); // printf("\n"); // } // printf("\n"); //} int Gauss(){ int ans = N; int free_x[N],free_cnt = 0; int free_num[N],free_i[N]; int k,col,max_i; memset(free_num,0,sizeof(free_num)); memset(free_x,0,sizeof(free_x)); memset(free_i,0,sizeof(free_i)); for(k = col = 1; k <= equ && col <= var; k++,col++){ //找最大值 max_i = k; for(int i = k + 1; i <= equ; i++){ if(a[max_i][col] < a[i][col]) max_i = i; } if(k != max_i){ for(int j = col; j <= var + 1; j++) swap(a[max_i][j],a[k][j]); } //获取自由元 if(a[k][col] == 0){ free_i[col] = 1; free_x[++free_cnt] = col; k--; continue; } //化简阶梯阵 for(int i = 1; i <= equ; i++){ if(i != k && a[i][col]){ for(int j = col; j <= var + 1; j++) a[i][j] ^= a[k][j]; } } //debug(); } //存在 0 = 1 的情况，无解 for(int i = k; i <=equ ; i++) if(a[i][var + 1]) return N; //debug(); int limit = 1 << free_cnt; //for(int i = 1; i <= free_cnt; i++) printf("%d ",free_x[i]); for(int i = 0; i < limit; i++){ int num = 0,m = i; memset(free_num,0,sizeof free_num); //使用二进制来开始枚举自由元 for(int j = 1; j <= free_cnt; j++){ if(m & 1){ free_num[free_x[j]] = 1; num++; } m /= 2; } //根据不定元确定主元 for(int j = k - 1; j >= 1; j--){ if(!free_i[j]){ int tmp = a[j][var+1]; for(int l = j + 1; l <= var; l++) if(a[j][l]) tmp ^= free_num[l]; free_num[j] = tmp; if(tmp) num++; } } //printf("num = %d\n",num); ans = min(ans,num); } return ans; } int main(){ int cnt = 0; char c; memset(a,0,sizeof a); equ = var = 16; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ scanf("%c",&c); if(c == 'b') mp[++cnt] = 1; else mp[++cnt] = 0; } getchar(); } //方格转化为增广矩阵 for(int i = 1; i <= cnt; i++){ a[i][i] = 1; a[i][var + 1] = 0 ^ mp[i]; if(i > n) a[i][i-n] = 1; if(i < n * (n-1) + 1) a[i][i+n] = 1; if(i % n != 0) a[i][i+1] = 1; if(i % n != 1) a[i][i-1] = 1; } //debug(); int tmp = Gauss(); memset(a,0,sizeof a); for(int i = 1; i <= cnt; i++){ a[i][i] = 1; a[i][var + 1] = 1 ^ mp[i]; if(i > n) a[i][i-n] = 1; if(i < n * (n-1) + 1) a[i][i+n] = 1; if(i % n != 0) a[i][i+1] = 1; if(i % n != 1) a[i][i-1] = 1; } tmp = min(tmp,Gauss()); if(tmp == N) printf("Impossible\n"); else{ printf("%d\n",tmp); } return 0; } /* bwwb bbwb bwwb bwww */