高斯消元

  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

今天学长来讲课了,2333
就是矩阵呀什么的(google去吧)

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 = ∑ (x1i^2-x2i^2) (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);
}