高斯消元 POJ 1222 POJ 1681（枚举自由变元）POJ 1753（两次高斯消元） POJ 1830 HDU 5833 （高斯消元，素数分解）POJ 3158 （集合压缩枚举自由变元）

2024-02-07 17:32
文章标签 压缩 集合 poj 枚举 自由 hdu 分解 素数 两次 高斯消 1753 1222 5833 1830 变元 1681 3158

本文主要是介绍高斯消元 POJ 1222 POJ 1681（枚举自由变元）POJ 1753（两次高斯消元） POJ 1830 HDU 5833 （高斯消元，素数分解）POJ 3158 （集合压缩枚举自由变元），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

高斯消元 POJ 1222 POJ 1681（枚举自由变元）POJ 1753（两次高斯消元） POJ 1830 HDU 5833 （高斯消元，素数分解）POJ 3158 （集合压缩枚举自由变元） POJ 2947（非01矩阵，求同模方程组的解）


http://www.cppblog.com/menjitianya/archive/2014/06/08/207226.html


http://blog.csdn.net/mishifangxiangdefeng/article/details/7191074


http://blog.sina.com.cn/s/blog_afe6bb330101a59d.html



POJ 1222

题目链接：http://poj.org/problem?id=1222


题意：一个01矩阵，表示灯的亮灭状态，每次操作可以反转上下左右和其本身的状态，问怎样将所有灯熄灭，输出反转方式。

第一次写高斯消元，用了模板，构造的过程比较丑陋....

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
const int MAXN=35;
int a[MAXN][MAXN];//增广矩阵
int x[MAXN];//解集int Gauss(int equ,int var) {int i,j,k;int max_r;// 当前这列绝对值最大的行.int col;//当前处理的列int temp;for(int i=0;i<=var;i++) {x[i]=0;}col=0;for(k = 0;k < equ && col < var;k++,col++) {max_r=k;for(i=k+1;i<equ;i++) {if(abs(a[i][col])>abs(a[max_r][col])) max_r=i;}if(max_r!=k) {for(j=k;j<var+1;j++) swap(a[k][j],a[max_r][j]);}if(a[k][col]==0) {k--;continue;}for(i=k+1;i<equ;i++) {if(a[i][col]!=0) {for(j=col;j<var+1;j++) {a[i][j] = a[i][j]^a[k][j];}}}}for (i = var - 1; i >= 0; i--) {temp = a[i][var];for (j = i + 1; j < var; j++) {if (a[i][j] != 0) temp ^= a[i][j] * x[j];}x[i] = temp;}return 0;
}
int dx[5] = {1, -1, 0, 0, 0};
int dy[5] = {0, 0, 0, -1, 1};
int main() {//freopen("out1.txt", "w", stdout);int t;scanf("%d", &t);int in[10][10];int flip[10][10];int i, j, k, l;int kase = 1;while(t--) {for(i = 0; i < 5; i++) {for(j = 0; j < 6; j++) {scanf("%d", &in[i][j]);}}int cnt = 0;//将开每个开关的影响范围矩阵转化成一个30 * 1的列矩阵//这样30个列矩阵组成一个30 * 30的矩阵，然后接上目标矩阵成为扩展矩阵 for(i = 0; i < 5; i++) {for(j = 0; j < 6; j++) {memset(flip, 0, sizeof(flip));for(int d = 0; d < 5; d++) {int tx = i + dx[d];int ty = j + dy[d];if(tx >= 0 && tx < 5 && ty >= 0 && ty < 6) {flip[tx][ty] = 1;}}for(int i = 0; i < 5; i++) {for(int j = 0; j < 6; j++) {a[i * 6 + j][cnt] = flip[i][j];}}cnt++;}}for(i = 0; i < 5; i++) {for(j = 0; j < 6; j++) {a[i * 6 + j][cnt] = in[i][j];}}//矩阵构造完成，解即可。 Gauss(30, 30);printf("PUZZLE #%d\n", kase++);for(i = 0; i < 30; i++) {printf("%d", x[i]);if(i % 6 == 5) printf("\n");else printf(" ");}}return 0;
}


POJ 1681

题目链接：http://poj.org/problem?id=1681


题意：一个n*n 的木板 ，每个格子 都 可以 染成 白色和黄色，（ 一旦我们对也个格子染色 ，他的上下左右 都将改变颜色）；

给定一个初始状态 ， 求将 所有的 格子 染成黄色 最少需要染几次？  若 不能 染成 输出 inf。

参考博客：http://www.cnblogs.com/kuangbin/archive/2012/08/31/2665913.html

也就是比较裸的开关灯问题，本来就对自由变元的枚举感到疑惑，看了聚聚的博客恍然大悟。本题若是不枚举自由变元直接判断无解有解也是可以过的，可能是因为并没有出现有多解的情况，但是显然这样的做法是不正确的。在每次解完矩阵后还应该枚举自由变元从而得到最小值才是正确的做法。具体见代码：


#include <iostream> 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 300;int a[MAXN][MAXN]; //矩阵 
int x[MAXN]; //解 
int n; //初始矩阵大小 
int free_x[MAXN]; //自由变元的下标 
int free_num; //自由变元个数 int gauss(int equ, int var) {int i, j, k;int max_r;int col;int temp;free_num = 0;for(i = 0; i < var + 1; i++) {x[i] = 0;free_x[i] = 0;}col = 0;for(k = 0; k < equ && col < var; k++, col++) {max_r = k;for(i = k + 1; i < equ; i++) {if(abs(a[i][col]) > abs(a[max_r][col])) max_r = i;}if(max_r != k) {for(j = k; j < var + 1; j++) swap(a[k][j], a[max_r][j]);}if(a[k][col] == 0) {k--;free_x[free_num++] = col; //记录自由变元下标 continue;}for(i = k + 1; i < equ; i++) {if(a[i][col] != 0) {for(j = col; j < var + 1; j++) {a[i][j] ^= a[k][j];}}}}for(i = k; i < equ; i++) {  //无解 if(a[i][col] != 0) return -1;}int res = INF;for(i = 0; i < 1 << (var - k); i++) {  //枚举自由变元的集合 int cnt = 0;	//本次非零解个数 int S = i; //本次集合 for(j = 0; j < var - k; j++) {x[free_x[j]] = (S >> j & 1); //看该自由变元是否在S集合中，即确定该自由变元是0还是1 if(x[free_x[j]]) cnt++;}for(j = k - 1; j >= 0; j--) {  //已知自由变元个数求解剩余的解 x[j] = a[j][var];for(int l = j + 1; l < var; l++) {if(a[j][l]) x[j] ^= x[l];}if(x[j]) cnt++;}if(cnt < res) res = cnt;  //求解最小值 }return res;
}
void init() {memset(a, 0, sizeof(a));memset(x, 0, sizeof(x));memset(free_x, 0, sizeof(free_x));int i, j;for(i = 0; i < n; i++) {for(j = 0; j < n; j++) {int t = i * n + j;a[t][t] = 1;if(i > 0) a[(i - 1) * n + j][t] = 1;if(i < n - 1) a[(i + 1) * n + j][t] = 1;if(j > 0) a[i * n + j - 1][t] = 1;if(j < n - 1) a[i * n + j + 1][t] = 1;}}
}
int main(void)
{//freopen("in.txt", "r", stdin);//freopen("out.txt","w",stdout);int t;scanf("%d", &t);char str[20];while(t--) {scanf("%d", &n);init();int i, j;for(i = 0; i < n; i++) {scanf("%s", str);for(j = 0; j < n; j++) {if(str[j] == 'y') a[i * n + j][n * n] = 0;else a[i * n + j][n * n] = 1;}}int res = gauss(n * n, n * n);if(res < 0) puts("inf");else printf("%d\n", res);}return 0;
}


POJ 1753 Flip Game

题目链接：http://poj.org/problem?id=1753


题意：有4*4的正方形，每个格子要么是黑色，要么是白色，当把一个格子的颜色改变(黑->白或者白->黑)时，其周围上下左右(如果存在的话)的格子的颜色也被反转，问至少反转几个格子可以使4*4的正方形变为纯白或者纯黑？


两次高斯消元后求最小结果，两个结果再去最小值即可。注意判断无解的情况。

由于棋盘较小，用搜索也可以过。

#include <iostream> 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 300;int a[MAXN][MAXN]; //矩阵 
int x[MAXN]; //解 
int n = 4; //初始矩阵大小 
int free_x[MAXN]; //自由变元的下标 
int free_num; //自由变元个数 int gauss(int equ, int var) {int i, j, k;int max_r;int col;int temp;free_num = 0;for(i = 0; i < var + 1; i++) {x[i] = 0;free_x[i] = 0;}col = 0;for(k = 0; k < equ && col < var; k++, col++) {max_r = k;for(i = k + 1; i < equ; i++) {if(abs(a[i][col]) > abs(a[max_r][col])) max_r = i;}if(max_r != k) {for(j = k; j < var + 1; j++) swap(a[k][j], a[max_r][j]);}if(a[k][col] == 0) {k--;free_x[free_num++] = col; //记录自由变元下标 continue;}for(i = k + 1; i < equ; i++) {if(a[i][col] != 0) {for(j = col; j < var + 1; j++) {a[i][j] ^= a[k][j];}}}}for(i = k; i < equ; i++) {  //无解 if(a[i][col] != 0) return INF;}int res = INF;for(i = 0; i < 1 << (var - k); i++) {  //枚举自由变元的集合 int cnt = 0;	//本次非零解个数 int S = i; //本次集合 for(j = 0; j < var - k; j++) {x[free_x[j]] = (S >> j & 1); //看该自由变元是否在S集合中，即确定该自由变元是0还是1 if(x[free_x[j]]) cnt++;}for(j = k - 1; j >= 0; j--) {  //已知自由变元个数求解剩余的解 x[j] = a[j][var];for(int l = j + 1; l < var; l++) {if(a[j][l]) x[j] ^= x[l];}if(x[j]) cnt++;}if(cnt < res) res = cnt;  //求解最小值 }return res;
}
void init() {memset(a, 0, sizeof(a));memset(x, 0, sizeof(x));memset(free_x, 0, sizeof(free_x));int i, j;for(i = 0; i < n; i++) {for(j = 0; j < n; j++) {int t = i * n + j;a[t][t] = 1;if(i > 0) a[(i - 1) * n + j][t] = 1;if(i < n - 1) a[(i + 1) * n + j][t] = 1;if(j > 0) a[i * n + j - 1][t] = 1;if(j < n - 1) a[i * n + j + 1][t] = 1;}}
}
int main(void) {//freopen("in.txt", "r", stdin);//freopen("out.txt","w",stdout);char str[20][20];init();int i, j;for(i = 0; i < n; i++) {scanf("%s", str[i]);for(j = 0; j < n; j++) {if(str[i][j] == 'w') a[i * n + j][n * n] = 0;else a[i * n + j][n * n] = 1;}}int res1 = gauss(n * n, n * n);init();for(i = 0; i < n; i++) {for(j = 0; j < n; j++) {if(str[i][j] == 'w') a[i * n + j][n * n] = 1;else a[i * n + j][n * n] = 0;}}int res2 = gauss(n * n, n * n);int res = res1 < res2 ? res1 : res2;if(res == INF) puts("Impossible");else printf("%d\n", res);return 0;
}


POJ 1830

题目链接：http://poj.org/problem?id=1830


题意：中文题就不说了。注意那个联系是单向的啊。。。WA了一发


#include <iostream> 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 300;int a[MAXN][MAXN]; //矩阵 
int n = 4; //初始矩阵大小 
int free_x[MAXN]; //自由变元的下标 
int free_num; //自由变元个数 int gauss(int equ, int var) {int i, j, k;int max_r;int col;int temp;free_num = 0;for(i = 0; i < var + 1; i++) {free_x[i] = 0;}col = 0;for(k = 0; k < equ && col < var; k++, col++) {max_r = k;for(i = k + 1; i < equ; i++) {if(abs(a[i][col]) > abs(a[max_r][col])) max_r = i;}if(max_r != k) {for(j = k; j < var + 1; j++) swap(a[k][j], a[max_r][j]);}if(a[k][col] == 0) {k--;continue;}for(i = k + 1; i < equ; i++) {if(a[i][col] != 0) {for(j = col; j < var + 1; j++) {a[i][j] ^= a[k][j];}}}}for(i = k; i < equ; i++) {  //无解 if(a[i][col] != 0) return -1;}return 1 << (var - k);
}
int main() {int k;scanf("%d", &k);int in1[35], in2[35];while(k--) {scanf("%d", &n);int i, j;memset(a, 0, sizeof(a));for(i = 0; i < n; i++) {scanf("%d", in1 + i);}for(i = 0; i < n; i++) {scanf("%d", in2 + i);a[i][n] = in1[i] ^ in2[i];}int x, y;vector<int> link[35];while(scanf("%d %d", &x, &y), x + y) {link[x - 1].push_back(y - 1);}for(i = 0; i < n; i++) {for(j = 0; j < n; j++) {if(i == j) a[j][i] = 1;else {for(int l = 0; l < link[i].size(); l++) {a[link[i][l]][i] = 1;}}}}int ans = gauss(n, n);if(ans < 0) puts("Oh,it's impossible~!!");else printf("%d\n", ans);}return 0;
}


HDU 5833

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5833


题意：n个数，选择其中任意个，不能不选，使这些数的乘积为完全平方数。问有多少种选法。


貌似有类似的题目。但是死活也想不起来是用高斯消元做啊。。。。不过队友却一个人搞出来了。。。。%%%%%


将每个数拆开成素因数相乘的形式，然后将每个素因子记录一下，奇数个为1， 偶数个为0，形成一个303的列矩阵，将n个列矩阵组合成一个303*n的系数矩阵。然后结果矩阵全为0。

为什么能这么构造呢？因为只要每个素因子是偶数个，那么一定是完全平方数，因此只需要想办法把每个奇数个的素因子都组合成偶数个即可。


#include <iostream> 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 500;bool a[MAXN][MAXN]; //系数矩阵
int n; //变元 
int isp[2005];void prime() {  // 求出2000以内所有的素数，并将其编号为第几个素数 int i, j, cnt = 1;for(i = 0; i <= 2000; i++) isp[i] = 1;isp[0] = isp[1] = 0;for(i = 2; i <= 2000; i++) {if(isp[i] == 1) {isp[i] = cnt++;for(j = i + i; j <= 2000; j += i) {isp[j] = 0;}}}
}int qpow(ll x, int n, int mod) {  //不用ll会WA ll res = 1;while(n) {if(n & 1) res = (res * x) % mod;x = (x * x) % mod;n >>= 1;}return res;
}
int gauss(int equ, int var) {  //解矩阵 int i, j, k;int max_r;int col;int temp;col = 1;for(k = 1; k <= equ && col <= var; k++, col++) {max_r = k;for(i = k + 1; i <= equ; i++) {if(abs(a[i][col]) > abs(a[max_r][col])) max_r = i;}if(max_r != k) {for(j = k; j <= var + 1; j++) swap(a[k][j], a[max_r][j]);}if(a[k][col] == 0) {k--;continue;}for(i = k + 1; i <= equ; i++) {if(a[i][col] != 0) {for(j = col; j <= var + 1; j++) {a[i][j] ^= a[k][j];}}}}return (qpow(2, var - k + 1, 1000000007) - 1 + 1000000007) % 1000000007;
}
int main() {prime();int t;scanf("%d", &t);int kase = 1;while(t--) {printf("Case #%d:\n", kase++);scanf("%d", &n);ll i, j;ll tmp;memset(a, 0, sizeof(a));for(i = 1; i <= n; i++) {scanf("%I64d", &tmp);for(j = 2; j * j <= tmp; j++) {  //素因子分解 while(tmp % j == 0) {a[isp[j]][i] ^= 1;  //建立矩阵 tmp /= j;}}if(tmp != 1) a[isp[tmp]][i] ^= 1;}printf("%d\n", gauss(303, n));}return 0;
}


POJ 3185 The Water Bowls

题目链接：http://poj.org/problem?id=3185


题意：一个序列，一次反转会改变前后的值，问最少几次能全反转为0。


矩阵构造很简单，系数矩阵是有多解的，所以要枚举自由变元来确定最小值。


#include <iostream> 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 30;int a[MAXN][MAXN];
int x[MAXN];
int n;
int free_x[MAXN]; 
int free_num;int gauss(int equ, int var) {int i, j, k;int max_r;int col;int temp;free_num = 0;for(i = 0; i < var + 1; i++) {x[i] = 0;free_x[i] = 0;}col = 0;for(k = 0; k < equ && col < var; k++, col++) {max_r = k;for(i = k + 1; i < equ; i++) {if(abs(a[i][col]) > abs(a[max_r][col])) max_r = i;}if(max_r != k) {for(j = k; j < var + 1; j++) swap(a[k][j], a[max_r][j]);}if(a[k][col] == 0) {k--;free_x[free_num++] = col; //???????? continue;}for(i = k + 1; i < equ; i++) {if(a[i][col] != 0) {for(j = col; j < var + 1; j++) {a[i][j] ^= a[k][j];}}}}for(i = k; i < equ; i++) {if(a[i][col] != 0) return -1;}int res = INF;for(i = 0; i < 1 << (var - k); i++) {  //枚举自由变元 int cnt = 0;	int S = i; for(j = 0; j < var - k; j++) {x[free_x[j]] = (S >> j & 1);if(x[free_x[j]]) cnt++;}for(j = k - 1; j >= 0; j--) {x[j] = a[j][var];for(int l = j + 1; l < var; l++) {if(a[j][l]) x[j] ^= x[l];}if(x[j]) cnt++;}if(cnt < res) res = cnt;}return res;
}
void init() {memset(a, 0, sizeof(a));memset(x, 0, sizeof(x));memset(free_x, 0, sizeof(free_x));int i, j;for(i = 0; i < n; i++) {a[i][i] = 1;if(i > 0) a[i - 1][i] = 1;if(i < n - 1) a[i + 1][i] = 1;}
}
int main(void)
{int in[25];int i, j;n = 20;init();for(i = 0; i < 20; i++) {scanf("%d", in + i);a[i][n] = in[i];}printf("%d\n", gauss(n, n));return 0;
}


POJ 2947 Widget Factory

题目链接：http://poj.org/problem?id=2947


题意：

生产一些零件，已知有n种零件，m条记录，


记录只记录了某次生产从周几开始，周几结束，以及生产了哪些产品。


每件商品生产所需天数为3-9天。


求每样产品需要多少天才能完成。
【输入】


多组数据


每组数据第一行n,m


之后m行描述m条记录


其中MON TUE WED THU FRI SAT SUN分别表示周一到周日


每条记录第一个数x表示有x件产品，之后两个日期表示起始和结束时间


接下来一行x个数分别表示生产了哪些产品
输入以0 0结束


【输出】
对于每组数据，若有唯一解，则按产品编号顺序输出该解，若有多解，则输出'Multiple solutions.'，若无解则输出'Inconsistent data.'


第一次做这种高斯消元的题，同模的地方搞得不是太明白。   建立矩阵就是按照给定的条件建立，但是关于有唯一解时，得到的解一定能是整数吗？是整数的话，一定能满足题目条件吗？这里存在疑问，看来还是线性代数学得不够好。。。


关于详细对建立矩阵的分析可以看这里：http://www.tuicool.com/articles/2Q3Mbqm


#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
#include <map>
using namespace std;const int MAXN=400;
int n;int a[MAXN][MAXN];//增广矩阵
int x[MAXN];//解集
bool free_x[MAXN];//标记是否是不确定的变元/*
void Debug(void)
{int i, j;for (i = 0; i < equ; i++){for (j = 0; j < var + 1; j++){cout << a[i][j] << " ";}cout << endl;}cout << endl;
}
*/inline int gcd(int a,int b)
{int t;while(b!=0){t=b;b=a%b;a=t;}return a;
}
inline int lcm(int a,int b)
{return a/gcd(a,b)*b;//先除后乘防溢出
}// 高斯消元法解方程组(Gauss-Jordan elimination).(-2表示有浮点数解，但无整数解，
//-1表示无解，0表示唯一解，大于0表示无穷解，并返回自由变元的个数)
//有equ个方程，var个变元。增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var.
int Gauss(int equ,int var)  //模板，要修改成模7同余的 
{int i,j,k;int max_r;// 当前这列绝对值最大的行.int col;//当前处理的列int ta,tb;int LCM;int temp;int free_x_num;int free_index;for(int i=0;i<=var;i++){x[i]=0;free_x[i]=true;}//转换为阶梯阵.col=0; // 当前处理的列for(k = 0;k < equ && col < var;k++,col++){// 枚举当前处理的行.
// 找到该col列元素绝对值最大的那行与第k行交换.(为了在除法时减小误差)max_r=k;for(i=k+1;i<equ;i++){if(abs(a[i][col])>abs(a[max_r][col])) max_r=i;}if(max_r!=k){// 与第k行交换.for(j=k;j<var+1;j++) swap(a[k][j],a[max_r][j]);}if(a[k][col]==0){// 说明该col列第k行以下全是0了，则处理当前行的下一列.k--;continue;}for(i=k+1;i<equ;i++){// 枚举要删去的行.if(a[i][col]!=0){LCM = lcm(abs(a[i][col]),abs(a[k][col]));ta = LCM/abs(a[i][col]);tb = LCM/abs(a[k][col]);if(a[i][col]*a[k][col]<0)tb=-tb;//异号的情况是相加for(j=col;j<var+1;j++){a[i][j] = ((a[i][j]*ta-a[k][j]*tb)%7 + 7) % 7;}}}}//  Debug();// 1. 无解的情况: 化简的增广阵中存在(0, 0, ..., a)这样的行(a != 0).for (i = k; i < equ; i++){ // 对于无穷解来说，如果要判断哪些是自由变元，那么初等行变换中的交换就会影响，则要记录交换.if (a[i][col] != 0) return -1;}// 2. 无穷解的情况: 在var * (var + 1)的增广阵中出现(0, 0, ..., 0)这样的行，即说明没有形成严格的上三角阵.// 且出现的行数即为自由变元的个数.if (k < var){// 首先，自由变元有var - k个，即不确定的变元至少有var - k个.for (i = k - 1; i >= 0; i--){// 第i行一定不会是(0, 0, ..., 0)的情况，因为这样的行是在第k行到第equ行.// 同样，第i行一定不会是(0, 0, ..., a), a != 0的情况，这样的无解的.free_x_num = 0; // 用于判断该行中的不确定的变元的个数，如果超过1个，则无法求解，它们仍然为不确定的变元.for (j = 0; j < var; j++){if (a[i][j] != 0 && free_x[j]) free_x_num++, free_index = j;}if (free_x_num > 1) continue; // 无法求解出确定的变元.// 说明就只有一个不确定的变元free_index，那么可以求解出该变元，且该变元是确定的.temp = a[i][var];for (j = 0; j < var; j++){if (a[i][j] != 0 && j != free_index) temp = (temp - a[i][j] * x[j]%7 + 7) % 7;}x[free_index] = temp / a[i][free_index] % 7; // 求出该变元.free_x[free_index] = 0; // 该变元是确定的.}return var - k; // 自由变元有var - k个.}// 3. 唯一解的情况: 在var * (var + 1)的增广阵中形成严格的上三角阵.// 计算出Xn-1, Xn-2 ... X0.for (i = var - 1; i >= 0; i--){temp = a[i][var];for (j = i + 1; j < var; j++){if (a[i][j] != 0) temp = (temp - a[i][j] * x[j]%7 + 7) % 7;}while(temp % a[i][i] != 0) temp += 7; // 因为有取模，所以当没有整数解的时候加上7即可，这样一定可以求出整数解吗？存在疑问 x[i] = temp / a[i][i] % 7;}return 0;
}
map<string, int> ma;
void init() {ma["MON"] = 1;ma["TUE"] = 2;ma["WED"] = 3;ma["THU"] = 4;ma["FRI"] = 5;ma["SAT"] = 6;ma["SUN"] = 7;
}
int main() {init();int m;while(~scanf("%d %d", &n, &m), m + n) {memset(a, 0, sizeof(a));int k;string t1, t2;int i, j;for(i = 0; i < m; i++) {cin >> k >> t1 >> t2;int tmp;for(j = 0; j < k; j++) {scanf("%d", &tmp);a[i][tmp - 1]++;a[i][tmp - 1] %= 7;}a[i][n] = (ma[t2] - ma[t1] + 1 + 7) % 7;}int res = Gauss(m, n);if(res == -1) puts("Inconsistent data.");else if(res > 0) puts("Multiple solutions.");else {for(i = 0; i < n; i++) {if(x[i] <= 2) x[i] += 7;  //只要有唯一解就一定满足题目条件吗？存在疑问 }for(i = 0; i < n; i++) {printf("%d", x[i]);if(i != n - 1) printf(" ");else printf("\n");}}}return 0;
}


这篇关于高斯消元 POJ 1222 POJ 1681（枚举自由变元）POJ 1753（两次高斯消元） POJ 1830 HDU 5833 （高斯消元，素数分解）POJ 3158 （集合压缩枚举自由变元）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/688436。

相关文章

hdu1254（嵌套bfs，两次bfs）

hdu1254（嵌套bfs，两次bfs）

/*第一次做这种题感觉很有压力，思路还是有点混乱，总是wa，改了好多次才ac的思路：把箱子的移动当做第一层bfs，队列节点要用到当前箱子坐标（x，y），走的次数step，当前人的weizhi（man_x，man_y），要判断人能否将箱子推到某点时要嵌套第二层bfs（人的移动）；代码如下：
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
hdu1565（状态压缩）

hdu1565（状态压缩）

本人第一道ac的状态压缩dp，这题的数据非常水，很容易过 题意：在n*n的矩阵中选数字使得不存在任意两个数字相邻，求最大值 解题思路： 一、因为在1<<20中有很多状态是无效的，所以第一步是选择有效状态，存到cnt[]数组中 二、dp[i][j]表示到第i行的状态cnt[j]所能得到的最大值，状态转移方程dp[i][j] = max(dp[i][j],dp[i-1][k]) ,其中k满足c
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
hdu 2093 考试排名（sscanf）

hdu 2093 考试排名（sscanf）

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()"，有时候又没有。而它也不会给我们提示。 这种情况下，就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和
阅读更多...
hdu 2602 and poj 3624(01背包)

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s
阅读更多...
poj 1511 Invitation Cards(spfa最短路)

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离，求来回到点1的最短路中的边权和。 因为边很大，不能用原来的dijkstra什么的，所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码： #include<stdio.h>#include<stack>using namespace std;const int M
阅读更多...
poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259： 题意：John的农场里n块地，m条路连接两块地，w个虫洞，虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来，看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码： #include<stdio.h>const int MaxN = 501;//农场数const int
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2