HDU4870 Rating(概率)

时间:2022-03-13 04:52:46

第一场多校,感觉自己都跳去看坑自己的题目里去了,很多自己可能会比较擅长一点的题目没看,然后写一下其中一道概率题的题解吧,感觉和自己前几天做的概率dp的思路是一样的。下面先来看题意:一个人有两个TC的账号,一开始两个账号rating都是0,然后每次它会选择里面rating较小的一个账号去打比赛,每次比赛有p的概率+1分,有1-p的概率-2分,当然如果本身是<=2分的也就还是回到0分。然后问最后其中一个账号到达20分时需要打多少次比赛。

先考虑一场比赛的情况,定义dp[k]为当前为k分,要达到20分时的期望回合数。(令q=1-p)

那么显然有 dp[0]=1+p*dp[1]+q*dp[0] 化简得 dp[0]=1/p+dp[1]

dp[1]=1+p*dp[2]+q*dp[0] 化简得 dp[0]=1/p+1/p^2+dp[2]

我们令  dp[0]=tk+dp[k] 那么tk就表示由0状态到达k状态所需的期望回合数。那么显然如果是要到达20分的话,答案就是t20

然后我们看   dp[k]=1+p*dp[k+1]+q*dp[k-2]  代入dp[0]=dp[k]+tk 就有

dp[0]=1/p+1/p*t[k]-(1-p)/p*t[k-2]+dp[k+1]

所以  t[k+1]=1/p+1/p*t[k]-(1-p)/p*t[k-2]

边界条件是  t[0]=0,t[1]=1/p,t[2]=1/p+1/p^2

知道这些就可以递推出所有需要的t[k]了。

现在我们来看如果有两个账号怎么破。首先我们必然是 (0,0)->(0,1)->(1,1)->(1,2)->(2,2)->(2,3)->(3,3)...

(0,0)->(0,1)需要的期望回合数是t[1]-t[0].  (0,1)->(1,1)需要的期望回合数是 t[1]-t[0]

(1,1)->(1,2)需要的期望回合数是t[2]-t[1].  (1,2)->(2,2)需要的期望回合数是 t[2]-t[1].

....

(18,18)->(18,19)需要的期望回合数是t[19]-t[18]. (18,19)->(19,19)需要的期望回合数是t[19]-t[18].

(19,19)->(19,20)需要的期望回合数是t[20]-t[19]。

全部加起来的结果就是t[19]*2+t[20]-t[19].

所以最后的复杂度可以是线性的,而且理论上对于k个账号也是适用的,这样就可以避开了高斯消元的做法了。

#pragma warning(disable:4996)
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#define ll long long
#define maxn 10000
#define maxe 30000
#define inf 0x3f3f3f3f
using namespace std; double p; double t[25]; int main()
{
while (cin >> p){
t[0] = 0;
t[1] = 1 / p;
t[2] = 1 / p + 1 / (p*p);
for (int i = 3; i <= 20; i++){
t[i] = 1 / p + 1 / p*t[i - 1] - (1 - p) / p*t[i - 3];
}
double ans = t[19] * 2 + t[20] - t[19];
printf("%.6lf\n", ans);
}
return 0;
}

HDU4870 Rating(概率)的更多相关文章

  1. hdu4870 Rating (高斯消元或者dp)

    Rating Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submi ...

  2. HDU 4870 Rating 概率DP

    Rating Time Limit:5000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Statu ...

  3. HDU4870&colon;Rating&lpar;DP&rpar;

    Problem Description A little girl loves programming competition very much. Recently, she has found a ...

  4. hdu 4870 Rating

    题目链接:hdu 4870 这题应该算是概率 dp 吧,刚开始看了好几个博客都一头雾水,总有些细节理不清楚,后来看了 hdu 4870 Rating (概率dp) 这篇博客终于有如醍醐灌顶,就好像是第 ...

  5. HDU 4870 Rating &lpar;2014 多校联合第一场 J&rpar;&lpar;概率&rpar;

    题意: 一个人有两个TC的账号,一开始两个账号rating都是0,然后每次它会选择里面rating较小的一个账号去打比赛,每次比赛有p的概率+1分,有1-p的概率-2分,当然如果本身是<=2分的 ...

  6. HDU 4870 Rating(概率、期望、推公式) &amp&semi;&amp&semi; ZOJ 3415 Zhou Yu

    其实zoj 3415不是应该叫Yu Zhou吗...碰到ZOJ 3415之后用了第二个参考网址的方法去求通项,然后这次碰到4870不会搞.参考了chanme的,然后重新把周瑜跟排名都反复推导(不是推倒 ...

  7. 2014多校第一场J题 &vert;&vert; HDU 4870 Rating(DP &vert;&vert; 高斯消元)

    题目链接 题意 :小女孩注册了两个比赛的帐号,初始分值都为0,每做一次比赛如果排名在前两百名,rating涨50,否则降100,告诉你她每次比赛在前两百名的概率p,如果她每次做题都用两个账号中分数低的 ...

  8. Rating

    Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission ...

  9. hdu 4870 Rating&lpar;可能性DP&amp&semi;amp&semi;高数消除&rpar;

    Rating Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Su ...

随机推荐

  1. Android 采用Layout Inflater创建一个View对象

    接着上文<Android ListViewview入门>,本文使用android的Inflater来实现 在layouyt文件夹中新建一个list_item.xml的文件,添加如下代码: ...

  2. Apache Storm 与 Spark:对实时处理数据,如何选择【翻译】

    原文地址 实时商务智能这一构想早已算不得什么新生事物(早在2006年*中就出现了关于这一概念的页面).然而尽管人们多年来一直在对此类方案进行探讨,我却发现很多企业实际上尚未就此规划出明确发展思路 ...

  3. HDU 2669 第六周 I题

    Description The Sky is Sprite.  The Birds is Fly in the Sky.  The Wind is Wonderful.  Blew Throw the ...

  4. 随机森林——Random Forests

    [基础算法] Random Forests 2011 年 8 月 9 日 Random Forest(s),随机森林,又叫Random Trees[2][3],是一种由多棵决策树组合而成的联合预测模型 ...

  5. 【HDOJ】4902 Nice boat

    区间线段树.题目还不错. /* */ #include <iostream> #include <string> #include <map> #include & ...

  6. Javascript 精髓整理篇之二(函数篇)postby&colon;http&colon;&sol;&sol;zhutty&period;cnblogs&period;com

    今天总结的内容是javascript的function, 涉及到function顺便讲讲this. Function 是javascript的函数,也是js的执行单元.函数是JavaScript的一种 ...

  7. MySQL的常用SQL语句&period;md

    修改密码 这是常见的大家一般都要用的 首先     安装成功了打开cmd --> mysql -u root -p -->输入你的密码     修改mysql root用户密码    格式 ...

  8. Java高级开发工程师面试——多线程

    来自:Sanesee 链接:http://www.sanesee.com/article/java-engineer-interview-of-thread 1.进程和线程的区别? 进程是一个具有独立 ...

  9. 安装Office2010出现MSXML版本6&period;10&period;1129&period;0错误

      在键盘上按“win+R”组合键出现图图示界面后,输入“regsvr32 /u msxml6.dll”,点击“确定”. 出现图示显示后,点击“确定”,并同时去试试office是否能够安装了. 如果上 ...

  10. Postman runner参数化

    按照下面图片的顺序操作吧~ lets go 1.把要做参数化的字段的value用花括号标识起来,如:{{phone}} 2.准备一个csv的文件,把每次请求接口的参数按下图填写好,第一行写字段名称(p ...