- 浏览: 316152 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
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; }
发表评论
-
HDU 3893 Drawing Pictures
2013-05-08 13:28 1644/* * [题意] * 有n个格子需要填色,有6 ... -
HDU 3483 A Very Simple Problem
2013-05-08 11:50 2511/* * [题意] * 输入n, x, m * ... -
HDU 3369 Robot
2013-05-07 10:35 1645/* * [题意] * 给出第一天是星期几,给出n ... -
HDU 3306 Another kind of Fibonacci
2013-05-04 13:54 1537/* * [题意] * 已知: * ... -
HDU 3221 Brute-force Algorithm
2013-05-04 13:31 1723/* * [题意] * 略 * [解题方法] ... -
HDU 2855 Fibonacci Check-up
2013-05-03 23:05 1432/* * [题意] * F(0) = 0; F(1 ... -
HDU 2294 Pendant
2013-05-01 16:50 1514/* * [题意] * 有k种珍珠,每种珍珠N个, ... -
HDU 2842 Chinese Rings
2013-04-30 10:57 1615/* * [题意] * 有n个灯,初始时是全亮的 ... -
HDU 2604 Queuing
2013-04-30 08:50 1442/* * [题意] * 对于只由数字1和0构成的 ... -
HDU 1588 Gauss Fibonacci
2013-04-29 10:38 1646/* * [题意] * g(i) = k*i + ... -
HDU 2254 奥运
2013-04-29 10:36 1344/* * [题意] * 给出n条道路,k个询问,每 ... -
【高斯消元 求期望】HDU 4418 Time travel
2012-10-01 21:10 4541KIDx的解题报告 题目链接:http://a ... -
【生成树计数】HDU 4305 Lightning
2012-08-16 15:45 2682KIDx的解题报告 题 ... -
HDU 1410 PK武林盟主
2011-10-02 16:28 1157KIDx 的解题报告 题目链接: http://acm.h ... -
【矩阵乘法+快速取幂模】HDU 1575 Tr A
2011-08-15 14:54 1582http://acm.hdu.edu.cn/showprobl ...
相关推荐
【描述】"浙江工业大学的OJ,zjut,355题代码全部亲测通过"表明作者或分享者对这道题目进行了实际测试,确认C++编写的代码不仅编译无误,而且在实际运行环境中也能正确处理各种输入,得到期望的输出结果。...
ZJUT OJ ACM ICIP 1329圆周率代码
【标题】"(zjc zjut 杭电 浙大 工大)ACM题目整理" 涉及的是ACM(国际大学生程序设计竞赛)的题目集合,这是一个全球性的编程竞赛,旨在提升大学生的算法设计、问题解决以及团队合作能力。ZJC、ZJUT、杭电、浙大、...
application form-key lab-zjut.doc
该项目是浙江工业大学(ZJUT)JavaEE本科课程课件的设计源码,包含459个文件,包括126个XML配置文件、123个Java源文件、73个JSP页面文件、29个属性文件、18个元数据文件、18个MF文件、15个Struts数据文件、10个PPT演示...
在"ZJUT · C++ 课程设计"中,学生可能会接触到以下几个关键知识点: 1. **基础语法**:这包括变量声明、数据类型(如int, float, char, bool)、运算符、流程控制(如if, switch, for, while循环)以及函数的使用...
浙江工业大学精美PPT合集-TIHS IS MY ZJUT .pptx
浙江工业大学第十九届“杭银理财杯”大学生程序设计竞赛暨全国邀请赛ZJUT_Contest_Analysis.pdf 本资源摘要信息是对浙江工业大学第十九届“杭银理财杯”大学生程序设计竞赛暨全国邀请赛的题目分析报告。该报告涵盖...
VALUES ('S78', '李迪', 'LD@zjut.edu.cn', 0, '男'); ``` - 插入子查询的结果:这种方式常用于从其他表或查询结果中获取数据进行插入。 2. **SELECT INTO语句**: - 用于创建一个新的表,并将查询结果插入其中...
管理系统是一种通过计算机技术实现的用于组织、监控和控制各种活动的软件系统。这些系统通常被设计用来提高效率、减少错误、加强安全性,同时提供数据和信息支持。以下是一些常见类型的管理系统: ...
使用经典meanshift算法跟踪运动中的乒乓球,实验效果较好,视频是老师上课给的
就在大家乱成一团的时候,一个聪明的大臣看了半天之后发现只需要把每五个数字加起来,结果对 26 取模,然后用 0 对应 a,1 对应 b ...以此类推即可多组输
有一个整型偶数 n (2) ,你要做的是:先把 1 到 n 中的所有偶数从小到大输出,再把所有的偶数从小到大输出。第一行输出所有的奇数,第二行
**ZJUT_Scorer_Web:一个基于Flask的浙江工业大学成绩查询应用** 这个名为“ZJUT_Scorer_Web”的项目是一个基于Python Flask框架的应用程序,专门设计用于查询浙江工业大学(Zhejiang University of Technology)的...
"Go.zjut.com:精弘网络导航"很可能是一个由浙江理工大学(Zhejiang University of Technology)创建的网络平台,用于整合并提供各种学习资源、学术信息以及与学校相关的链接。这个平台可能对在校师生以及其他感兴趣...
数据库系统概念第六版.sql文件
在当今信息技术飞速发展的时代,数据库技术作为信息系统的核心部分,扮演着极其重要的角色。openGauss作为一款高性能、高可靠性的开源关系型数据库,越来越受到业界的关注。本篇指导手册主要针对使用虚拟机镜像文件...
高校成绩管理数据库系统的设计与实现 数据库技术课程设计报告 项目代码可以“搜索高校成绩管理数据库系统的设计与实现的项目代码”
- 配置Web应用:为了创建名为`zjut`的Web应用,你需要在Tomcat的`webapps`目录下创建一个新的目录`zjut`。然后,将`Tomcat主目录/webapps/ROOT/WEB-INF`目录复制到`zjut`目录下。这样,`zjut`应用就会拥有一个基本...
保守值法matlab代码第四届2021年中国生理信号挑战赛的Python示例代码 该存储库中有什么? 我们实现了基于阈值的分类器,该分类器使用ECG超前信号的样本熵系数(cosEn)作为特征。 这个简单的示例说明了如何格式化...