高斯消元
以前只会贺板子，理解了但不深刻，很快就忘了，现在再看高斯消元，也没有很难理解的。
我们首先第一步枚举要消的元是哪个，然后将其系数置为\(1\),再将剩余方程中这个元的系数消为\(0\),这样辗转反复，我们就可以得到最后一个元的答案，然后逐步带回即可
\(code\)
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const double eps=1e-8;
double a[200][200];
int n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)for(int j=1;j<=n+1;j++)scanf("%lf",&a[i][j]);
for(int i=1;i<=n;i++){
int tmp=i;
for(int j=i+1;j<=n;j++)if(fabs(a[j][i])>fabs(a[tmp][i]))tmp=j;
if(tmp!=i)swap(a[tmp],a[i]);
if(fabs(a[i][i])<eps){
puts("No Solution");
return 0;
}
double lsp=a[i][i];
for(int j=i;j<=n+1;j++)a[i][j]/=lsp;
for(int j=i+1;j<=n;j++){
double op=a[j][i];
for(int k=i;k<=n+1;k++){
a[j][k]-=op*a[i][k];
}
}
}
for(int i=n-1;i>=1;i--){
for(int k=i+1;k<=n;k++){
a[i][n+1]-=a[k][n+1]*a[i][k];
}
}
for(int i=1;i<=n;i++)printf("%.2lf\n",a[i][n+1]);
return 0;
}
高斯约旦消元
就是将高斯消元的过程简略了一下，在消元的情况中也对之前处理过的行消元，这样我们得到的解就可用对角线上的系数与权值相除的方法得到。
\(code\)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const double eps=1e-8;
double a[200][200];
int n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)for(int j=1;j<=n+1;j++)scanf("%lf",&a[i][j]);
for(int i=1;i<=n;i++){
int tmp=i;
for(int j=i+1;j<=n;j++)if(fabs(a[j][i])>fabs(a[tmp][i]))tmp=j;
if(tmp!=i)swap(a[tmp],a[i]);
double div=a[i][i];
if(fabs(div)<eps){
puts("No Solution");
return 0;
}
for(int j=i;j<=n+1;j++)a[i][j]/=div;
for(int j=1;j<=n;j++){
if(j==i)continue;
div=a[j][i];
for(int k=i;k<=n+1;k++){
a[j][k]-=div*a[i][k];
}
}
}
for(int i=1;i<=n;i++)printf("%.2lf\n",a[i][n+1]/a[i][i]);
return 0;
}
异或方程组
其实就是将高斯消元的方程组换为了异或方程，即从求解
\[ \begin{cases} a_{1,1}x_1+a_{1,2}x_2+a_{1,3}x_3+...+a_{1,n}x_n=b_1\\ a_{2,1}x_1+a_{2,2}x_2+a_{2,3}x_3+...+a_{1,n}x_n=b_2\\ ...\\ a_{n,1}x_1+a_{n,2}x_2+a_{n,3}x_3+...+a_{n,n}x_n=b_n \end{cases} \]变为
\[ \begin{cases} a_{1,1}x_1\ xor\ a_{1,2}x_2\ xor\ a_{1,3}x_3\ xor\ ...\ xor\ a_{1,n}x_n=b_1\\ a_{2,1}x_1\ xor\ a_{2,2}x_2\ xor\ a_{2,3}x_3\ xor\ ...\ xor\ a_{1,n}x_n=b_2\\ ...\\ a_{n,1}x_1\ xor\ a_{n,2}x_2\ xor\ a_{n,3}x_3\ xor\ ...\ xor\ a_{n,n}x_n=b_n \end{cases} \]因为异或是满足结合律和交换律的，所以我们可使用普通高斯消元的方法求解异或方程组，并可用\(bitset\)优化时间。下面的代码是外星千足虫这题的代码，使用的就是\(bitset\)优化高斯约旦消元求解异或方程组。
\(code\)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;
int n,m;
bitset<2010>Bit[2010];
char ch[2010];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int s1=0;
scanf("%s%d",ch+1,&s1);
for(int j=1;j<=n;j++)Bit[i].set(j,int(ch[j]-'0'));
Bit[i].set(0,s1);
}
int ans=-1;
for(int i=1;i<=n;i++){
int tmp=i;
while(tmp<=m&&!Bit[tmp].test(i))tmp++;
if(tmp>m){
puts("Cannot Determine");
return 0;
}
ans=max(ans,tmp);
if(tmp!=i)swap(Bit[i],Bit[tmp]);
for(int j=1;j<=m;j++){
if(i!=j&&Bit[j].test(i)==1)Bit[j]^=Bit[i];
}
}
printf("%d\n",ans);
for(int i=1;i<=n;i++)printf(Bit[i].test(0)==0?"Earth\n":"?y7M#\n");
return 0;
}