高斯消元

OI&ACM, 数学
  1. 1 【bzoj 1013】[JSOI2008]球形空间产生器sphere
  2. 2 【poj 1222】EXTENDED LIGHTS OUT
  3. 3 【bzoj 1770】[Usaco2009 Nov]lights 燈
  4. 4 【bzoj 2115】[Wc2011] Xor

1 【bzoj 1013】[JSOI2008]球形空间产生器sphere

已知一个n维球体的球面上n+1个点的坐标，求球心坐标

手推公式
设球心坐标x01,x02...x0n
(xi1-x01)2+(xi2-x02)2+...+(xin-x0n)^2 对于1<=i<=n+1值相同,组成n个方程
对于1和2：
∑ (x1i-x2i) * x01 = ∑ (x1i2-x2i2) (1<=i<=n)
写的好像看不懂，自己脑补一下就是了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<cstdio>
#include<cmath>
#define eps 1e-6
using namespace std;
int n,k;
double t,a[15][15];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n+1;i++)
		for(int j=1;j<=n;j++)
		{
			scanf("%lf",&t);
			a[i][j]+=t;a[i][n+1]+=t*t/2; 
			if(i!=1) a[i-1][j]-=t,a[i-1][n+1]-=t*t/2;
		}
	for(int i=1;i<=n;i++)
	{
		if(fabs(a[i][i])<eps) 
		{
			for(int j=i+1;j<=n;j++)
			  if(fabs(a[j][i])>=eps) {k=j;break;}
			swap(a[i],a[k]);
		}
		t=a[i][i];
		for(int j=1;j<=n+1;j++) a[i][j]/=t;
		for(int j=1;j<=n;j++)
		  if(j!=i)
		  {
		  	t=a[j][i];
		  	for(int k=1;k<=n+1;k++) a[j][k]-=a[i][k]*t;
		  }
	}
	for(int i=1;i<n;i++)  printf("%.3lf ",a[i][n+1]);
	printf("%.3lf\n",a[n][n+1]);
}

2 【poj 1222】EXTENDED LIGHTS OUT

当改变一个点的状态时，周围的四个点也会改变,求方案使都变成0

比如说(1,1)这个灯的最终状态将由(1,1),(1,2),(2,1)这三个灯的状态决定这样就可以列出一个方程:
(L(1,1)+x(1,1)+x(1,2)+0 * x(1,3)+...+x(2,1)+...)%2=0
L表示给出的初始状态的矩阵，x表示最终需要求的开关矩阵

即对于每一个点(m,n)，所有(i,j)的a(i,j) * x(i,j)异或起来=L
a表示(m,n)与(i,j)的改变有相关关系，即一个改变对另一个有影响

怎么总觉得我写的东西语言表达有问题。。。自己看代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int T;
bool a[31][32];
int main()
{
	scanf("%d",&T);
	for(int cas=1;cas<=T;cas++)
	{
		memset(a,0,sizeof(a));
		for(int i=1,x;i<=5;i++)
		  for(int j=1;j<=6;j++)
		  {
		  	x=(i-1)*6+j;
		  	scanf("%d",&a[x][31]);
		  	a[x][x]=1;
		  	if(j>1) a[x][x-1]=1;
			if(j<6) a[x][x+1]=1;
		  	if(i>1) a[x][x-6]=1;
			if(i<5) a[x][x+6]=1;
		  }
		for(int i=1,k;i<=30;i++)
		{
	  		k=i;while(!a[k][i]&&k<=30) k++;
	  		if(k!=i) for(int j=1;j<=31;j++)
			  swap(a[i][j],a[k][j]);
	  		for(int j=1;j<=30;j++)
	  		  if(i!=j&&a[j][i])
		  	 	for(int k=1;k<=31;k++) a[j][k]^=a[i][k];
		}
	  	printf("PUZZLE #%d\n",cas);
	  	for(int i=1;i<=30;i++)
	  	{
	  		printf("%d ",a[i][31]);
	  		if(!(i%6)) printf("\n");
	  	}
	}
}

3 【bzoj 1770】[Usaco2009 Nov]lights 燈

牛棚中一共有N盏灯，编号为1到N。有M条很神奇的无向边，每条边连接两盏灯。
每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候，这盏灯本身，还有所有有边连向这盏灯的灯的状态都会被改变。状态改变指的是：当一盏灯是开着的时候，这盏灯被关掉；当一盏灯是关着的时候，这盏灯被打开。
问最少要按下多少个开关，才能把所有的灯都给重新打开。

和上一题差不多，但是要求最少
所以要加一个dfs的过程 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,minn=0x7fffffff,x,y,tot,ans[36],a[36][37];
void Dfs(int x,int num)
{
	if(num>=minn) return;
	if(!x)
	{
		minn=num;return;
	}
	if(a[x][x])
	{
		ans[x]=a[x][n+1];
		for(int i=x+1;i<=n;i++)
		  if(a[x][i]) ans[x]^=ans[i];
		if(ans[x]) Dfs(x-1,num+1);
		else Dfs(x-1,num);
	}
	else
	{
		ans[x]=1;Dfs(x-1,num+1);
		ans[x]=0;Dfs(x-1,num);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&x,&y);
		a[x][y]=a[y][x]=1;
	}
	for(int i=1;i<=n;i++) a[i][i]=a[i][n+1]=1;
	for(int i=1,k;i<=n;i++)
	{
		k=i;while(!a[k][i]&&k<=n) k++;
		if(k>n) continue;
		if(k!=i) swap(a[i],a[k]);
		for(int j=1;j<=n;j++)
		  if(i!=j&&a[j][i])
		    for(int k=1;k<=n+1;k++)
		      a[j][k]^=a[i][k];
	}
	Dfs(n,0);
	printf("%d\n",minn);
}

4 【bzoj 2115】[Wc2011] Xor

这道题目看起来挺纠结的。
注意到一个性质，一个数xor它本身等于0，那么就是说如果一条边在xor序列里面出现两次就会被抵消。
那么我们可以先随便找到一条从1到n的路径求xor，然后找到图中所有的环分别求xor，最后判定取哪些环能使答案最大。可以这样理解，我们从路径上出去，走某个环，再回到路径上，那么过去和回来的路径是相同的这样就可以抵消。所以只要判定取哪些环能使答案最大就可以了。
有一个细节不能很快想到，就是怎么求环的xor值。
其实在dfs的时候能方便地解决。记每个点从1到它的xor值d[]。dfs的时候，如果发现某个节点x，它的后继节点y已经访问过了，说明构成了一个环，那么这个环的xor值就是d[x]w(x,y)d[y]。因为在环外的那部分x和y是一样的，xor一下就抵消了，剩下的就是环内的，再xor一下x到y的这条边，就是整个换的xor值。
然后是怎么判定取哪些环。这个就类似于hdu3949的那个xor高斯消元。消成若干个基数，再从大到小判断是否能使答案变大。
一开始我没有想到一点就是环的个数一定是m-n+1，然后数组开小了交上去就RE了。这种错误实在非常不能忍。
from winedia

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,ecnt,tot,st[50050],to[200050],next[200050];
long long ans,a[200010],d[50050],cost[200050];
bool used[50050];
void Addedge(int x,int y,long long z)
{
	to[++ecnt]=y;cost[ecnt]=z;next[ecnt]=st[x];st[x]=ecnt;
	to[++ecnt]=x;cost[ecnt]=z;next[ecnt]=st[y];st[y]=ecnt;
}
void dfs(int x)
{
	used[x]=1;
	for(int e=st[x],y;e;e=next[e])
	{
		y=to[e];
		if(!used[y]) used[y]=1,d[y]=d[x]^cost[e],dfs(y);
		else a[++tot]=d[x]^d[y]^cost[e];
	}
}
int Gauss()
{
	int i=1;
	for(int t=60;t>=0;t--)
	{
		int j=i;
		while(j<=tot&&!((a[j]>>t)&1)) j++;
		if(j<=tot)
		{
		    swap(a[i],a[j]);
		    for(int k=1;k<=tot;k++)
		      if(k!=i&&((a[k]>>t)&1))
			    a[k]^=a[i];
			i++;
		}
	}
	return i-1;
}
int main()
{
	scanf("%d%d",&n,&m);
	int x,y;long long z;
	while(m--)
	{
		scanf("%d%d%lld",&x,&y,&z);
		Addedge(x,y,z);
	}
	dfs(1);tot=Gauss();
	ans=d[n];
	for(int i=1;i<=tot;i++)
	  if((ans^a[i])>ans) ans^=a[i];
	printf("%lld\n",ans);
}
高斯消元