KIDx的解题报告
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4418
题意:一个人在数轴上来回走,以pi的概率走i步i∈[1, m],给定n(数轴长度),m,e(终点),s(起点),d(方向),求从s走到e经过的点数期望
解析:设E[x]是人从x走到e经过点数的期望值,显然对于终点有:E[e] = 0
一般的:E[x] = sum((E[x+i]+i) * p[i])(i∈[1, m])
(走i步经过i个点,所以是E[x+i]+i)
建立模型:高斯消元每个变量都是一个互不相同的独立的状态,由于人站在一个点,还有一个状态是方向!例如人站在x点,有两种状态向前、向后,不能都当成一种状态建立方程,所以要把两个方向化为一个方向从而使状态不受方向的影响
实现:
n个点翻过去(除了头尾两个点~~~)变为2*(n-1)个点,例如:
6个点:012345 ---> 0123454321
那么显然,从5开始向右走其实就是相当于往回走
然后方向就由两个状态转化成一个状态的,然后每个点就是只有一种状态了,对每个点建立方程高斯消元即可
bfs判断是否可以到达终点,顺便建立方程
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <math.h>
using namespace std;
#define M 205
#define eps 1e-8
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 (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;
}
//has[x]表示人在x点时的变量号,因为我们只用可达状态建立方程,所以需要编号
int has[M], vis[M], k, e, n, m;
double p[M], sum;
int bfs (int u)
{
memset (has, -1, sizeof(has));
memset (a, 0, sizeof(a)); //忘记初始化WA勒,以后得注意
memset (vis, 0, sizeof(vis));
int v, i, flg = 0;
queue<int> q;
q.push (u);
k = 0;
has[u] = k++;
while (!q.empty ())
{
u = q.front ();
q.pop ();
if (vis[u]) continue;
vis[u] = 1;
if (u == e || u == n-e) //终点有两个,你懂的~
{
a[has[u]][has[u]] = 1;
x[has[u]] = 0;
flg = 1;
continue;
}
//E[x] = sum ((E[x+i]+i) * p[i])
// ----> E[x] - sum(p[i]*E[x+i]) = sum(i*p[i])
a[has[u]][has[u]] = 1;
x[has[u]] = sum;
for (i = 1; i <= m; i++)
{
//非常重要!概率为0,该状态可能无法到达,如果还去访问并建立方程会导致无解
if (fabs (p[i]) < eps) continue;
v = (u + i) % n;
if (has[v] == -1) has[v] = k++;
a[has[u]][has[v]] -= p[i];
q.push (v);
}
}
return flg;
}
int main()
{
int t, s, d, i;
scanf ("%d", &t);
while (t--)
{
scanf ("%d%d%d%d%d", &n, &m, &e, &s, &d);
n = 2*(n-1);
sum = 0;
for (i = 1; i <= m; i++)
{
scanf ("%lf", p+i);
p[i] = p[i] / 100;
sum += p[i] * i;
}
if (s == e)
{
puts ("0.00");
continue;
}
//一开始向左,起点要变
if (d > 0) s = (n - s) % n;
if (!bfs (s))
{
puts ("Impossible !");
continue;
}
equ = var = k;
Gauss ();
printf ("%.2f\n", x[has[s]]);
}
return 0;
}
分享到:
相关推荐
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,以求在限定时间内提交正确的解决方案。这类竞赛有助于提升编程能力、算法思维以及问题解决技巧。 【标签】:“杭电”代表题目来源于杭州电子...
HDU1059的代码
hdu1001解题报告
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
hdu 1574 passed sorce
hdu2101AC代码
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
在HDU平台上,用户提交代码后,系统会自动进行编译和运行,并根据结果给出相应的状态,如“Accepted”(AC)、"Wrong Answer"(WA)、"Time Limit Exceeded"(TLE)等。 通过学习和分析"HDU最全ac代码",你可以学到...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...
【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...
hdu 1166线段树代码
母函数的应用通常涉及到高斯消元、欧几里得算法等数学技巧,能够帮助我们快速有效地求解这类问题。在实际编程过程中,要注意优化代码,避免不必要的计算,提高算法效率。对于这两个题目,虽然没有直接使用母函数的...