1.球形空间产生器
题目能得到的方程：
由于有二次方，则我们可以进行一些操作变成线性方程：
高斯消元的步骤：
1.先变成上三角矩阵
2.变成对角矩阵
3.然后左边就直接就是答案也即每个未知量的解
做法：
1.枚举列c
2. 找主元（绝对值最大的数）
3.交换主元和我当前行
4.把主元这行变成1
5.用主元这行消其他行，让其他列变成0
#include<bits/stdc++.h> using namespace std; const int N=15; double a[N][N],b[N][N]; int n; void gauss() { //转化成上三角矩阵 for(int r=1,c=1;c<=n;c++,r++) { //找主元 int t=r; for(int i=r+1;i<=n;i++) if(fabs(b[i][c]>fabs(b[t][c]))) t=i; //交换 for(int i=c;i<=n+1;i++) swap(b[t][i],b[r][i]); //归一化 for(int i=n+1;i>=c;i--) b[r][i]/=b[r][c]; //消当前列的当前行的下面行的数为0 for(int i=r+1;i<=n;i++) for(int j=n+1;j>=c;j--) b[i][j]-=b[i][c]*b[r][j]; } //转化成对角矩阵 for(int i=n;i>1;i--) for(int j=i-1;j;j--) { b[j][n+1]-=b[i][n+1]*b[j][i]; b[j][i]=0; } } int main() { scanf("%d",&n); for(int i=0;i<=n;i++) for(int j=1;j<=n;j++) scanf("%lf",&a[i][j]); for(int i=1;i<=n;i++)//转化成线性方程 for(int j=1;j<=n;j++) { b[i][j]=2*(a[i][j]-a[0][j]); b[i][n+1]+=a[i][j]*a[i][j]-a[0][j]*a[0][j]; } gauss();//高斯消元 for(int i=1;i<=n;i++) printf("%.3lf ",b[i][n+1]);//输出答案 return 0; }
2.开关问题
异或的高斯消元
方案数取决于我们自由元的个数，每个自由元有两种情况0或者1，则假如自由元有k个则,答案有2^k个方案，k就是n-非0行的个数也即自由元
#include<bits/stdc++.h> using namespace std; const int N=35; int n; int a[N][N]; int gauss() { int r,c; for(r=1,c=1;c<=n;c++) { //找主元 int t=r; for(int i=r+1;i<=n;i++) if(a[i][c]) t=i; //假如最大已经是了，则这一列不用操作了 if(!a[t][c]) continue; //交换 for(int i=c;i<=n+1;i++) swap(a[t][i],a[r][i]); //消 for(int i=r+1;i<=n;i++) for(int j=n+1;j>=c;j--) a[i][j]^=a[i][c]&a[r][j]; r++; } int res=1; if(r<n+1)//求自由元个数 { for(int i=r;i<=n;i++) { if(a[i][n+1]) return -1;//出现了0==！0无解 res*=2;//每个自由元都有两个状态则就是*2 } } return res; } int main() { int T; scanf("%d",&T); while(T--) { memset(a,0,sizeof a);//清空 scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i][n+1]);//存初始状态 for(int i=1;i<=n;i++) { int t; scanf("%d",&t); a[i][n+1]^=t;//初始跟末状态异或 a[i][i]=1;//自己这盏灯影响自己的状态 } int x,y; while(scanf("%d%d",&x,&y),x||y) a[y][x]=1;//x影响y这盏灯则y这行x会影响他 int t=gauss(); if(t==-1) puts("Oh,it's impossible~!!");//假如无解 else printf("%d\n",t); } return 0; }
