POJ 1222 POJ 1830 POJ 1681 POJ 1753 POJ 3185 高斯消元求解一类开关问题

这几个题目都类似，都可以使用高斯消元来求解一个模2的01方程组来解决。

有时候需要枚举自由变元，有的是判断存不存在解

普通的问题。

肯定有唯一解。肯定枚举第一行去做，也可以使用高斯消元。

  1 /* ***********************************************
  2 Author        :kuangbin
  3 Created Time  :2013/8/17 18:25:42
  4 File Name     :F:2013ACM练习专题学习高斯消元POJ1222.cpp
  5 ************************************************ */
  6 
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <queue>
 13 #include <set>
 14 #include <map>
 15 #include <string>
 16 #include <math.h>
 17 #include <stdlib.h>
 18 #include <time.h>
 19 using namespace std;
 20 
 21 //对2取模的01方程组
 22 const int MAXN = 40;
 23 //有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var
 24 int equ,var;
 25 int a[MAXN][MAXN]; //增广矩阵
 26 int x[MAXN]; //解集
 27 int free_x[MAXN];//用来存储自由变元（多解枚举自由变元可以使用）
 28 int free_num;//自由变元的个数
 29 
 30 //返回值为-1表示无解，为0是唯一解，否则返回自由变元个数
 31 int Gauss()
 32 {
 33     int max_r,col,k;
 34     free_num = 0;
 35     for(k = 0, col = 0 ; k < equ && col < var ; k++, col++)
 36     {
 37         max_r = k;
 38         for(int i = k+1;i < equ;i++)
 39         {
 40             if(abs(a[i][col]) > abs(a[max_r][col]))
 41                 max_r = i;
 42         }
 43         if(a[max_r][col] == 0)
 44         {
 45             k--;
 46             free_x[free_num++] = col;//这个是自由变元
 47             continue;
 48         }
 49         if(max_r != k)
 50         {
 51             for(int j = col; j < var+1; j++)
 52                 swap(a[k][j],a[max_r][j]);
 53         }
 54         for(int i = k+1;i < equ;i++)
 55         {
 56             if(a[i][col] != 0)
 57             {
 58                 for(int j = col;j < var+1;j++)
 59                     a[i][j] ^= a[k][j];
 60             }
 61         }
 62     }
 63     for(int i = k;i < equ;i++)
 64         if(a[i][col] != 0)
 65             return -1;//无解
 66     if(k < var) return var-k;//自由变元个数
 67     //唯一解，回代
 68     for(int i = var-1; i >= 0;i--)
 69     {
 70         x[i] = a[i][var];
 71         for(int j = i+1;j < var;j++)
 72             x[i] ^= (a[i][j] && x[j]);
 73     }
 74     return 0;
 75 }
 76 void init()
 77 {
 78     memset(a,0,sizeof(a));
 79     memset(x,0,sizeof(x));
 80     equ = 30;
 81     var = 30;
 82     for(int i = 0;i < 5;i++)
 83         for(int j = 0;j < 6;j++)
 84         {
 85             int t = i*6+j;
 86             a[t][t] = 1;
 87             if(i > 0)a[(i-1)*6+j][t] = 1;
 88             if(i < 4)a[(i+1)*6+j][t] = 1;
 89             if(j > 0)a[i*6+j-1][t] = 1;
 90             if(j < 5)a[i*6+j+1][t] = 1;
 91         }
 92 }
 93 int main()
 94 {
 95     //freopen("in.txt","r",stdin);
 96     //freopen("out.txt","w",stdout);
 97     int T;
 98     int iCase = 0;
 99     scanf("%d",&T);
100     while(T--)
101     {
102         iCase++;
103         init();
104         for(int i = 0;i < 30;i++)
105             scanf("%d",&a[i][30]);
106         Gauss();
107         printf("PUZZLE #%d
",iCase);
108         for(int i = 0;i < 5;i++)
109         {
110             for(int j = 0;j < 5;j++)
111                 printf("%d ",x[i*6+j]);
112             printf("%d
",x[i*6+5]);
113         }
114     }
115     return 0;
116 }

View Code

POJ 1830 开关问题

输出方案数，就是求出有多少个自由变元就可以了。

  1 /* ***********************************************
  2 Author        :kuangbin
  3 Created Time  :2013/8/17 19:44:33
  4 File Name     :F:2013ACM练习专题学习高斯消元POJ1830.cpp
  5 ************************************************ */
  6 
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <queue>
 13 #include <set>
 14 #include <map>
 15 #include <string>
 16 #include <math.h>
 17 #include <stdlib.h>
 18 #include <time.h>
 19 using namespace std;
 20 //对2取模的01方程组
 21 const int MAXN = 40;
 22 //有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var
 23 int equ,var;
 24 int a[MAXN][MAXN]; //增广矩阵
 25 int x[MAXN]; //解集
 26 int free_x[MAXN];//用来存储自由变元（多解枚举自由变元可以使用）
 27 int free_num;//自由变元的个数
 28 
 29 //返回值为-1表示无解，为0是唯一解，否则返回自由变元个数
 30 int Gauss()
 31 {
 32     int max_r,col,k;
 33     free_num = 0;
 34     for(k = 0, col = 0 ; k < equ && col < var ; k++, col++)
 35     {
 36         max_r = k;
 37         for(int i = k+1;i < equ;i++)
 38         {
 39             if(abs(a[i][col]) > abs(a[max_r][col]))
 40                 max_r = i;
 41         }
 42         if(a[max_r][col] == 0)
 43         {
 44             k--;
 45             free_x[free_num++] = col;//这个是自由变元
 46             continue;
 47         }
 48         if(max_r != k)
 49         {
 50             for(int j = col; j < var+1; j++)
 51                 swap(a[k][j],a[max_r][j]);
 52         }
 53         for(int i = k+1;i < equ;i++)
 54         {
 55             if(a[i][col] != 0)
 56             {
 57                 for(int j = col;j < var+1;j++)
 58                     a[i][j] ^= a[k][j];
 59             }
 60         }
 61     }
 62     for(int i = k;i < equ;i++)
 63         if(a[i][col] != 0)
 64             return -1;//无解
 65     if(k < var) return var-k;//自由变元个数
 66     //唯一解，回代
 67     for(int i = var-1; i >= 0;i--)
 68     {
 69         x[i] = a[i][var];
 70         for(int j = i+1;j < var;j++)
 71             x[i] ^= (a[i][j] && x[j]);
 72     }
 73     return 0;
 74 }
 75 void init()
 76 {
 77     memset(a,0,sizeof(a));
 78     memset(x,0,sizeof(x));
 79 }
 80 int start[MAXN],end[MAXN];
 81 
 82 int main()
 83 {
 84     //freopen("in.txt","r",stdin);
 85     //freopen("out.txt","w",stdout);
 86     int n;
 87     int T;
 88     scanf("%d",&T);
 89     while(T--)
 90     {
 91         scanf("%d",&n);
 92         for(int i = 0;i < n;i++)
 93             scanf("%d",&start[i]);
 94         for(int i = 0;i < n;i++)
 95             scanf("%d",&end[i]);
 96         init();
 97         equ = var = n;
 98         for(int i = 0;i < n;i++)
 99             a[i][i] = 1;
100         int u,v;
101         while(scanf("%d%d",&u,&v) == 2)
102         {
103             if(u == 0 && v == 0)break;
104             a[v-1][u-1] = 1;
105         }
106         for(int i = 0;i < n;i++)
107             a[i][n] = (start[i]^end[i]);
108         int ans = Gauss();
109         if(ans == -1)
110             printf("Oh,it's impossible~!!
");
111         else printf("%d
",(1<<ans));
112     }
113     return 0;
114 }

View Code

POJ 1681 Painter's Problem

需要步数最少的，要枚举自由变元求解。

  1 /* ***********************************************
  2 Author        :kuangbin
  3 Created Time  :2013/8/17 19:56:07
  4 File Name     :F:2013ACM练习专题学习高斯消元POJ1681.cpp
  5 ************************************************ */
  6 
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <queue>
 13 #include <set>
 14 #include <map>
 15 #include <string>
 16 #include <math.h>
 17 #include <stdlib.h>
 18 #include <time.h>
 19 using namespace std;
 20 //对2取模的01方程组
 21 const int MAXN = 300;
 22 //有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var
 23 int equ,var;
 24 int a[MAXN][MAXN]; //增广矩阵
 25 int x[MAXN]; //解集
 26 int free_x[MAXN];//用来存储自由变元（多解枚举自由变元可以使用）
 27 int free_num;//自由变元的个数
 28 
 29 //返回值为-1表示无解，为0是唯一解，否则返回自由变元个数
 30 int Gauss()
 31 {
 32     int max_r,col,k;
 33     free_num = 0;
 34     for(k = 0, col = 0 ; k < equ && col < var ; k++, col++)
 35     {
 36         max_r = k;
 37         for(int i = k+1;i < equ;i++)
 38         {
 39             if(abs(a[i][col]) > abs(a[max_r][col]))
 40                 max_r = i;
 41         }
 42         if(a[max_r][col] == 0)
 43         {
 44             k--;
 45             free_x[free_num++] = col;//这个是自由变元
 46             continue;
 47         }
 48         if(max_r != k)
 49         {
 50             for(int j = col; j < var+1; j++)
 51                 swap(a[k][j],a[max_r][j]);
 52         }
 53         for(int i = k+1;i < equ;i++)
 54         {
 55             if(a[i][col] != 0)
 56             {
 57                 for(int j = col;j < var+1;j++)
 58                     a[i][j] ^= a[k][j];
 59             }
 60         }
 61     }
 62     for(int i = k;i < equ;i++)
 63         if(a[i][col] != 0)
 64             return -1;//无解
 65     if(k < var) return var-k;//自由变元个数
 66     //唯一解，回代
 67     for(int i = var-1; i >= 0;i--)
 68     {
 69         x[i] = a[i][var];
 70         for(int j = i+1;j < var;j++)
 71             x[i] ^= (a[i][j] && x[j]);
 72     }
 73     return 0;
 74 }
 75 int n;
 76 void init()
 77 {
 78     memset(a,0,sizeof(a));
 79     memset(x,0,sizeof(x));
 80     equ = n*n;
 81     var = n*n;
 82     for(int i = 0;i < n;i++)
 83         for(int j = 0;j < n;j++)
 84         {
 85             int t = i*n+j;
 86             a[t][t] = 1;
 87             if(i > 0)a[(i-1)*n+j][t] = 1;
 88             if(i < n-1)a[(i+1)*n+j][t] = 1;
 89             if(j > 0)a[i*n+j-1][t] = 1;
 90             if(j < n-1)a[i*n+j+1][t] = 1;
 91         }
 92 }
 93 void solve()
 94 {
 95     int t = Gauss();
 96     if(t == -1)
 97     {
 98         printf("inf
");
 99         return;
100     }
101     else if(t == 0)
102     {
103         int ans = 0;
104         for(int i = 0;i < n*n;i++)
105             ans += x[i];
106         printf("%d
",ans);
107         return;
108     }
109     else
110     {
111         //枚举自由变元
112         int ans = 0x3f3f3f3f;
113         int tot = (1<<t);
114         for(int i = 0;i < tot;i++)
115         {
116             int cnt = 0;
117             for(int j = 0;j < t;j++)
118             {
119                 if(i&(1<<j))
120                 {
121                     x[free_x[j]] = 1;
122                     cnt++;
123                 }
124                 else x[free_x[j]] = 0;
125             }
126             for(int j = var-t-1;j >= 0;j--)
127             {
128                 int idx;
129                 for(idx = j;idx < var;idx++)
130                     if(a[j][idx])
131                         break;
132                 x[idx] = a[j][var];
133                 for(int l = idx+1;l < var;l++)
134                     if(a[j][l])
135                         x[idx] ^= x[l];
136                 cnt += x[idx];
137             }
138             ans = min(ans,cnt);
139         }
140         printf("%d
",ans);
141     }
142 }
143 char str[30][30];
144 int main()
145 {
146     //freopen("in.txt","r",stdin);
147     //freopen("out.txt","w",stdout);
148     int T;
149     scanf("%d",&T);
150     while(T--)
151     {
152         scanf("%d",&n);
153         init();
154         for(int i = 0;i < n;i++)
155         {
156             scanf("%s",str[i]);
157             for(int j = 0;j < n;j++)
158             {
159                 if(str[i][j] == 'y')
160                     a[i*n+j][n*n] = 0;
161                 else a[i*n+j][n*n] = 1;
162             }
163         }
164         solve();
165     }
166     return 0;
167 }

View Code

POJ 1753 Flip Game

数据范围很小，随便搞，也是要枚举自由变元。。。。这题用高斯消元真是杀鸡用牛刀了

  1 /* ***********************************************
  2 Author        :kuangbin
  3 Created Time  :2013/8/17 20:53:13
  4 File Name     :F:2013ACM练习专题学习高斯消元POJ1753.cpp
  5 ************************************************ */
  6 
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <queue>
 13 #include <set>
 14 #include <map>
 15 #include <string>
 16 #include <math.h>
 17 #include <stdlib.h>
 18 #include <time.h>
 19 using namespace std;
 20 //对2取模的01方程组
 21 const int MAXN = 300;
 22 //有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var
 23 int equ,var;
 24 int a[MAXN][MAXN]; //增广矩阵
 25 int x[MAXN]; //解集
 26 int free_x[MAXN];//用来存储自由变元（多解枚举自由变元可以使用）
 27 int free_num;//自由变元的个数
 28 
 29 //返回值为-1表示无解，为0是唯一解，否则返回自由变元个数
 30 int Gauss()
 31 {
 32     int max_r,col,k;
 33     free_num = 0;
 34     for(k = 0, col = 0 ; k < equ && col < var ; k++, col++)
 35     {
 36         max_r = k;
 37         for(int i = k+1;i < equ;i++)
 38         {
 39             if(abs(a[i][col]) > abs(a[max_r][col]))
 40                 max_r = i;
 41         }
 42         if(a[max_r][col] == 0)
 43         {
 44             k--;
 45             free_x[free_num++] = col;//这个是自由变元
 46             continue;
 47         }
 48         if(max_r != k)
 49         {
 50             for(int j = col; j < var+1; j++)
 51                 swap(a[k][j],a[max_r][j]);
 52         }
 53         for(int i = k+1;i < equ;i++)
 54         {
 55             if(a[i][col] != 0)
 56             {
 57                 for(int j = col;j < var+1;j++)
 58                     a[i][j] ^= a[k][j];
 59             }
 60         }
 61     }
 62     for(int i = k;i < equ;i++)
 63         if(a[i][col] != 0)
 64             return -1;//无解
 65     if(k < var) return var-k;//自由变元个数
 66     //唯一解，回代
 67     for(int i = var-1; i >= 0;i--)
 68     {
 69         x[i] = a[i][var];
 70         for(int j = i+1;j < var;j++)
 71             x[i] ^= (a[i][j] && x[j]);
 72     }
 73     return 0;
 74 }
 75 int n;
 76 void init()
 77 {
 78     memset(a,0,sizeof(a));
 79     memset(x,0,sizeof(x));
 80     equ = n*n;
 81     var = n*n;
 82     for(int i = 0;i < n;i++)
 83         for(int j = 0;j < n;j++)
 84         {
 85             int t = i*n+j;
 86             a[t][t] = 1;
 87             if(i > 0)a[(i-1)*n+j][t] = 1;
 88             if(i < n-1)a[(i+1)*n+j][t] = 1;
 89             if(j > 0)a[i*n+j-1][t] = 1;
 90             if(j < n-1)a[i*n+j+1][t] = 1;
 91         }
 92 }
 93 const int INF = 0x3f3f3f3f;
 94 int solve()
 95 {
 96     int t = Gauss();
 97     if(t == -1)
 98     {
 99         return INF;
100     }
101     else if(t == 0)
102     {
103         int ans = 0;
104         for(int i = 0;i < n*n;i++)
105             ans += x[i];
106         return ans;
107     }
108     else
109     {
110         //枚举自由变元
111         int ans = INF;
112         int tot = (1<<t);
113         for(int i = 0;i < tot;i++)
114         {
115             int cnt = 0;
116             for(int j = 0;j < t;j++)
117             {
118                 if(i&(1<<j))
119                 {
120                     x[free_x[j]] = 1;
121                     cnt++;
122                 }
123                 else x[free_x[j]] = 0;
124             }
125             for(int j = var-t-1;j >= 0;j--)
126             {
127                 int idx;
128                 for(idx = j;idx < var;idx++)
129                     if(a[j][idx])
130                         break;
131                 x[idx] = a[j][var];
132                 for(int l = idx+1;l < var;l++)
133                     if(a[j][l])
134                         x[idx] ^= x[l];
135                 cnt += x[idx];
136             }
137             ans = min(ans,cnt);
138         }
139         return ans;
140     }
141 }
142 char str[10][10];
143 int main()
144 {
145     //freopen("in.txt","r",stdin);
146     //freopen("out.txt","w",stdout);
147     n = 4;
148     for(int i = 0;i < 4;i++)
149         scanf("%s",str[i]);
150     init();
151     for(int i = 0;i < 4;i++)
152         for(int j = 0;j < 4;j++)
153         {
154             if(str[i][j] == 'b')a[i*4+j][16] = 0;
155             else a[i*4+j][16] = 1;
156         }
157     int ans1 = solve();
158     init();
159     for(int i = 0;i < 4;i++)
160         for(int j = 0;j < 4;j++)
161         {
162             if(str[i][j] == 'b')a[i*4+j][16] = 1;
163             else a[i*4+j][16] = 0;
164         }
165     int ans2 = solve();
166     if(ans1 == INF && ans2 == INF)
167         printf("Impossible
");
168     else printf("%d
",min(ans1,ans2));
169     return 0;
170 }

View Code

POJ 3185 The Water Bowls

一维的了，更简单的还是枚举比较好。

高斯消元随便搞

  1 /* ***********************************************
  2 Author        :kuangbin
  3 Created Time  :2013/8/17 21:53:09
  4 File Name     :F:2013ACM练习专题学习高斯消元POJ3185.cpp
  5 ************************************************ */
  6 
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <queue>
 13 #include <set>
 14 #include <map>
 15 #include <string>
 16 #include <math.h>
 17 #include <stdlib.h>
 18 #include <time.h>
 19 using namespace std;
 20 //对2取模的01方程组
 21 const int MAXN = 300;
 22 //有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var
 23 int equ,var;
 24 int a[MAXN][MAXN]; //增广矩阵
 25 int x[MAXN]; //解集
 26 int free_x[MAXN];//用来存储自由变元（多解枚举自由变元可以使用）
 27 int free_num;//自由变元的个数
 28 
 29 //返回值为-1表示无解，为0是唯一解，否则返回自由变元个数
 30 int Gauss()
 31 {
 32     int max_r,col,k;
 33     free_num = 0;
 34     for(k = 0, col = 0 ; k < equ && col < var ; k++, col++)
 35     {
 36         max_r = k;
 37         for(int i = k+1;i < equ;i++)
 38         {
 39             if(abs(a[i][col]) > abs(a[max_r][col]))
 40                 max_r = i;
 41         }
 42         if(a[max_r][col] == 0)
 43         {
 44             k--;
 45             free_x[free_num++] = col;//这个是自由变元
 46             continue;
 47         }
 48         if(max_r != k)
 49         {
 50             for(int j = col; j < var+1; j++)
 51                 swap(a[k][j],a[max_r][j]);
 52         }
 53         for(int i = k+1;i < equ;i++)
 54         {
 55             if(a[i][col] != 0)
 56             {
 57                 for(int j = col;j < var+1;j++)
 58                     a[i][j] ^= a[k][j];
 59             }
 60         }
 61     }
 62     for(int i = k;i < equ;i++)
 63         if(a[i][col] != 0)
 64             return -1;//无解
 65     if(k < var) return var-k;//自由变元个数
 66     //唯一解，回代
 67     for(int i = var-1; i >= 0;i--)
 68     {
 69         x[i] = a[i][var];
 70         for(int j = i+1;j < var;j++)
 71             x[i] ^= (a[i][j] && x[j]);
 72     }
 73     return 0;
 74 }
 75 void init()
 76 {
 77     memset(a,0,sizeof(a));
 78     memset(x,0,sizeof(x));
 79     equ = 20;
 80     var = 20;
 81     for(int i = 0;i < 20;i++)
 82     {
 83         a[i][i] = 1;
 84         if(i > 0) a[i-1][i] = 1;
 85         if(i < 19)a[i+1][i] = 1;
 86     }
 87 }
 88 void solve()
 89 {
 90     int t = Gauss();
 91     if(t == -1)
 92     {
 93         printf("inf
");
 94         return;
 95     }
 96     else if(t == 0)
 97     {
 98         int ans = 0;
 99         for(int i = 0;i < 20;i++)
100             ans += x[i];
101         printf("%d
",ans);
102         return;
103     }
104     else
105     {
106         //枚举自由变元
107         int ans = 0x3f3f3f3f;
108         int tot = (1<<t);
109         for(int i = 0;i < tot;i++)
110         {
111             int cnt = 0;
112             for(int j = 0;j < t;j++)
113             {
114                 if(i&(1<<j))
115                 {
116                     x[free_x[j]] = 1;
117                     cnt++;
118                 }
119                 else x[free_x[j]] = 0;
120             }
121             for(int j = var-t-1;j >= 0;j--)
122             {
123                 int idx;
124                 for(idx = j;idx < var;idx++)
125                     if(a[j][idx])
126                         break;
127                 x[idx] = a[j][var];
128                 for(int l = idx+1;l < var;l++)
129                     if(a[j][l])
130                         x[idx] ^= x[l];
131                 cnt += x[idx];
132             }
133             ans = min(ans,cnt);
134         }
135         printf("%d
",ans);
136     }
137 }
138 
139 int main()
140 {
141     //freopen("in.txt","r",stdin);
142     //freopen("out.txt","w",stdout);
143     init();
144     for(int i = 0;i < 20;i++)
145         scanf("%d",&a[i][20]);
146     solve();
147     return 0;
148 }

View Code

专题：

高斯消元解方程：

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=29538#overview