可并堆(实际上只有左倾树)
数学相关

高斯消元

HJWJBSR posted @ 2015年6月02日 17:27 in 专题 , 369 阅读

Orzei了hzwer的代码,还算是学了高斯消元吧。。。然后开始水了几道题。感觉高斯消元的题目有的思路还是很屌的。。。

BZOJ1013球形空间产生器:直接根据每个点到球心的距离相等列方程,然后直接Gauss()

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 105
#define eps 1e-6
#define INF 0x7f7f7f7f
double a[N][N],f[N];
int n;
inline double sqr(double x)
 {
 	return x*x;
 }
void Gauss()
 {
 	int now=1,i,j,k;double t;
 	for (i=1;i<=n;i++)
 	 {
 	 	j=now;while (fabs(a[j][i])<eps&&j<=n) j++;
 	 	if (j>n) continue;
 	 	for (k=i;k<=n+1;k++) swap(a[now][k],a[j][k]);
 	 	for (k=i+1;k<=n+1;k++) a[now][k]/=a[now][i];
 	 	a[now][i]=1;
 	    for (j=1;j<=n;j++)
 	     if (j!=i)
 	      {
 	     	 t=a[j][i];
 	     	 for (k=1;k<=n+1;k++)
 	     	   a[j][k]-=t*a[now][k];
 	      }
 	    now++;
 	 }
 	return;
 }
int main()
 {
 	int i,j,q,w,e;double k,l;
 	freopen("input.txt","r",stdin);
 	memset(f,0,sizeof(f));memset(a,0,sizeof(a));
 	scanf("%d",&n);
 	for (i=1;i<=n;i++)
 	  scanf("%lf",&f[i]);
 	for (i=1;i<=n;i++)
 	 for (j=1;j<=n;j++)
 	  {
 	  	 scanf("%lf",&k);
 	  	 a[i][j]=2*(k-f[j]);a[i][n+1]+=sqr(k)-sqr(f[j]);
 	  }
 	Gauss();
 	for (i=1;i<=n-1;i++)
 	  printf("%.3lf ",a[i][n+1]);
 	printf("%.3lf\n",a[n][n+1]);
 	return 0;
 }

BZOJ1923外星千足虫:取模高斯消元,感觉很吊,而且新技能get了bitset。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
#define N 2050
#define INF 0x7f7f7f7f
typedef bitset<N> M[N];
M a;
int n,m,ans=0;
void Gauss()
 {
 	int i,j,k,l;
 	for (i=1;i<=n;i++)
 	 {
 	 	j=i;while (!a[j][i]&&j<=m) j++;
 	 	if (j>m)
 	 	  {ans=-1;return;}else
 	 	  ans=max(ans,j);
 	 	swap(a[j],a[i]);
 	 	for (k=1;k<=m;k++)
 	 	 if (k!=i&&a[k][i])
 	 	   a[k]^=a[i];
 	 }
 	return;
 }
int main()
 {
 	int i,j,k,l,q,w,e;
 	char b[N],c[N];
 	scanf("%d%d",&n,&m);
 	for (i=1;i<=m;i++)
 	 {
 	 	scanf("%s%s",b,c);a[i][n+1]=c[0]-'0';
 	 	for (j=0;j<n;j++)
 	 	  a[i][j+1]=b[j]-'0';
 	 }
 	Gauss();
 	if (ans==-1)
 	 {
 	    printf("Cannot Determine\n");
 	    return 0;
 	 }
 	printf("%d\n",ans);
 	for (i=1;i<=n;i++)
 	 if (a[i][n+1])
 	   printf("?y7M#\n");else
 	   printf("Earth\n");
 	return 0;
 }

BZOJ2115XOR:感觉十分屌,可以将图转化为一条从1到n的路径及若干环,环有O(M)个,然后二进制按位看可不可以取,验证就用高斯消元。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 250050
#define ll long long
#define INF 0x7f7f7f7f
int ss=0,n,m,fi[N],c[N][2],tot=1,cir=0;
ll v[N],a2[N],s[N],ans=0,h[N];bool vis[N];
inline ll Read()
 {
 	ll x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
inline void Line(int x,int y,ll z)
 {
 	c[++ss][0]=y;c[ss][1]=fi[x];s[ss]=z;fi[x]=ss;
 	c[++ss][0]=x;c[ss][1]=fi[y];s[ss]=z;fi[y]=ss;
 	return;
 }
void DFS(int x)
 {
 	vis[x]=1;
 	for (int i=fi[x];i;i=c[i][1])
 	 if (!vis[c[i][0]])
 	  {
 	  	 h[c[i][0]]=h[x]^s[i];DFS(c[i][0]);
 	  }else
 	   v[++cir]=h[c[i][0]]^h[x]^s[i];
 	return;
 }
void Gauss()
 {
 	int i,j,k,l;ll q,w,e;
 	for (q=a2[60];q;q >>= 1)
 	 {
 	 	j=tot;while (j<=cir&&!(v[j]&q)) j++;
 	 	if (j>cir) continue;
 	 	swap(v[j],v[tot]);
 	 	for (i=1;i<=cir;i++)
 	 	 if (i!=tot&&v[i]&q)
 	 	   v[i]^=v[tot];
 	 	tot++;
 	 }
 	return;
 }
int main()
 {
 	int i,j,k,l;ll q,w,e;
 	memset(s,0,sizeof(s));memset(h,0,sizeof(h));
 	memset(v,0,sizeof(v));memset(c,0,sizeof(c));
 	memset(a2,0,sizeof(a2));memset(fi,0,sizeof(fi));
 	memset(vis,0,sizeof(vis));
 	scanf("%d%d",&n,&m);
 	for (i=1,a2[0]=1;i<=60;i++) a2[i]=a2[i-1] << 1;
 	for (i=1;i<=m;i++)
 	  k=Read(),l=Read(),q=Read(),Line(k,l,q);
 	DFS(1);Gauss();
 	ans=h[n];
 	for (i=1;i<tot;i++)
 	  ans=max(ans,ans^v[i]);
 	cout <<ans<<endl;
 	return 0;
 }

BZOJ2466树:据说只要高斯消元后暴力枚举未确定点DFS,总感觉dzy的代码很高能,现在还是不懂原理。。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 110
#define INF 0x7f7f7f7f
int a[N][N];
int n,m,ans,t[N];
void Gauss()
 {
    int i,j,k,l;
    for (i=1;i<=n;i++)
     {
        j=i;while (!a[j][i]&&j<=n) j++;
        
        if (j>n) continue;
        swap(a[j],a[i]);
        for (j=1;j<=n;j++)
         if (j!=i&&a[j][i])
          for (k=1;k<=n+1;k++)
            a[j][k]^=a[i][k];
     }
    return;
 }
inline void DFS(int x,int y)
 {
 	if (y>=ans) return;
    if (!x) {ans=min(ans,y);return;}
    if (a[x][x])
     {
        t[x]=a[x][n+1];
        for (int i=x+1;i<=n;i++)
          t[x]^=(t[i]&a[x][i]);
        DFS(x-1,y+t[x]);
     }else
      DFS(x-1,y+(t[x]=0)),DFS(x-1,y+(t[x]=1));
    return;
 }
int main()
 {
    int i,j,k,l,q,w,e;
    while (scanf("%d",&n),n)
     {
        ans=INF;
        memset(a,0,sizeof(a));memset(t,0,sizeof(t));
        for (i=1;i<=n;i++)
          a[i][i]=a[i][n+1]=1;
        for (i=1;i<n;i++)
          scanf("%d%d",&k,&l),a[k][l]=a[l][k]=1;
        Gauss();DFS(n,0);
        printf("%d\n",ans);
     }
    return 0;
 }

BZOJ2337XOR和路径:之前一直在想怎么设从1到i的二进制位为1的概率写方程,其实还好,但是被样例卡了很久没想出来1怎么处理= =结果应该是设从i到n的二进制位为1的概率(好像确实没区别),并且a[n]设为0。然后按位跑高斯消元求出a[1],然后带权求和即可。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 105
#define M 20050
#define INF 0x7f7f7f7f
int fi[N],c[M][3],n,m,ss=1,d[N];
double a[N][N],ans=0;
long long s=0;
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
inline void Line(int x,int y,int z)
 {
 	c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
 	c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
 	return;
 }
void Gauss()
 {
 	int i,j,k;double l;
 	for (i=1;i<n;i++)
 	 {
 	 	j=i;while (!a[j][i]) j++;
 	 	swap(a[j],a[i]);
 	 	for (j=i+1;j<=n;j++) a[i][j]/=a[i][i];
 	 	a[i][i]=1;
 	    for (j=1;j<n;j++)
 	     if (a[j][i]&&j!=i)
 	      {
 	      	 l=a[j][i];
 	      	 for (k=1;k<=n;k++)
 	      	   a[j][k]-=a[i][k]*l;
 	      }
 	 }
 	return;
 }
inline void Set_up(int x)
 {
 	int i,j,k,l;double q,w,e;
 	for (i=1;i<n;i++)
 	 {
 	 	q=1.0/d[i];a[i][i]=-1;
 	 	for (j=fi[i];j;j=c[j][1])
 	 	 if (j%2&&c[j][0]==i) continue;else
 	 	 if (c[j][0]==n) a[i][n]-=c[j][2]&x?q:0;else
 	 	 if (c[j][2]&x) 
 	 	   a[i][c[j][0]]-=q,a[i][n]-=q;else
 	 	   a[i][c[j][0]]+=q;
 	 }
 	return;
 }
int main()
 {
 	int i,j,k,l,q,w,e;
 	memset(a,0,sizeof(a));memset(c,0,sizeof(c));
 	memset(fi,0,sizeof(fi));memset(d,0,sizeof(d));
 	scanf("%d%d",&n,&m);
 	for (i=1;i<=m;i++)
 	 {
 	    k=Read(),l=Read(),Line(k,l,Read());
 	    d[k]++;if (k!=l) d[l]++;
 	 }
 	for (s=1;s<=1073741824;s <<= 1)
 	 {
 	 	Set_up(int(s));Gauss();
 	 	ans+=(int)(s)*a[1][n];
 	 	memset(a,0,sizeof(a));
 	 }
 	printf("%.3lf\n",ans);
 	return 0;
 }

BZOJ3143游走:直接设每个点走过次数的期望列方程,注意边界是an=1以及a1的方程里面要加上1。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1050
#define M 1000050
#define INF 0x7f7f7f7f
struct Edge
 {
 	int u,v;double t;
 } b[M];
double a[N][N],ans=0;
int n,m,c[M][2],fi[N],ss=1,d[N];
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
inline void Line (int x,int y)
 {
 	c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
 	c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
 	return;
 }
void Gauss()
 {
 	int i,j,k;double l;
 	for (i=1;i<n;i++)
 	 {
 	 	j=i;while (!a[j][i]) j++;
 	 	swap(a[i],a[j]);
 	 	for (j=i+1;j<=n;j++)
 	 	  a[i][j]/=a[i][i];
 	 	a[i][i]=1;
 	 	for (k=1;k<n;k++)
 	 	 if (k!=i&&a[k][i])
 	 	  {
 	 	  	 l=a[k][i];
 	 	  	 for (j=1;j<=n;j++)
 	 	  	   a[k][j]-=l*a[i][j];
 	 	  }
 	 }
 	return;
 }
void Set_up()
 {
 	int i,j,k,l;double q,w,e;
 	for (i=1;i<n;i++)
 	 {
 	 	a[i][i]=-1;
 	 	for (j=fi[i];j;j=c[j][1])
 	 	 if (c[j][0]!=n)
 	 	   a[i][c[j][0]]=1.0/d[c[j][0]];
 	 }
 	a[1][n]=-1;
 	return;
 }
inline bool cmp(Edge x,Edge y)
 {
 	return x.t>y.t;
 }
int main()
 {
 	int i,j,k,l,q,w,e;
 	memset(c,0,sizeof(c));memset(a,0,sizeof(a));
 	memset(fi,0,sizeof(fi));memset(d,0,sizeof(d));
 	scanf("%d%d",&n,&m);
 	for (i=1;i<=m;i++)
 	 {
 	    Line(b[i].u=k=Read(),b[i].v=l=Read()),d[k]++,d[l]++;
 	    if (k==n) swap(b[i].u,b[i].v);
 	 }
  	Set_up();Gauss();
 	for (i=1;i<=m;i++)
 	  b[i].t=a[b[i].u][n]/d[b[i].u]+a[b[i].v][n]/d[b[i].v];
 	sort(b+1,b+m+1,cmp);
 	for (i=1;i<=m;i++)
 	  ans+=b[i].t*i;
 	printf("%.3lf\n",ans);
 	return 0;
 }

BZOJ3503和谐矩阵:由于元素数量过多,不能直接列方程,但是可以推出每个格子是哪些第一行元素的异或和,然后就直接列异或方程。但是最后求可行解的部分好像加了特技= =(其实是人太naive一开始还写什么DFS之类的什么找可行解)具体部分看代码吧。。。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 105
#define M 10050
#define ll long long
#define INF 0x7f7f7f7f
int a[N][N],n,m,c[N][N],ss;
ll b[N][N];
void Gauss()
 {
 	int i,j,k,l;
 	for (i=1;i<=m;i++)
 	 {
 	 	j=i;while (j<=m&&!a[j][i]) j++;
 	 	if (j>m) continue;
 	 	swap(a[i],a[j]);
 	 	for (j=1;j<=m;j++)
 	 	 if (j!=i&&a[j][i])
 	 	  for (k=1;k<=m;k++)
 	 	    a[j][k]^=a[i][k];
 	 }
 	for (i=m;i>=1;i--)
 	 {
 	 	if (!a[i][i])
 	 	  {c[1][i]=1;continue;}
 	 	for (j=i+1;j<=m;j++)
 	 	  c[1][i]^=a[i][j]&c[1][j];
 	 }
 	return;
 }
int main()
 {
 	int i,j,k,l,q,w,e;
 	memset(a,0,sizeof(a));memset(b,0,sizeof(b));
 	memset(c,0,sizeof(c));
 	scanf("%d%d",&n,&m);
 	b[1][1]=1;for (i=2;i<=m;i++) b[1][i]=b[1][i-1] << 1;
 	for (i=2;i<=n+1;i++)
 	 for (j=1;j<=m;j++)
 	   b[i][j]=b[i-1][j-1]^b[i-1][j]^b[i-1][j+1]^b[i-2][j];
 	for (i=1;i<=m;i++)
 	 for (j=1;b[n+1][i];j++)
 	   a[i][j]=b[n+1][i]%2,b[n+1][i]/=2;
 	Gauss();ss=0;
 	for (i=2;i<=n;i++)
 	 for (j=1;j<=m;j++)
 	   c[i][j]=c[i-1][j-1]^c[i-1][j]^c[i-1][j+1]^c[i-2][j];
 	for (i=1;i<=n;i++)
 	 {
 	 	for (j=1;j<=m;j++)
 	 	  printf("%d ",c[i][j]);
 	 	printf("\n");
 	 }
 	return 0;
 }

先更到这里吧,感觉再多题目我也还是做不出来= =先提高自身姿势再来填坑吧。。。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter