其实就是那种暴力的加减消元啊。。
步骤：
- 每次枚举一个未知数(x_i)，选出这项系数最大的方程式换到第(i)行
- 把剩下的(n-i)个方程式的(x_i)系数减为0
- 这时就形成了一个上三角，最后一项的答案已经算出来了。然后就依次往前推
void Gauss()
{
int r; double db;
for(int i=1;i<n;i++)
{
r=i;
for(int j=i+1;j<n;j++) if(fabs(a[j][i]>a[r][i])) r=j;
if(r!=i) swap(a[r],a[i]);
for(int j=i+1;j<n;j++)
{
db=a[j][i]/a[i][i];
for(int l=i;l<=n;l++) a[j][l]-=db*a[i][l];
}
}
for(int i=n-1;i>0;i--)
{
for(int j=i+1;j<n;j++) a[i][n]-=a[j][n]*a[i][j];
a[i][n]/=a[i][i];
}
}
3143: [Hnoi2013]游走
要算边的概率就先算点的概率
点的概率可以用所有与它有边的点表示，高斯消元
但是要注意的是1的概率还有一个常数1，n不会走到其他点所以不用算概率
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,k,d[100001];
struct vv
{
int u,v; double res;
} c[300001];
bool cmp(vv a,vv b) {return a.res>b.res; }
double a[510][510],ans;
void Gauss()
{
int r; double db;
for(int i=1;i<n;i++)
{
r=i;
for(int j=i+1;j<n;j++) if(fabs(a[j][i]>a[r][i])) r=j;
if(r!=i) swap(a[r],a[i]);
for(int j=i+1;j<n;j++)
{
db=a[j][i]/a[i][i];
for(int l=i;l<=n;l++) a[j][l]-=db*a[i][l];
}
}
for(int i=n-1;i>0;i--)
{
for(int j=i+1;j<n;j++) a[i][n]-=a[j][n]*a[i][j];
a[i][n]/=a[i][i];
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&c[i].u,&c[i].v);
d[c[i].u]++, d[c[i].v]++;
}
for(int i=1;i<=m;i++)
{
if(c[i].u==n || c[i].v==n) continue;
a[c[i].u][c[i].v]=1.0/d[c[i].v];
a[c[i].v][c[i].u]=1.0/d[c[i].u];
}
for(int i=1;i<n;i++) a[i][i]=-1.0;
a[1][n]=-1; Gauss();
for(int i=1;i<=m;i++) c[i].res=a[c[i].v][n]/d[c[i].v]+a[c[i].u][n]/d[c[i].u];
sort(c+1,c+1+m,cmp);
for(int i=1;i<=m;i++) ans+=c[i].res*i;
printf("%.3lf",ans);
}
1013: [JSOI2008]球形空间产生器sphere
设球心是(x1,x2,x3,x4,x5...)
每个点到球心的距离是相同的
列出这个柿子，相邻两个联立一下，移调常数项就变成
(2 imes(a_1-a_2)x_1+2 imes(b_1-b_2)x_2+2 imes(c_1-c_2)x_3+...=a_2^2-a_1^2+b_2^2-b_1^2..)
然后就高斯消元啦
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define M 510
using namespace std;
int n,m;
double d[M],a[M][M],k;
void Guss()
{
int r; double db;
for(int i=1;i<n;i++)
{
r=i;
for(int j=i+1;j<n;j++) if(fabs(a[j][i]>a[r][i])) r=j;
if(r!=i) swap(a[r],a[i]);
for(int j=i+1;j<n;j++)
{
db=a[j][i]/a[i][i];
for(int l=i;l<=n;l++) a[j][l]-=db*a[i][l];
}
}
for(int i=n-1;i>0;i--)
{
for(int j=i+1;j<n;j++) a[i][n]-=a[j][n]*a[i][j];
a[i][n]/=a[i][i];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf",&d[i]);
for(int i=2;i<=n+1;i++)
for(int j=1;j<=n;j++)
{
scanf("%lf",&k);
a[i-1][j]=2*k-2*d[j];
a[i-1][n+1]+=k*k-d[j]*d[j];d[j]=k;
}
n+=1;
Guss();
for(int i=1;i<n;i++) printf("%.3lf ",a[i][n]);
}
1923: [Sdoi2010]外星千足虫
一个神奇的操作：线性基解异或方程组！
- 用(bitset)维护线性基(如果插入个数小于n就无解)
- 求第(i)位的解就是只把这一位设成1，然后异或成0的过程中顺便求出即可
// luogu-judger-enable-o2
#include<iostream>
#include<cstring>
#include<cstdio>
#include<bitset>
using namespace std;
bitset <1002> q[1002];
bitset <1002> a;
int n,m,k,b[2001],c[2001],cnt, ans,t;
char ch[2001];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%s",ch+1);
for(int j=1;j<=n;j++) a[j]=ch[j]-'0';
scanf("%d",&k);
for(int j=n;j>=1;j--) if(a[j])
{
if(!q[j][j]) {q[j]=a, c[j]=k, cnt++, t=i; break;}
a^=q[j], k^=c[j];
}
}
if(cnt!=n)
{
printf("Cannot Determine");
return 0;
}
printf("%d
",t);
for(int i=1;i<=n;i++)
{
a.reset(); a[i]=1; ans=0;
for(int j=i;j>=1;j--) if(a[j])
{
a^=q[j]; ans^=c[j];
}
if(ans) printf("?y7M#
");
else printf("Earth
");
}
}