蒟蒻掉rating辣

最近考一场掉一次rating一点都不爽

问题是新高一已经来了

于是被碾炸惹呜呜呜

20160612终于压线上了紫名

但还是比新高一大爷低到不知道哪里去了

顺带还沉浸在POI要剧终的悲伤中

哎。。

感觉高斯消元这东西之前没怎么写过（其实根本就没写过辣

大家快去膜lbn187 http://lbn187.is-programmer.com/posts/95838.html

所以呢。。应该要来学习一下辣 （蒟蒻只做了5道求不D (๑•ᴗ•๑)

1013: [JSOI2008]球形空间产生器sphere

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define eps 1e-6
#define INF 0x3f3f3f3f
#define NN 25
#define LL long long
#define D double

D a[NN][NN],f[NN],tmp;
int n;

D sqr(D xx) { return xx*xx;}

void Gauss()
{
	int now = 1, v;
	D t;
	for (int i=1;i<=n;++i)
	{
		for (v = now;v<=n;++v) if (fabs(a[v][i])>eps) break;
		if (v>n) continue;
		if (v!=now)
			for (int j=1;j<=n+1;++j) swap(a[v][j],a[now][j]);
		t = a[now][i];
		for (int j=1;j<=n+1;++j) a[now][j] /= t;
		for (int j=1;j<=n;++j)
		if (j!=now)
		{
			t = a[j][i];
			for (int k=1;k<=n+1;++k)
				a[j][k] -= t*a[now][k];
		}
		++now;
	}
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%lf",&f[i]);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
		{
			scanf("%lf",&tmp);
			a[i][j] = 2 * (tmp - f[j]);
			a[i][n+1] += sqr(tmp) - sqr(f[j]);
		}
	Gauss();
	for (int i=1;i<n;++i) printf("%.3lf ",a[i][n+1]);
	printf("%.3lf\n",a[n][n+1]);
	return 0;
}

1923: [Sdoi2010]外星千足虫

好像xor方程有某种奇特的姿势

反正还是查了好多题解之类的学习了一下

（bitset是什么QAQ怎么这么厉害

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <bitset>
using namespace std;

#define NN 2010

bitset <NN> g[NN];
int n,m,ans = 0;
char ch[NN];

bool Gauss()
{
	int now = 0;
	for (int i=1;i<=n;++i)
	{
		int j = now+1;
		while (j<=m && !g[j][i]) ++j;
		if (j > m) return 0;
		else ans = max(ans,j);
		++now;
		swap(g[j],g[now]);
		for (j = 1;j<=m;++j)
			if (j!=now && g[j][i]) g[j] ^= g[now];
	}
	return 1;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i)
	{
		scanf("%s",ch+1);
		for (int j=1;j<=n;++j) g[i][j] = ch[j] - '0';
		scanf("%s",ch+1);
		g[i][n+1] = ch[1] - '0';
	}
	if (!Gauss()) { puts("Cannot Determine"); return 0; }
	printf("%d\n",ans);
	for (int i=1;i<=n;++i)
		if (g[i][n+1]) puts("?y7M#"); else puts("Earth");
	return 0;
}

2337: [HNOI2011]XOR和路径

感觉这东西一副期望DP很好用的样子哎

当然这个建方程的鬼要比之前难哎 （感觉自环+xor坑

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;

#define LD long double
#define NN 110

struct E
{
	int ne,v,w;
}e[NN*NN<<1];
int head[NN], tot, n, m, d[NN], x, y, z;
LD f[NN][NN], a[NN], ans;

void Build(int xx,int yy,int zz)
{
	d[xx] ++;
	e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy, e[tot].w = zz;
}

void Gauss()
{
	for (int i=1;i<n;++i)
	{
		int k = 0;
		for (int j=i;j<n;++j)
			if (fabs(f[j][i]) > fabs(f[k][i])) k = j;
		for (int j=i;j<=n+1;j++) swap(f[i][j], f[k][j]);
		for (int j=i+1;j<n;++j)
		{
			LD tmp = -f[j][i] / f[i][i];
			for (k=i;k<=n+1;++k) f[j][k] += f[i][k] * tmp;
		}
	}
	for (int i=n-1;i;i--)
	{
		for (int j=i+1;j<=n;++j) f[i][n+1] -= f[i][j] * a[j];
		a[i] = f[i][n+1] / f[i][i];
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		Build(x,y,z);
		if (x != y) Build(y,x,z);
	}
	for (int j=0;j<=30;++j)
	{
		memset(f,0,sizeof(f));
		memset(a,0,sizeof(a));
		for (int x=1;x<n;++x)
		{
			for (int i=head[x];i;i=e[i].ne)
			{
				if (e[i].w & (1<<j)) f[x][e[i].v] += 1, f[x][n+1] += 1;
				else f[x][e[i].v] -= 1;
			}
			f[x][x] += d[x];
		}
		Gauss();
		ans += a[1] * (1<<j);
	}
	printf("%.3lf\n",(double)ans);
	return 0;
}

3143: [Hnoi2013]游走

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define eps 1e-6
#define INF 0x3f3f3f3f
#define NN 505
#define MM 220000
#define LL long long
#define D double

D a[NN][NN],w[MM],ans;
int n,m,d[NN],x[MM],y[MM];

void Gauss()
{
	int now = 1, v;
	D t;
	for (int i=1;i<=n;++i)
	{
		for (v = now; v<=n ; ++v) if (fabs(a[v][i])>eps) break;
		if (v>n) continue;
		if (v!=now)
			for (int j=1;j<=n+1;++j) swap(a[v][j],a[now][j]);
		t = a[now][i];
		for (int j=1;j<=n+1;++j) a[now][j] /= t;
		for (int j=1;j<=n;++j)
		if (j!=now)
		{
			t = a[j][i];
			for (int k=1;k<=n+1;++k)
				a[j][k] -= t*a[now][k];
		}
		++now;
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&x[i],&y[i]);
		d[x[i]] ++, d[y[i]] ++;
	}
	for (int i=1;i<=m;++i)
	{
		a[x[i]][y[i]] -= 1.0/d[y[i]];
		a[y[i]][x[i]] -= 1.0/d[x[i]];
	}
	for (int i=1;i<n;++i) a[i][i] = 1, a[i][n] = 0;
	a[1][n] = 1;
	n--;
	Gauss();
	n++;
	for (int i=1;i<=m;++i) w[i] = a[x[i]][n] / d[x[i]] + a[y[i]][n] / d[y[i]];
	sort(w+1,w+1+m);
	for (int i=1;i<=m;++i) ans += (m-i+1) * w[i];
	printf("%.3lf\n",ans);
	return 0;
}

3503: [Cqoi2014]和谐矩阵

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <bitset>
using namespace std;

#define LL long long
#define N 45
LL bin[N][N];
int a[N][N],ans[N][N],n,m;

void Gauss()
{
	for (int i=1;i<=m;++i)
	{
		int j;
		for (j=i;j<=m && !a[j][i];++j);
		if (j>m) continue;
		if (j!=i)
			for (int k=i;k<=m+1;++k) swap(a[i][k],a[j][k]);
		for (int j=i+1;j<=m;++j)
			if (a[j][i])
			 	for (int k=i;k<=m+1;++k) a[j][k] ^= a[i][k];
	}
	for (int i=m;i;--i)
	{
		if (!a[i][i])
		{
			ans[1][i] = 1;
			continue;
		}
		for (int j=i+1;j<=m;++j) a[i][m+1] ^= (ans[1][j] * a[i][j]);
		ans[1][i] = a[i][m+1];
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i) bin[1][i] = 1ll<<(LL)(i-1);
	for (int i=2;i<=n+1;++i)
		for (int j=1;j<=m;++j)
			bin[i][j] = bin[i-1][j-1] ^ bin[i-1][j] ^ bin[i-1][j+1] ^ bin[i-2][j];
	for (int i=1;i<=m;++i)
		for (int j=1;j<=m;++j)
			a[i][j] = (bin[n+1][i] >> (j-1))&1;
	Gauss();
	for (int i=1;i<=m;++i) printf("%d ",ans[1][i]);	puts("");
	for (int i=2;i<=n;++i)
	{
		for (int j=1;j<=m;++j)
		{
			ans[i][j] = ans[i-1][j-1] ^ ans[i-1][j] ^ ans[i-1][j+1] ^ ans[i-2][j];
			printf("%d ",ans[i][j]);
		}
		puts("");
	}
	return 0;
}