嘴巴题8 BZOJ2318: Spoj4060 game with probability Problem
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 555 Solved: 273
[Submit][Status][Discuss]
Description
Alice和Bob在玩一个游戏。有n个石子在这里,Alice和Bob轮流投掷硬币,如果正面朝上,则从n个石子中取出一个石子,否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面,同样,Bob有q的概率投掷出他相投的一面。
现在Alice先手投掷硬币,假设他们都想赢得游戏,问你Alice胜利的概率为多少。
Input
第一行一个正整数t,表示数据组数。
对于每组数据,一行三个数n,p,q。
Output
对于每组数据输出一行一个实数,表示Alice胜利的概率,保留6位小数。
Sample Input
1
1 0.5 0.5
Sample Output
0.666667
HINT
数据范围:
1<=t<=50
0.5<=p,q<=0.99999999
对于100%的数据 1<=n<=99999999
Source
题解
\(f[i]\)表示剩i个石头,Alice先手获胜的概率
\(g[i]\)表示剩i个石头,Alice后手获胜的概率
不妨设他们都想选
有
\(f[i] = p \times g[i-1] + (1-p) \times g[i]\)
\(g[i] = q \times f[i-1] + (1-q) \times f[i]\)
不想选只需把\(p\)与\((1-p)\)互换,\(q\)与\((1-q)\)即可
这个式子看上去是不能推的,但观察发现下面式子左边是\(g[i]\),右边是\(f[i-1]\)和\(f[i]\),上面的式子右边是\(g[i]\)和\(g[i-1]\),左边是 $ g[i]$
所以把下边的式子待到上面去就能得到\(f[i]\)等于关于\(g[i-1]\),\(f[i-1]\)的多项式,\(f[i]\)就可以递推了
\(g[i]\)同理
那么如何确定想选还是不想选呢?
不难发现,如果\(f[i-1] > g[i-1]\),肯定是不想选的,Ailce想让Bob选成剩下\(i-1\)个,这样自己获胜概率大一些
反之,如果\(f[i-1] < g[i-1]\),肯定是想选的,同理
但是n很大,线性也做不了
不(题)难(解)发(上)现(说)n大了之后概率变动很小
既然是n的那就让n最大跑个1000W吧(或者卡时跑)
最新文章
- python一个注意的地方
- No.008 String to Integer (atoi)
- 【转】iOS设计模式之观察者模式
- Nginx 基本配置和日志分析
- Java命令参数说明
- Spring中各jar包的作用
- 用AndroidStudio发布Libs到Bintray jCenter
- Why Helm? - 每天5分钟玩转 Docker 容器技术(160)
- Flutter 即学即用系列博客——10 混淆
- (七) Keras 绘制网络结构和cpu,gpu切换
- swust oj 986
- C#多线程与并行编程方面的电子书,中英文版本
- EffectiveC++ 第1章 让自己习惯C++
- 超级牛皮的oracle的分析函数over(Partition by...) 及开窗函数 (转)
- JQuery学习二-字典操作
- 四张图带你了解Tomcat系统架构
- NMS和soft-nms算法
- linux /proc目录说明(访问内核数据结构,修改内核设置)
- linux每日命令(13):more命令
- 数据结构与算法之Stack(栈)的应用——用stack实现一个计算器-/bin/calc.dart
热门文章
- android Toast提示异常:java.lang.RuntimeException: Can&#39;t create handler inside thread that has not called
- Java学习 时间类 Period类与Duration类 / LocalDate类与Instant类 用法详解
- 【JZOJ4665】数列
- 廖雪峰Java16函数式编程-2Stream-2创建Stream
- 页面JS缓存问题解决方案
- MYSQL - database 以及 table 的增删改查
- 尚学linux课程---3、linux网络说明
- 现金贷平台下载量TOP100 涉逾30家P2P
- typedef void (*funcptr)(void) typedef void (*PFV)(); typedef int32_t (*PFI)();
- day 65 Django基础一之web框架的本质