`

【高斯消元 求期望】ZJUT 1423 地下迷宫 + ZJUT 1317 掷飞盘

阅读更多

KIDx的解题报告

1、地下迷宫
Description

由于山体滑坡,DK被困在了地下蜘蛛王国迷宫。为了抢在DH之前来到TFT,DK必须尽快走出此迷宫。此迷宫仅有一个出口,而由于大BOSS的力量减弱影响到了DK,使DK的记忆力严重下降,他甚至无法记得他上一步做了什么。所以他只能每次等概率随机的选取一个方向走。当然他不会选取周围有障碍的地方走。如DK周围只有两处空地,则每个都有1/2的概率。现在要求他平均要走多少步可以走出此迷宫
Input

先是一行两个整数N, M(1<=N, M<=10)表示迷宫为N*M大小,然后是N行,每行M个字符,'.'表示是空地,'E’表示出口,'D’表示DK,'X’表示障碍。
Output

如果DK无法走出或要超过1000000步才能走出,输出tragedy!,否则输出一个实数表示平均情况下DK要走几步可以走出迷宫,四舍五入到小数点后两位。

Sample Input

1 2
ED
3 3
D.X
.X.
X.E
Sample Output:

1.00
tragedy!

 

解析:E[i]表示从i点到达终点的期望步数

设i的临近可达点有a1, a2, a3,...,an

E[i]可以随机选一个临近点再走到终点

则平均步数E[i] = ((E[a1]+1) + (E[a2]+1) + ... + (E[an]+1)) / n;

化简得n*E[i] - E[a1] - E[a2] - ... - E[an] = n

设s为起点,e为终点:

显然对于e点有方程:E[e] = 0

然后对每个点都建立一个方程然后高斯消元求出E[s]即可

 

#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define M 101
#define eps 1e-9
int equ, var;
double a[M][M], x[M];

int r, c, has[15][15], sx, sy, ex, ey;
char map[15][15];
bool vis[15][15];
int xm[] = {-1, 0, 1, 0};
int ym[] = {0, 1, 0, -1};

int Gauss ()
{
	int i, j, k, col, max_r;
	for (k = 0, col = 0; k < equ && col < var; k++, col++)
	{
		max_r = k;
		for (i = k+1; i < equ; i++)
			if (fabs (a[i][col]) > fabs (a[max_r][col]))
				max_r = i;
		if (fabs (a[max_r][col]) < eps) return 0;		//无解
		if (k != max_r)
		{
			for (j = col; j < var; j++)
				swap (a[k][j], a[max_r][j]);
			swap (x[k], x[max_r]);
		}
		x[k] /= a[k][col];
		for (j = col+1; j < var; j++) a[k][j] /= a[k][col];
		a[k][col] = 1;
		for (i = 0; i < equ; i++) if (i != k)
		{
			x[i] -= x[k] * a[i][k];
			for (j = col+1; j < var; j++) a[i][j] -= a[k][j] * a[i][col];
			a[i][col] = 0;
		}
	}
	return 1;
}

struct point{
	int x, y;
};

void bfs ()
{
	int u, v, i, n, en = 1;
	memset (vis, false, sizeof(vis));
	memset (has, -1, sizeof(has));
	point ft, tp;
	ft.x = sx, ft.y = sy;
	queue<point> q;
	q.push (ft);
	//建立方程E(e) = 0
	has[ex][ey] = 0;			//设终点的方程编号为0
	a[0][0] = 1, x[0] = 0;
	has[sx][sy] = en++;		//设起点的方程编号为1
	//bfs建立其他点的方程
	while (!q.empty())
	{
		ft = q.front();
		q.pop();
		if (map[ft.x][ft.y] == 'E') continue;		//终点e的方程已经建立好
		u = has[ft.x][ft.y];
		n = 0;
		//n*E(u) - E(a1) - E(a2) -... = n
		for (i = 0; i < 4; i++)
		{
			tp.x = ft.x + xm[i];
			tp.y = ft.y + ym[i];
			if (tp.x < 0 || tp.y < 0 || tp.x >= r || tp.y >= c) continue;
			if (map[tp.x][tp.y] == 'X') continue;
			//邻近的点合法,得到该方程u变元v的系数
			if (has[tp.x][tp.y] > -1)
				v = has[tp.x][tp.y];
			else v = has[tp.x][tp.y] = en++;
			++n;
			a[u][v] = -1;
			//已访问过的点不需要再去建立方程
			if (vis[tp.x][tp.y]) continue;
			vis[tp.x][tp.y] = true;
			q.push (tp);
		}
		//u的系数以及方程右边的值
		a[u][u] = x[u] = n;
	}
	equ = var = en;
}

int main()
{
	int i, j;
	while (~scanf ("%d%d", &r, &c))
	{
		for (i = 0; i < r; i++) scanf ("%s", map[i]);
		for (i = 0; i < r; i++)
		{
			for (j = 0; j < c; j++)
			{
				if (map[i][j] == 'D') sx = i, sy = j;
				else if (map[i][j] == 'E') ex = i, ey = j;
			}
		}
		//初始化
		for (i = 0; i < M; i++) for (j = 0; j < M; j++) a[i][j] = 0;
		bfs ();
		if (Gauss()) printf ("%.2f\n", x[1]);
		else puts ("tragedy!");
	}
	return 0;
}

 

2、掷飞盘
Description

m个人位于正m边形的顶点上,彼此抛掷飞盘。他们共有两个飞盘,且开始时这两个飞盘位于相距为n的两个人的手中(相邻两个人相距为1,依此类推)。在每次抛掷时两个飞盘被同时抛出,飞盘都以1/2的概率被抛到掷飞盘的人左边相邻的人,1/2的概率被抛到右边相邻的人。此过程一直进行,直到两个飞盘被掷到同一个人手中,求此抛掷飞盘的游戏平均情况下(期望)会在抛掷几次后结束
Input

每行有两个整数m (2<m<=100),n (0 < n < m)。
Output

对每组数据m,n,输出平均所需步数(四舍五入,保留两位小数),如果有限步内不可能结束就输出INF。
Sample Input

3 1
4 1
Sample Output

4.00
INF

 

解析:设E[n]是距离从n变到0的期望步数,那么显然有:E[0] = 0

由于距离变成n的组合有:左左(距离不变),右右(距离不变),左右(由n-2扩大而来),右左(由n+2缩小而来)

于是对于E[n]有:

E[n] = [(E[n]+1) + (E[n]+1) + (E[n-2]+1) + (E[n+2]+1)] / 4

化简得:2*E[n] - E[n-2] - E[n+2] = 4

 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define M 105
#define eps 1e-9
int equ, var;
double a[M][M], x[M];

int Gauss ()
{
	int i, j, k, col, max_r;
	for (k = 0, col = 0; k < equ && col < var; k++, col++)
	{
		max_r = k;
		for (i = k+1; i < equ; i++)
			if (fabs (a[i][col]) > fabs (a[max_r][col]))
				max_r = i;
		if (fabs (a[max_r][col]) < eps) return 0;
		if (k != max_r)
		{
			for (j = col; j < var; j++)
				swap (a[k][j], a[max_r][j]);
			swap (x[k], x[max_r]);
		}
		x[k] /= a[k][col];
		for (j = col+1; j < var; j++) a[k][j] /= a[k][col];
		a[k][col] = 1;
		for (i = 0; i < equ; i++) if (i != k)
		{
			x[i] -= x[k] * a[i][k];
			for (j = col+1; j < var; j++) a[i][j] -= a[k][j] * a[i][col];
			a[i][col] = 0;
		}
	}
	return 1;
}

int has[M], k, f, m;    //has[i] 存的是 i状态的方程号,f=m/2

int cal (int n)    //得到合法的n,距离n不能小于0,也不能超过m的一半
{
	if (n < 0) n = -n;
	if (n > f) n = m - n;
	return n;
}

void dfs (int n)
{
	n = cal (n);
	if (has[n] >= 0) return ;
	has[n] = k++;
	dfs (n-2);
	dfs (n+2);
}

int main ()
{
	int n, i, j;
	while (~scanf ("%d%d", &m, &n))
	{
		f = m >> 1;
		n = cal (n);	//输入可能是非法的距离n,trick
		memset (has, -1, sizeof(has));
		k = 0;
		dfs (n);    //dfs遍历得到所有可达状态,每个状态都建立一条方程
		if (has[0] == -1)
		{
			puts ("INF");
			continue;
		}
		//高斯消元的初始化
		equ = var = k;
		for (i = 0; i < k; i++)
			for (j = 0; j < k; j++)
				a[i][j] = 0;
		//建图
		a[has[0]][has[0]] = 1; x[has[0]] = 0;		//E[0] = 0
		for (i = 1; i <= f; i++)
		{
			//2*E[n] - E[n-2] - E[n+2] = 4
			if (has[i] == -1) continue;	//i状态不可达  
			int u = has[i], v;
			a[u][u] = 2;			//E[n]
			v = has[cal(i+2)];		//E[n+2]
			--a[u][v];
			v = has[cal(i-2)];		//E[n-2]
			--a[u][v];
			x[u] = 4;				//方程右边
		}
		Gauss ();
		printf ("%.2f\n", x[has[n]]);		//输出E[n]
	}
    return 0;
}

 

2
3
分享到:
评论

相关推荐

    zjut acm 浙工大 OJ 355题 AC代码 by C++

    【描述】"浙江工业大学的OJ,zjut,355题代码全部亲测通过"表明作者或分享者对这道题目进行了实际测试,确认C++编写的代码不仅编译无误,而且在实际运行环境中也能正确处理各种输入,得到期望的输出结果。...

    ZJUT OJ ACM ICIP 1329圆周率代码

    ZJUT OJ ACM ICIP 1329圆周率代码

    (zjc zjut 杭电 浙大 工大)ACM题目整理

    【标题】"(zjc zjut 杭电 浙大 工大)ACM题目整理" 涉及的是ACM(国际大学生程序设计竞赛)的题目集合,这是一个全球性的编程竞赛,旨在提升大学生的算法设计、问题解决以及团队合作能力。ZJC、ZJUT、杭电、浙大、...

    application form-key lab-zjut.doc

    application form-key lab-zjut.doc

    基于Java的ZJUT JavaEE本科课件设计源码

    该项目是浙江工业大学(ZJUT)JavaEE本科课程课件的设计源码,包含459个文件,包括126个XML配置文件、123个Java源文件、73个JSP页面文件、29个属性文件、18个元数据文件、18个MF文件、15个Struts数据文件、10个PPT演示...

    ZJUT · C++ 课程设计.zip

    在"ZJUT · C++ 课程设计"中,学生可能会接触到以下几个关键知识点: 1. **基础语法**:这包括变量声明、数据类型(如int, float, char, bool)、运算符、流程控制(如if, switch, for, while循环)以及函数的使用...

    浙江工业大学精美PPT合集-TIHS IS MY ZJUT .pptx

    浙江工业大学精美PPT合集-TIHS IS MY ZJUT .pptx

    浙江工业大学第十九届“杭银理财杯”大学生程序 设计竞赛暨全国邀请赛ZJUT_Contest_Analysis.pdf

    浙江工业大学第十九届“杭银理财杯”大学生程序设计竞赛暨全国邀请赛ZJUT_Contest_Analysis.pdf 本资源摘要信息是对浙江工业大学第十九届“杭银理财杯”大学生程序设计竞赛暨全国邀请赛的题目分析报告。该报告涵盖...

    sql课内上机实验数据更新

    VALUES ('S78', '李迪', 'LD@zjut.edu.cn', 0, '男'); ``` - 插入子查询的结果:这种方式常用于从其他表或查询结果中获取数据进行插入。 2. **SELECT INTO语句**: - 用于创建一个新的表,并将查询结果插入其中...

    ZJUT原创教务管理系统学生账号获取.zip

    管理系统是一种通过计算机技术实现的用于组织、监控和控制各种活动的软件系统。这些系统通常被设计用来提高效率、减少错误、加强安全性,同时提供数据和信息支持。以下是一些常见类型的管理系统: ...

    乒乓球meanshift算法捕捉,实验三zjut

    使用经典meanshift算法跟踪运动中的乒乓球,实验效果较好,视频是老师上课给的

    RunCoderHang#ZJUT-Notes#1341-解密1

    就在大家乱成一团的时候,一个聪明的大臣看了半天之后发现只需要把每五个数字加起来,结果对 26 取模,然后用 0 对应 a,1 对应 b ...以此类推即可多组输

    RunCoderHang#ZJUT-Notes#1358-奇偶数分离1

    有一个整型偶数 n (2) ,你要做的是:先把 1 到 n 中的所有偶数从小到大输出,再把所有的偶数从小到大输出。第一行输出所有的奇数,第二行

    ZJUT_Scorer_Web:一个用于查询浙江工业大学平时成绩的Flask应用

    **ZJUT_Scorer_Web:一个基于Flask的浙江工业大学成绩查询应用** 这个名为“ZJUT_Scorer_Web”的项目是一个基于Python Flask框架的应用程序,专门设计用于查询浙江工业大学(Zhejiang University of Technology)的...

    Go.zjut.com:精弘网络导航

    "Go.zjut.com:精弘网络导航"很可能是一个由浙江理工大学(Zhejiang University of Technology)创建的网络平台,用于整合并提供各种学习资源、学术信息以及与学校相关的链接。这个平台可能对在校师生以及其他感兴趣...

    university.sql

    数据库系统概念第六版.sql文件

    实验1 使用虚拟机镜像文件导入部署CentOSopenGauss指导手册.pdf

    在当今信息技术飞速发展的时代,数据库技术作为信息系统的核心部分,扮演着极其重要的角色。openGauss作为一款高性能、高可靠性的开源关系型数据库,越来越受到业界的关注。本篇指导手册主要针对使用虚拟机镜像文件...

    数据库课程设计-高校成绩管理数据库系统的设计与实现

    高校成绩管理数据库系统的设计与实现 数据库技术课程设计报告 项目代码可以“搜索高校成绩管理数据库系统的设计与实现的项目代码”

    叶倩琳 201706061330 实验二1

    - 配置Web应用:为了创建名为`zjut`的Web应用,你需要在Tomcat的`webapps`目录下创建一个新的目录`zjut`。然后,将`Tomcat主目录/webapps/ROOT/WEB-INF`目录复制到`zjut`目录下。这样,`zjut`应用就会拥有一个基本...

    熵值法matlab代码-CPSC_zjut:CPSC2021的项目

    保守值法matlab代码第四届2021年中国生理信号挑战赛的Python示例代码 该存储库中有什么? 我们实现了基于阈值的分类器,该分类器使用ECG超前信号的样本熵系数(cosEn)作为特征。 这个简单的示例说明了如何格式化...

Global site tag (gtag.js) - Google Analytics