暑期专题一 高斯消元法
一般来说，对于n个一次方程和n个未知数，可以通过高斯消元法来判断这个方程无解，有唯一解还是有多解。对于一个有唯一解的方程，我们可以通过程序实现加减消元和代入消元，以此来求得这个方程的解。
先贴一个解普通方程的模板：
void Gauss(int m, int n) { int i = 0, j = 0; for (; i < m && j < n; i++, j++) { int mx = i; for (int k = i + 1; k < m; k++) if (fabs(a[k][j]) > fabs(a[mx][j])) mx = k; if (fabs(a[mx][i]) < eps) {i--; continue;} if (mx ^ i) swap(a[mx], a[i]); for (int k = 1; k < m; k++) if (k ^ i) { double tmp = a[j][i] / a[i][i]; for (int l = j; l <= n; l++) a[k][l] -= tmp * a[k][l]; } } }
1. [JSOI2008 Round1] 球形空间产生器
问题描述
火星人不能忍受地球人对他们的歧视，终于发明了一种非常强大的武器：球形空间产生器。球形空间产生器能产生一个N维球体屏障，而且这个屏障是坚不可摧的，被困在球体内的地球人就被切断了与外界的联系。Js08现在就被困在了屏障中，情况十分危急，必须尽快找出并摧毁球形空间产生器。Js08经过摸索和碰壁，给出了球体上N+1个点的坐标，希望你能够帮Js08找出球形空间产生器的位置——它总是位于球形空间的球心。
输入格式
第一行为整数N，代表了空间的维度。
接下来N+1行，每行N个实数代表一个坐标。输入数据精确到小数点后6位。
输入数据保证输出结果唯一。
输出格式
输出一行N个实数，代表球心的坐标，精确到小数点后三位。相邻的数字之间用一个空格分开（行末无空格）。
数据规模：对于40%的数据，1<=n<=3
对于100%的数据，1<=n<=10 思路：这个题其实就是一个高斯消元的板题。为什么呢？我们来看题。 首先，假设这个球心为 (X1, X2, X3, X4, ... , Xn) ，第i个球的坐标为(Xi1, Xi2, Xi3, Xi4, ... , Xin) 可知：对于第i个球，设有di ^ 2 = (Xi1 - X1) ^ 2 + (Xi2 - X2) ^ 2 + .. + (Xin - Xn) ^ 2，那么显然d1 = d2 = d3 = ... = dn 但是高斯消元只能解决一次方程，怎么办呢？我们发现对于每一个方程的两边，都必然含有X1 ^ 2,X2 ^ 2, ... , Xn ^ 2，于是可以消去。 这样方程就只剩下常数项和一次项，可以用高斯消元法解决。
#includeusing namespace std; typedef double db; const db eps = 1e-8; db a[15][15]; void Gauss(int n) { for (int i = 0; i < n; i++) { int mx = i; for (int j = i + 1; j < n; j++) if (fabs(a[mx][i]) < fabs(a[j][i])) mx = j; if (fabs(a[mx][i]) < eps) continue; for (int j = 0; j <= n; j++) swap(a[i][j], a[mx][j]); for (int j = 0; j < n; j++) { if (i ^ j) { db tmp = a[j][i] / a[i][i]; for (int k = i + 1; k <= n; k++) a[j][k] -= a[i][k] * tmp; } } } for (int i = 0; i < n - 1; i++) printf("%.3lf ", a[i][n] / a[i][i]); } int main() { int n; scanf("%d", &n); ++n; for (int i = 0; i < n; i++) for (int j = 0; j < n - 1; j++) { scanf("%lf", &a[i][j]), a[i][n] -= a[i][j] * a[i][j], a[i][j] *= -2.0; a[i][n - 1] = 1.0; } Gauss(n); }
2.NKOJ1986 开关问题
问题描述
有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关，最多只能进行一次开关操作。你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）
输入格式
输入第一行有一个数K，表示以下有K组测试数据。
每组测试数据的格式如下：
第一行 一个数N（0 < N < 29）
第二行 N个0或者1的数，表示开始时N个开关状态。
第三行 N个0或者1的数，表示操作结束后N个开关的状态。
接下来 每行两个数I J，表示如果操作第 I 个开关，第J个开关的状态也会变化。每组数据以 0 0 结束。
输出格式
如果有可行方法，输出总数，否则输出“Oh,it's impossible~!!” 不包括引号。
思路：非常经典的高斯消元解异或方程组。和普通的高斯消元其实类似，只是状态和未知数都变成了0和1。
贴个异或方程组的模板（其实还可以用bitset优化）
int Gauss(int n) { int ans = 1; for (int i = 0; i < n; i++) { int mx = i; if (!a[mx][i]) { for (int j = i + 1; j < n; j++) if (a[mx][j]) { mx = j; break; } } if (!a[mx][i]) continue; swap(a[i], a[mx]); for (int j = 0; j < n; j++) { if ((i ^ j) && a[j][i]) { for (int k = i + 1; k <= n; k++) a[j][k] ^= a[i][k]; } } } for (int i = n - 1; ~i; i--) { if (a[i][i] == 0 && a[i][n]) return 0; else if (a[i][i] == 0) ans <<= 1; else for (int j = i - 1; ~j; j--) { if (a[j][i]) a[j][i] ^= a[i][i], a[j][n] ^= a[i][n]; } } return ans; }
3.手机游戏
问题描述
有一个有趣的手机游戏，有n*n个正方形的小按钮，有的按钮是黄色，有的按钮是白色。玩家的任务是通过点击按钮，让所有按钮都变成黄色，点按钮的次数越少，得分越高。
但是按钮有个奇怪的特点，当你点击了坐标为(x,y)的按钮后，坐标为(x,y),(x+1,y),(x-1,y),(x,y-1),(x,y+1)的五个按钮会同时改变自身的颜色，是白色的变成黄色，黄色的变成白色。完成游戏最少需要点击多少次按钮呢？请找出答案。
输入格式
第一行，一个整数n，表示有nn个按钮。(1<=n<=40)
接下来是一个由小写字母'y'和字符'w'构成的nn的矩阵，描述了游戏开始时的情景。'y'表示该按钮式黄色，'w'表示该按钮式白色。
输出格式
如果能够完成游戏，输出一个整数，表示所需最小点击次数。
如果无法完成游戏，输出"inf"。
思路：同样是异或方程组，但是这次是一个二维的矩阵，怎么转化为高斯消元呢？其实非常简单，把每一个方块的状态当作一个方程，显然，它旁边的四个点同样会影响它的状态，所以把这五个点在这一个方程的系数设为1，然后高斯消元即可。
#includeusing namespace std; char ch[55][55]; bool a[1805][1805], st[1805][1805]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; int ans = 1e9; void dfs(int u, int n) { if (u == -1) { int cnt = 0; for (int i = 0; i < n; i++) cnt += a[i][n]; ans = min(ans, cnt); return; } bool flg = 0; if (!a[u][u]) { if (a[u][n]) return; dfs(u - 1, n), flg = 1, a[u][n] = 1; } for (int i = 0; i < u; i++) { st[u][i] = a[i][n]; a[i][n] = a[i][n] - a[u][n] * a[i][u] + 2 & 1; } dfs(u - 1, n); for (int i = 0; i < u; i++) a[i][n] = st[u][i]; if (flg) a[u][n] = 0; } void Gauss(int n) { int i, j; for (i = 0, j = 0; i < n && j < n; i++, j++) { int mx = i; for (int k = i + 1; k < n; k++) { if (abs(a[k][j]) > abs(a[mx][j])) mx = k; } if (a[mx][j] == 0) { --i; continue; } if (mx ^ i) for (int k = j; k <= n; k++) swap(a[i][k], a[mx][k]); for (int k = i + 1; k < n; k++) { if (a[k][j] != 0) { for (int l = j; l <= n; l++) a[k][l] ^= a[i][l]; } } } dfs(n - 1, n); } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { int pos = i * n + j; a[pos][pos] = 1; for (int t = 0; t < 4; t++) { int x = i + dx[t], y = j + dy[t]; if (x >= 0 && x < n && y >= 0 && y < n) a[x * n + y][pos] = 1; } } for (int i = 0; i < n; i++) { scanf("%s", ch[i]); for (int j = 0; j < n; j++) { if (ch[i][j] == 'w') a[i * n + j][n * n] = 1; else a[i * n + j][n * n] = 0; } } Gauss(n * n); if (ans >= 1e9) return puts("inf"), 0; printf("%d", ans); }
4.[HNOI2013 DAY2]游走
问题描述
一个无向连通图，顶点从1 编号到N，边从1 编号到M。小Z 在该图上进行随机游走，初始时小Z 在1 号顶点，每一步小Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z到达N 号顶点时游走结束，总分为所有获得的分数之和。现在，请你对这M 条边进行编号，使得小Z 获得的总分的期望值最小。
输入格式
第一行是正整数N和M，分别表示该图的顶点数和边数，接下来M行每行是整数u，v(1≤u,v≤N)，表示顶点u与顶点v之间存在一条边。
输入保证30%的数据满足N≤10，
100%的数据满足2≤N≤500, 1<=M<=150000且是一个无向简单连通图。
输出格式
仅包含一个实数，表示最小的期望值，保留3 位小数。
思路：非常经典的一道期望+高斯消元的题目。首先看到期望应该把它转化为方程。 显然，让经过期望次数较大的边权值尽可能小，总分的期望值就会最小。那么如何算出每条边经过的期望次数呢？假设这条边的两个端点为u和v，设f[i]为走出第i个点的期望次数，d[i]为第i个点的度数，那么这条边经过的期望次数 = f[u] / d[u] + f[v] / d[v]。然后如何计算f[i]呢？首先终点为n的边不能计算贡献，因为我并不能走出n点。其次，如果起点为1，那么首先会有一个期望值1。那么这样的话，对于第i个点，f[i] = f[v1] / d[v1] + f[v2] / d[v2] + ... （其中vi是与i有边直接相连的点）。这个东西没有拓扑序，不能用递推或dfs解决，于是考虑高斯消元，n个未知数，m个方程，可以解决本题。#includeusing namespace std; struct node { int to, nxt; }e[400005]; int head[1005], tot; inline void add_e(int u, int v) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot;} typedef double db; const db eps = 1e-7; db d[1005], val[200005], a[605][605]; int st[200005], ed[200005]; void Gauss(int n) { for (int i = 1; i < n; i++) { int mx = i; for (int j = i + 1; j < n; j++) if (fabs(a[j][i]) > fabs(a[mx][i])) mx = j; if (mx ^ i) swap(a[i], a[mx]); // for (int j = i; j <= n; j++) swap(a[i][j], a[mx][j]); if (fabs(a[i][i]) < eps) continue; for (int j = 1; j < n; j++) { if (i ^ j) { db tmp = a[j][i] / a[i][i]; for (int k = i + 1; k <= n; k++) a[j][k] -= tmp * a[i][k]; } } } for (int i = 1; i < n; i++) a[i][n] /= a[i][i]; } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &st[i], &ed[i]); d[st[i]] += 1.0, d[ed[i]] += 1.0; add_e(st[i], ed[i]), add_e(ed[i], st[i]); } for (int i = 1; i < n; i++) { a[i][i] = -1.0; for (int j = head[i]; j; j = e[j].nxt) { int v = e[j].to; if (v == n) continue; a[i][v] = 1.0 / d[v]; } } a[1][n] = -1.0; Gauss(n); for (int i = 1; i <= m; i++) val[i] = a[st[i]][n] / d[st[i]] + a[ed[i]][n] / d[ed[i]]; sort(val + 1, val + m + 1); db ans = 0; // for (int i = 1; i <= m; i++) printf("%.3lf ", val[i]); for (int i = 1; i <= m; i++) ans += val[i] * (m - i + 1.0) * 1.0; printf("%.3lf", ans); }
5.[HNOI2011]XOR和路径
题目描述
给定一个无向连通图，其节点编号为 1 到 N，其边的权值为非负整数。试求出一条从 1 号节点到 N 号节点的路径，使得该路径上经过的边的权值的“XOR 和”最大。该路径可以重复经过某些节点或边，当一条边在路径中出现多次时，其权值在计算“XOR 和”时也要被重复计算相应多的次数。
直接求解上述问题比较困难，于是你决定使用非完美算法。具体来说，从 1 号节点开始，以相等的概率，随机选择与当前节点相关联的某条边，并沿这条边走到下一个节点，重复这个过程，直到走到 N 号节点为止，便得到一条从 1 号节点到 N 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。
输入格式
输入文件的第一行是用空格隔开的两个正整数N和M，分别表示该图的节点数和边数。紧接着的M行，每行是用空格隔开的三个非负整数u，v和w(1≤u,v≤N，0≤w≤10^9)，表示该图的一条边(u,v)，其权值为w。输入的数据保证图连通。
输出格式
输出文件仅包含一个实数，表示上述算法得到的路径的“XOR 和”的期望值，要求保留三位小数。（建议使用精度较高的数据类型进行计算）
思路：和游走那个题比较类似，但是我感觉这个题还要复杂一些。 要注意XOR这个东西，对于这个东西，我们有很多处理它的方案，但是原理都是一样：有类似前缀的性质，并且在二进制下每一位独立计算互不干扰。那么这个题就利用了它每一位可以独立计算的性质，对二进制下的每一位分别进行高斯消元，然后将每一位的答案合并。这就是这个题的核心考点。其余的对于期望的处理和上一题类似。#includeusing namespace std; typedef double db; const db eps = 1e-8; db a[105][105]; struct node { int to, nxt, len; }e[20005]; int head[105], tot, d[105]; inline void add_e(int u, int v, int w) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot; e[tot].len = w;} void Gauss(int n) { for (int i = 1; i <= n; i++) { int mx = i; for (int j = i + 1; j <= n; j++) if (fabs(a[j][i]) - fabs(a[mx][i]) > eps) mx = j; if (mx ^ i) swap(a[i], a[mx]); for (int j = 1; j <= n; j++) { if ((i ^ j) && fabs(a[j][i]) > eps) { db tmp = a[j][i] / a[i][i]; for (int k = i; k <= n + 1; k++) { a[j][k] -= tmp * a[i][k]; } } } } for (int i = 1; i <= n; i++) a[i][n + 1] /= a[i][i]; } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1, x, y, z; i <= m; i++) { scanf("%d%d%d", &x, &y, &z); if (x == y) {add_e(x, y, z), ++d[x]; continue;} add_e(x, y, z), add_e(y, x, z); ++d[x], ++d[y]; } db ans = 0; for (int k = 30; ~k; k--) { memset(a, 0, sizeof a); for (int i = 1; i < n; i++) { a[i][i] = -d[i]; for (int j = head[i]; j; j = e[j].nxt) { int v = e[j].to, w = e[j].len >> k & 1; w ? a[i][v] -= 1, a[i][n + 1] -= 1 : a[i][v] += 1; } } a[n][n] = 1; Gauss(n); ans += (1 << k) * a[1][n + 1]; } printf("%.3lf", ans); }