Alice和Bob赌糖果

[编程题]Alice和Bob赌糖果

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

Alice和Bob赌糖果。规则是这样的：Alice从[ l, r]中随机抽一个数，Bob从[ L, R]中随机抽一个数，谁抽的数大谁就赢，输的一方给另一方1颗糖（平局不用给糖），他们会一直赌下去直到有一方没有糖果为止。

Alice有n颗糖果，Bob有m颗糖果，求Alice将Bob的糖果赢完的概率。

输入描述:

第一行3个整数n, l, r。
第二行3个整数m, L, R。

输出描述:

Alice将Bob糖果赢完的概率，结果保留5位小数。

示例1

输入

1 1 3
1 1 2

输出

0.75000

示例2

输入

0 1 100
1 1 100

输出

0.00000

备注:

0 <= n,m <=1e5,n+m > 0
1 <= l <= r <= 100,1 <= L <= R <= 100

算法知识视频讲解

louhc

发表于 2019-11-23 09:00:42

思路首先,我们可以忽略平局的情况.因为如果我们过滤掉平局的情况,最终结果仍然不变. 我们记Alice赢的概率为 ,输的概率为 , 当Alice手头有颗糖果时,最终获胜的概率是 . 然后我们就可以列出转移方程: 很明显这玩意不能直接转移,如果比较小的时候我们可以高斯消元解方程,但是这展开全文

稻云麦花

发表于 2019-09-26 19:57:51

首先，需要计算单局Alice获胜的概率p. 方法1 这个由于l,r,L,R都是非常小的范围，所以，直接枚举每一个点，统计获胜点和失败点的个数即可求得。方法2 如果l,r,L,R并不是100以内，那么需要通过皮克定理，线性规划，计算获胜区域内的整点数目和失败区域的整点数目。l和L的大小关系3种，同理展开全文