Record - Nov. 26st, 2020

首页

关于

笔记

文章

友链

Record - Nov. 26st, 2020 - Training REC

cirnovsky / Nov 27, 2020

Topic：高斯消元

Problems	States
#8799. 熄灯游戏	AC
#15778. Dotp 驱逐猪猡	AC
#17270. 博物馆	AC
#16337. XOR 和路径	IP

Problem. 1 Junior - Formula

用 $m_{i,j}$ 表示答案， $a_{i,j}$ 表示原矩阵。

则方程为 $(m_{i,j}+m_{i-1,j}+m_{i+1,j}+m_{i,j-1}+m_{i,j+1}+a_{i,j})\operatorname{bitand}1=0$ 。

变下形高消即可。

#include <cstdio>
#include <cstring>

const int MAXN = 50;

template<typename _T> void swapp ( _T &x, _T &y ) { _T w = x; x = y; y = w; }

int mat[MAXN][MAXN], ori[MAXN][MAXN];
int wax[5] = { 0, 0, 0, 1, -1 }, way[5] = { 0, 1, -1, 0, 0 };

int has ( const int x, const int y ) { return ( x - 1 ) * 6 + y; }

void Eradicate () {
	for ( int i = 1; i <= 30; ++ i ) {
		int p = i;
		for ( int j = i + 1; j <= 30; ++ j ) {
			if ( mat[p][i] < mat[j][i] )	p = j;
		}
		for ( int j = 1; j <= 31; ++ j )	swapp ( mat[p][j], mat[i][j] );
		for ( int j = 1; j <= 30; ++ j ) {
			if ( i == j || ! mat[j][i] )	continue;
			for ( int k = 1; k <= 31; ++ k )	mat[j][k] ^= mat[i][k];
		}
	}
}

int main () {
	int cases; scanf ( "%d", &cases );
	for ( int _ = 1; _ <= cases; ++ _ ) {
		memset( mat, 0, sizeof ( mat ) );
		for ( int i = 1; i <= 5; ++ i ) {
			for ( int j = 1; j <= 6; ++ j )	scanf ( "%d", &ori[i][j] );
		}
		for ( int i = 1; i <= 5; ++ i ) {
			for ( int j = 1; j <= 6; ++ j ) {
				for ( int k = 0; k < 5; ++ k ) {
					int nxi = i + wax[k], nxj = j + way[k];
					if ( nxi >= 1 && nxi <= 5 && nxj >= 1 && nxj <= 6 )	mat[has ( i, j )][has ( nxi, nxj )] = 1;
				}
				mat[has ( i, j )][31] = ori[i][j];
			}
		}
		Eradicate ();
		printf ( "PUZZLE #%d\n", _ );
		for ( int i = 1; i <= 5; ++ i ) {
			for ( int j = 1; j <= 6; ++ j )	printf ( "%d ", mat[has ( i, j )][31] );
			putchar ( '\n' );
		}
	}
	return 0;
}

Problem. 2 Junior / Senior - Formula

直接设概率做不来的样子。。。

问了一下懂行的人发现需要设期望。

设 $f_{u}$ 为节点经过 $u$ 的期望次数，设 $E$ 为边集， $d_{u}$ 表示节点 $u$ 的度。

f_{u}=(1-\frac{p}{q})\sum_{(u,v)\in E}\frac{1}{d_{v}}f_{v}

因为有环，所以需要高斯消元一下。

那么在每个节点爆炸的概率即为 $f_{u}\times\frac{p}{q}$ 。

总结一下，这道题告诉了我不仅是期望可以回归本质用概率搞，概率也可以用期望来整。

#include <cstdio>

const int MAXN = 300 + 5, MAXM = MAXN * MAXN;

template<typename _T> _T ABS ( const _T x ) { return x > 0 ? x : -x; }
template<typename _T> void swapp ( _T &x, _T &y ) { _T w = x; x = y; y = x; }

struct GraphSet {
	int to, nx;
	GraphSet ( int T = 0, int N = 0 ) { to = T, nx = N; }
} as[MAXM];

int n, m, p, q, cnt, d[MAXN], begin[MAXN];
double mat[MAXN][MAXN], sol[MAXN], boomed, transed;

void makeEdge ( const int u, const int v ) { as[++ cnt] = GraphSet ( v, begin[u] ), begin[u] = cnt; }

void Eradicate () {
	for ( int i = 1; i <= n; ++ i ) {
		int p = i;
		for ( int j = i + 1; j <= n; ++ j ) {
			if ( ABS ( mat[p][i] ) < ABS ( mat[j][i] ) )	p = j;
		}
		for ( int j = 1; j <= n + 1; ++ j )	swapp ( mat[p][j], mat[i][j] );
		for ( int j = 1; j <= n; ++ j ) {
			if ( i == j )	continue;
			double d = mat[j][i] / mat[i][i];
			for ( int k = 1; k <= n + 1; ++ k )	mat[j][k] -= mat[i][k] * d;
		}
	}
	for ( int i = 1; i <= n; ++ i )	sol[i] = mat[i][n + 1] / mat[i][i];
}

int main () {
	scanf ( "%d%d%d%d", &n, &m, &p, &q );
	for ( int i = 1, u, v; i <= m; ++ i ) {
		scanf ( "%d%d", &u, &v );
		makeEdge ( u, v ), makeEdge( v, u );
		d[u] ++, d[v] ++;
	}
	boomed = ( double )p / ( double )q;
	transed = 1 - boomed;
	for ( int _ = 1; _ <= n; ++ _ ) {
		int u = _;
		mat[u][u] = 1;
		for ( int i = begin[u]; i; i = as[i].nx ) {
			int v = as[i].to;
			mat[u][v] -= transed / d[v];
		}
	}
	mat[1][n + 1] = 1;
	Eradicate ();
	for ( int i = 1; i <= n; ++ i )	printf ( "%.9lf\n", sol[i] * boomed );
	return 0;
}

Problem. 3 Junior / Senior - Formula & Thinking

设 $f_{u,v}$ 表示同一时刻 Petya 在点 $u$ ，Vasya 在点 $v$ 的概率。

f_{u,v}=p_{u}p_{v}f_{u,v}+\sum_{(u,u')\in E}\sum_{(v,v')\in E}\frac{1-p_{u'}}{d_{u'}}\frac{1-p_{v'}}{d_{v'}}f_{u',v'}+\sum_{(u,u')\in E}p_{v}\frac{1-p_{u'}}{d_{v'}}f_{u',v}+\sum_{(v,v')\in E}p_{u}\frac{1-p_{v'}}{d_{v'}}f_{u,v'}

完了。

#include <cstdio>

const double EPS = 1e-8;
const int MAXN = 500 + 5, MAXM = MAXN * MAXN;

template<typename _T> _T ABS ( const _T x ) { return x > 0 ? x : -x; }
template<typename _T> void swapp ( _T &x, _T &y ) { _T w = x; x = y; y = w; }

struct GraphSet {
	int to, nx;
	GraphSet ( int T = 0, int N = 0 ) { to = T, nx = N; }
} as[MAXM];

int n, m, s, t, cnt, upper, d[MAXN], begin[MAXN];
double mat[MAXN][MAXN], p[MAXN];

int has ( const int x, const int y ) { return ( x - 1 ) * n + y; }
void makeEdge ( const int u, const int v ) { as[++ cnt] = GraphSet ( v, begin[u] ), begin[u] = cnt; }

void Eradicate () {
	for ( int i = 1; i <= upper; ++ i ) {
		int p = i;
		for ( int j = i + 1; j <= upper; ++ j ) {
			if ( ABS ( mat[p][i] ) < ABS ( mat[j][i] ) )	p = i;
		}
		for ( int j = i + 1; j <= upper + 1; ++ j )	swapp ( mat[p][j], mat[i][j] );
		if ( ABS ( mat[i][i] ) < EPS )	continue;
		for ( int j = 1; j <= upper; ++ j ) {
			if ( i == j )	continue;
			double d = mat[j][i] / mat[i][i];
			for ( int k = 1; k <= upper + 1; ++ k )	mat[j][k] -= mat[i][k] * d;
		}
	}
	for ( int i = 1; i <= upper; ++ i )	mat[i][upper + 1] /= mat[i][i];
}

int main () {
	scanf ( "%d%d%d%d", &n, &m, &s, &t ), upper = n * n;
	for ( int i = 1, u, v; i <= m; ++ i ) {
		scanf ( "%d%d", &u, &v );
		makeEdge ( u, v ), makeEdge ( v, u );
		d[u] ++, d[v] ++;
	}
	for ( int i = 1; i <= n; ++ i )	scanf ( "%lf", &p[i] );
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = 1; j <= n; ++ j ) {
			if ( i == j )	mat[has ( i, j )][has ( i, j )] = 1;
			else	mat[has ( i, j )][has ( i, j )] = 1 - p[i] * p[j];
			for ( int ii = begin[i]; ii; ii = as[ii].nx ) {
				int u = as[ii].to;
				for ( int iii = begin[j]; iii; iii = as[iii].nx ) {
					int v = as[iii].to;
					if ( u == v )	continue;
					mat[has ( i, j )][has ( u, v )] = -( 1 - p[u] ) / d[u] * ( 1 - p[v] ) / d[v];
				}
			}
			for ( int ii = begin[i]; ii; ii = as[ii].nx ) {
				int u = as[ii].to;
				if ( u == j )	continue;
				mat[has ( i, j )][has ( u, j )] = -p[j] * ( 1 - p[u] ) / d[u];
			}
			for ( int ii = begin[j]; ii; ii = as[ii].nx ) {
				int v = as[ii].to;
				if ( i == v )	continue;
				mat[has ( i, j )][has ( i, v )] = -p[i] * ( 1 - p[v] ) / d[v];
			}
		}
	}
	mat[has ( s, t )][upper + 1] = 1;
	Eradicate ();
	for ( int i = 1; i <= n; ++ i )	printf ( "%.9lf ", mat[has ( i, i )][upper + 1] );
	return 0;
}