Pluto_Rabbit's Blog

蒟蒻妹纸一枚,轻拍

【学习】高斯消元

Jacinth posted @ 2016年6月15日 14:16 in Lerning with tags 学习 算法 Learning 高斯消元 bzoj , 973 阅读

蒟蒻掉rating辣

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

问题是新高一已经来了

于是被碾炸惹呜呜呜

20160612终于压线上了紫名

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

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

哎。。

 

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

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

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

 

No. 算法 状态
1013 高斯消元 Accepted
1923 高斯消元 Accepted
2337 期望高斯消元 Accepted
3143 期望高斯消元 Accepted
3503 异或高斯消元 Accepted

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坑

对于每一位 令f[i]为从i节点出发到n的期望值
对于每条出边,如果这条边边权为1,那么$f[x]+= \frac {f[y]}{d[x]}$ 否则$f[x]+=\frac{(1-f[y])}{d[x]}$ 其中d[x]表示x的度数
特殊地,f[n]=1
然后跑一跑Gauss应该就bingo辣
#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]游走

一副期望DP都好像的赶脚哎
(期望次数大的标号应该小QAQ)
#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]和谐矩阵

这题题解都看了老久感觉有点尴尬了
这种不一般的方法真高大上%%% 一脸懵逼.jpg
感觉这比纯板子题高大上多了 (虽然不会哎T^T
#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;
}

 

Avatar_small
Grade 5 Result dinaj 说:
2022年9月03日 01:37

Government of the People’s Republic of Bangladesh, Directorate of Primary Education (DPE), is going to announce PSC Result 2022 in student wide on 30th December 2022 for all divisional Grade 5 exam result with Ebtedayee Result 2022 for annual final terminal examinations, The Primary School Certificate Examination Result 2022 will be announced for both of General and Madhrsah students in division wise to all education board known as Prathomik Somaponi Result 2022. Grade 5 Result dinajpur BoardThe DPE has successfully conducted the class 5th grade PSC and Ebtedayee Examination tests from 17th to 24th November 2022 under all education boards of Dhaka, Chittagong, Comilla, Rajshahi, Sylhet, Barisal, Jessore, Dinajpur and Madrasah Board, and the DPE Grade-5 exams are successfully conducted at all 7,194 centers across the country.


登录 *


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