高斯消元

今天,跟着HYM大神学习了高斯消元,思想很简单,不过用处很大,也有一些细节。

其实就是消元的思想,对n个方程不断消元,在解出一个未知数之后,回带求出其他未知数。如果回带时,我们发现方程左面为0,右面不为0,则无解;若左面为0,右面为0,则多解。

cogs1845||bzoj1013 球星空间生成器sphere

题目大意:给出n维空间内一个球上的n+1个点,求圆心坐标。

思路:比较裸的高斯消元,唯一就是自己建方程。设圆心坐标(a,b,c,d,...),我们发现,球上各点到圆心距离相等,于是就有连等式:(a-a1)^2+(b-b1)^2+(c-c1)^2+(d-d1)^2+...=(a-a2)^2+(b-b2)^2+(c-c2)^2+(d-d2)^2...=...=(a-an)^2+(b-bn)^2+(c-cn)^2+(d-dn)^2;选取等号左右的式子建方程,得到n个方程,求解就可以了。由题意可知,这里不需要考虑无解的情况。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
double a[100][100]={0},b[100]={0},c[100][100];
int main()
{
    freopen("bzoj_1013.in","r",stdin);
    freopen("bzoj_1013.out","w",stdout);
    
    int n,i,j,k,maxn,maxi;
    double t;
    scanf("%d",&n);
    for (i=1;i<=n+1;++i)
      for (j=1;j<=n;++j)
      {
           scanf("%lf",&c[i][j]);
           c[i][j]*=1.0;
      }
    for (i=1;i<=n;++i)
    {
      t=0;
      for (j=1;j<=n;++j)
      {
           a[i][j]=2*(c[i][j]-c[i+1][j]);
           t+=c[i][j]*c[i][j]-c[i+1][j]*c[i+1][j];
      }
      a[i][n+1]=t;
    }
    for (i=1;i<=n;++i)
    {
        if (a[i][i]==0)
        {
            for (j=i+1;j<=n;++j)
              if (a[j][i]!=0)
              {
                    for (k=1;k<=n+1;++k)
                      swap(a[i][k],a[j][k]);
                    break;
              }
        }
        for (j=i+1;j<=n;++j)
        {
            t=a[j][i]/a[i][i];
            for (k=1;k<=n+1;++k)
              a[j][k]-=a[i][k]*t;
        }
    }
    for (i=n;i>=1;--i)
    {
        b[i]=a[i][n+1]/a[i][i];
        for (j=i-1;j>=1;--j)
        {
            a[j][n+1]-=a[j][i]*b[i];
            a[j][i]=0;
        }
    }
    for (i=1;i<n;++i)
      printf("%0.3f ",b[i]);
    printf("%0.3f
",b[n]);
    
    fclose(stdin);
    fclose(stdout);
}
View Code

bzoj2337 XOR和路径

http://www.cnblogs.com/Rivendell/p/4734640.html

解异或方程组

bzoj1923 外星千足虫

题目大意:给定m个方程,有n个未知数,判断有无唯一解,若有求出最早在第几个方程处判断出的,并输出答案;无解就输出“Cannot Determine”。

思路:因为要求最早在哪求出解,所以一开始想二分一下,回来觉得会超时,就。。。了一下学长的博客,其实只需要在对第i个合法方程(第i个未知数前系数不为0)操作的时候,取max就可以了(这种思想要掌握)。这道题目中,只有0、1,所以可以用xor来计算。一开始狂wa,回来才发现,回带的时候,要判断几个不为0,否则xor后就呵呵了。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct use{
    int num[1002],p;
}a[2001],b;
int n,m,ans=0,k;
void gauss()
{
    int i,j,k;
    bool f=false;
    for (i=1;i<=n;++i)
    {
        if (a[i].num[i]==0)
        {
            f=false;
            for (j=i+1;j<=m;++j)
                if (a[j].num[i]!=0)
                {
                    swap(a[i],a[j]);
                    f=true;break;
                }
            if (!f)
            {
                ans=0;return;
            }
        }
        ans=max(ans,a[i].p);
        for (j=i+1;j<=m;++j)
        {
            if (a[j].num[i]!=0)
                for (k=1;k<=n+1;++k)
                    a[j].num[k]^=a[i].num[k];
        }
    }
    for (i=n;i>=1;--i)
    {
        b.num[i]=a[i].num[n+1]/a[i].num[i];
        for (j=i-1;j>=1;--j)
        {
            if (a[j].num[i])
            {
                a[j].num[n+1]=a[j].num[n+1]^b.num[i];
                a[j].num[i]=0;
            }
        }
    }
}
int main()
{
    int i,j;
    char ch;
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;++i)
    {
        scanf("%*c");
        for (j=1;j<=n;++j)
        {
            scanf("%c",&ch);
            a[i].num[j]=ch-'0';
        }
        scanf("%d",&a[i].num[n+1]);
        a[i].p=i;
    }
    gauss();
    if (ans==0) printf("Cannot Determine
");
    else
    {
        printf("%d
",ans);
        for (i=1;i<=n;++i)
        {
            if (b.num[i]==0) printf("Earth
");
            else printf("?y7M#
");
        }
    }
}
View Code

bzoj3503 和谐矩阵

题目大意:给n*m的矩阵放0、1,要求一个人上下左右和自己中只有偶数个1,求一种合法方案。

思路:对n*m个位置列异或方程组,这个点四周和自己的未知数异或=0,然后就是解异或方程组了。这里会出现解出来都是0的情况,这是不合法的(题目要求不全为0),那我们就要在解方程的时候,如果回带时这个位置上的a[i][i]=0,说明这个位置是0是1都可以,我们就赋成1。

        注意解异或方程组的方法。这里在判断那些0/1都行的点时,可以边做发现后面的这一位系数都是0的时候,就赋成1,同时还要把其他方程中的这个未知数的影响取消。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxnode 1605
using namespace std;
struct use{
    int num[maxnode];
}ai[maxnode]={0},bi;
int tot=0,dx[5]={0,0,1,-1,0},dy[5]={1,-1,0,0,0};
void gauss()
{
    int i,j,k;
    bool f=false;
    for (i=1;i<=tot;++i){
      if (!ai[i].num[i]){
           f=false;
           for (j=i+1;j<=tot;++j)
            if (ai[j].num[i]){
                swap(ai[i],ai[j]);f=true;break;
            }
        if (!f){
            bi.num[i]=1;
            for (j=1;j<=tot;++j) ai[j].num[tot+1]^=ai[j].num[i];
        }
      }
      for (j=i+1;j<=tot;++j)
          if (ai[j].num[i])
              for (k=1;k<=tot+1;++k) ai[j].num[k]^=ai[i].num[k];
    }
    for (i=tot;i>=1;--i)
      if (!bi.num[i]){
          bi.num[i]=ai[i].num[tot+1]/ai[i].num[i];
          for (j=i-1;j>=1;--j)
             if (ai[j].num[i]){
              ai[j].num[tot+1]^=bi.num[i];ai[j].num[i]=0;
             }
      }
}
int main()
{
    int n,m,i,j,k,x,y;
    scanf("%d%d",&n,&m);tot=n*m;
    for (i=1;i<=n;++i)
      for (j=1;j<=m;++j)
          for (k=0;k<5;++k){
              x=i+dx[k];y=j+dy[k];
              if (x<=0||x>n||y<=0||y>m) continue;
              ai[(i-1)*m+j].num[(x-1)*m+y]=1;
          }
    gauss();
    for (i=1;i<=n;++i){
      for (j=1;j<=m;++j) printf("%d ",bi.num[(i-1)*m+j]);
      printf("
");
    }
}
View Code

 
bzoj2466 树

题目大意:给定一棵树,所有点是0,每次操作可以把u这个点以及和它相邻的状态置反,问所有点变成1的最少操作次数。

思路:n<=100,可以建出异或方程组,其中有一些变量的值可0可1,记录下来,然后暴力枚举这些变量的状态,在gauss回带就可以了。

注意:通过消三角矩阵求出无关元,枚举无关元状态之后在回带,因为无关元的状态会影响其他变量的取值,但无关元之间互不影响。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 105
using namespace std;
int ai[N][N],bi[N],zh[N],n,ans,co[N],cc[N][N];
void gauss(){
    int i,j,k;bool f;
    for (i=1;i<=n;++i){
        if (!ai[i][i]){
            for (f=false,j=i+1;j<=n&&!f;++j)
                if (ai[j][i])
                    for (f=true,k=1;k<=n+1;++k) swap(ai[i][k],ai[j][k]);
            if (!f){zh[++zh[0]]=i;continue;}
        }for (j=i+1;j<=n;++j)
            if (ai[j][i])
              for (k=i;k<=n+1;++k) ai[j][k]^=ai[i][k];
    }
}
void dfs(int ii,int cnt){
    if (cnt>=ans) return;
    if (ii>zh[0]){
        int i,j,ci=0;
        for (i=1;i<=n;++i)
          for (j=1;j<=n+1;++j) cc[i][j]=ai[i][j];
        for (i=n;i;--i){
            if (!cc[i][i]) bi[i]=co[i];
            else bi[i]=cc[i][n+1]/cc[i][i];
            for (j=i-1;j;--j)
              if (cc[j][i]) cc[j][n+1]^=bi[i];
        }for (i=1;i<=n;++i) ci+=bi[i];
        ans=min(ans,ci);return;
    }dfs(ii+1,cnt);
    co[zh[ii]]=1;dfs(ii+1,cnt+1);co[zh[ii]]=0;
}
int main(){
    int i,j,u,v,cnt;
    while(scanf("%d",&n)==1){
        if (!n) break;ans=n;
        memset(ai,0,sizeof(ai));
        for (i=1;i<n;++i){
            scanf("%d%d",&u,&v);
            ai[u][v]=ai[v][u]=1;
        }for (i=1;i<=n;++i) ai[i][i]=ai[i][n+1]=1;
        zh[0]=0;gauss();dfs(1,0);
        printf("%d
",ans);
    }
}
View Code
原文地址:https://www.cnblogs.com/Rivendell/p/4294258.html