Tony102's Blog - 高斯消元
type: channel
link: https://tony102.com/index.php/tag/%E9%AB%98%E6%96%AF%E6%B6%88%E5%85%83/
items: Luogu2447 [SDOI2010]外星千足虫
items: Luogu4035 [JSOI2008]球形空间产生器

Luogu2447 [SDOI2010]外星千足虫
type: item
date: 2021-04-07T07:04:00+08:00
description: LinkSolbitset 优化高斯消元，是用来解异或方程组的。高斯消元需要钦定一个主元，然后逐一消去其他方程在该项，这样是 $O(n^3)$ 的，但是异或方程组直接异或把你选定的那个主元方程给它异或上去就可以了。其他的跟高斯消元一模一样Code#include <bits/stdc++.h> using namespace std; const int SIZE = 2e3 + 5; int n, m; std::bitset < SIZE > a[SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } inline int readChar() { int c = fetch(); while (c < '0' || c > '9') c = fetch(); return c - 48; } } using GTR::read; using GTR::readChar; int main() { n = read() + 1, m = read(); for (int i = 1; i <= m; ++ i) { for (int j = 1; j <= n; ++ j) a[i][j] = readChar(); } int ans = 0; for (int i = 1, cur; i < n; ++ i) { cur = i; while (!a[cur][i] && cur <= m) ++ cur; ans = std::max(ans, cur); if (cur == m + 1) { puts("Cannot Determine"); return 0; } if (cur != i) std::swap(a[i], a[cur]); for (int j = 1; j <= m; ++ j) { if (i == j || !a[j][i]) continue; a[j] ^= a[i]; } } printf("%d\n", ans); for (int i = 1; i < n; ++ i) puts(a[i][n] ? "?y7M#" : "Earth"); return 0; }

Luogu4035 [JSOI2008]球形空间产生器
type: item
date: 2021-01-11T20:32:00+08:00
description: LinkSol似乎很久都没有发题解了看题，现在在 $n$ 维空间中我们要求出这个球的球心。我们可以设球心的坐标为 $(r_1, r_2, \dots, r_n)$ 。根据给出的定义的距离公式，我们可以得到半径和一个球面上的点与球心的关系，即:$$ R = \sqrt{\sum \left( a_i-r_i\right)^2} $$有根号项，同时平方一下，并且把二项式展开$$ R^2= \sum a_{i}^2 - 2\sum{a_i\times r_i + \sum r_i^2} $$那么因为只有关$a_i$的先均可以视为常数项，将其移至等号右边，这样就得到了一个关于$r_i$的$n+1$一个方程。高斯消元求解即可Code#include <bits/stdc++.h> using namespace std; const int SIZE = 10 + 5; const int eps = 1e-7; int n; double a[SIZE][SIZE]; int main() { // freopen("code.in", "r", stdin); // freopen("code.out", "w", stdout); scanf("%d", &n); ++ n; for (int i = 1; i <= n; ++ i) { for (int j = 1; j < n; ++ j) { scanf("%lf", &a[i][j]); a[i][n + 1] -= a[i][j] * a[i][j]; a[i][j] *= -2.00; } a[i][n] = 1; } for (int i = 1, cur; i <= n; ++ i) { cur = i; for (int j = i + 1; j <= n; ++ j) { if (fabs(a[j][i]) > fabs(a[cur][i])) cur = j; } if (fabs(a[cur][i]) < eps) continue; std::swap(a[cur], a[i]); for (int j = i + 1; j <= n + 1; ++ j) a[i][j] /= a[i][i]; a[i][i] = 1.00; for (int j = 1; j <= n; ++ j) { if (i == j) continue; for (int k = i + 1; k <= n + 1; ++ k) a[j][k] -= a[j][i] * a[i][k]; a[j][i] = 0; } } for (int i = 1; i < n; ++ i) printf("%.3lf ", a[i][n + 1]); return 0; }