概率&期望

好久没写博客了，最近刷完了概率期望的专题，特地总结一下。

概率

(1) 基本概率知识
学过概率论课程的话，下面的都是基础了。
①条件概率： p(A|B)=p(AB)p(B) p ( A | B ) = p ( A B ) p ( B ) 。
P(A|B) P ( A | B ) 指B发生的条件下A发生的概率。
②全概率： p(A)=∑ni=1p(A|Bi) p ( A ) = ∑ i = 1 n p ( A | B i ) 。
全概率公式的关键在于划分样本空间，需要把所有可能情况不重复、不遗漏地进行分类，并计算出每个分类下事件A发生的概率。
③贝叶斯公式： p(Bi|A)=p(Bi)∗p(A|Bi)∑ni=1p(A|Bi) p ( B i | A ) = p ( B i ) ∗ p ( A | B i ) ∑ i = 1 n p ( A | B i ) 。
④ 古典概型和几何概型：古典概型是最基本的概率计算模型，适用于有限个随机事件的情况，而几何概型则适用于无限个随机事件的情况，几何概型的基本思想是把事件与几何区域对应，利用几何区域的度量来计算事件发生的概率。

(2) 练习

uva11722 Joining with Friend
传送门
题意：两人会面，第一个人去的时间在[t1, t2]中，第二个人去的时间在[s1, s2]中，两人会面成功的话，到达会面地点的时间差不能大于w，求两人成功会面的概率。

讯享网

分析：经典的几何概型，想必数学书上概率部分都有介绍此问题。
几何概型最大的一个特点是通过给定的条件可以将概率分布归于一个几何区域，而所有可能的分布情况也是一个几何区域。那么可以通过几何区域的度量来完成概率计算。常见的一般都是二维随机变量的分布。
本题中情况比较多，考虑需要仔细，计算会面成功的面积可以通过反面来考虑，把不符合的面积减去，每一种概率都不同。

#include <bits/stdc++.h> using namespace std; bool cal(int m, int l, int r) { return l <= m && m <= r; } double l, h, t1, t2, s1, s2, tota; double solve(double w) { double ux, dx, mly, mry; mly = t1 - w; mry = t2 - w; ux = s2 + w; dx = s1 + w; double are; if (cal(mly, s1, s2) && cal(ux, t1, t2)) { are = (s2 - mly) * (ux - t1) / 2.0; return w < 0 ? are : tota - are; } else if (cal(mly, s1, s2) && cal(mry, s1, s2)) { are = (2 * s2 - mly - mry) * l / 2.0; return w < 0 ? are : tota - are; } else if (cal(dx, t1, t2) && cal(mry, s1, s2)) { are = (t2 - dx) * (mry - s1) / 2.0; return w < 0 ? tota - are : are; } else if (cal(dx, t1, t2) && cal(ux, t1, t2)) { are = (ux + dx - 2 * t1) * h / 2.0; return w < 0 ? are : tota - are; } if (w < 0 && mry <= s1 && dx >= t2) return tota; if (w > 0 && mly >= s2 && ux <= t1) return tota; return 0; } int main() { int t, ca = 0; scanf("%d", &t); while (t--) { double w; scanf("%lf %lf %lf %lf %lf", &t1, &t2, &s1, &s2, &w); l = t2 - t1; h = s2 - s1; tota = l * h; double ar = tota - solve(w) - solve(-w); printf("Case #%d: %.8f\n", ++ca, ar / tota); } return 0; } 

xtu 1244 Gambling
传送门
题意：袋子中有a个红球，b个绿球，c个蓝球，不放回地取球，如果某一种球取完了，则游戏结束，先取完红球得一等奖，先取完绿球得二等奖，先取完蓝球得三等奖。求得一等、二等、三等奖的概率。

分析：这题一开始是直接概率dp的。。。然而根本不可做，因为abc范围太大，都达到了1e3，且题目输出的是一个分子/分母的形式，交上去都直接t掉了。。。
要解决还是需要一定的数学基础的。考虑先取完红球的情况，所有可能情况无外乎两种：
(1) 先取完红，在取完绿球，在取完蓝球；
蓝球是最后一个取完的概率是 ca+b+c c a + b + c ，这个概率论课上讲过一个结论，第n次取得蓝球的概率和第一次取得蓝球的概率是相同的，这个可以通过多重集排列证明。
还需要保证绿球晚于红球取完，而绿球在红球和绿球的排列中是最后一个的概率是 ba+b b a + b ，很容易知道这两者的交集包含了所有的先取完红，在取完绿球，在取完蓝球的情况，所以第一种情况的概率就是两者相乘。
(2) 先取完红，在取完绿球，在取完蓝球；
与上面类似，概率为 ba+b+c∗ca+c b a + b + c ∗ c a + c 。
那么先取完红球的概率就是 bc(a+b+c+a)(a+b+c)∗(a+c)∗(a+b) b c ( a + b + c + a ) ( a + b + c ) ∗ ( a + c ) ∗ ( a + b ) 。
先取完绿球和先取完蓝球的概率同理可得分别为 ac(a+b+c+b)(a+b+c)∗(b+c)∗(a+b)，ab(a+b+c+c)(a+b+c)∗(b+c)∗(a+c) a c ( a + b + c + b ) ( a + b + c ) ∗ ( b + c ) ∗ ( a + b ) ， a b ( a + b + c + c ) ( a + b + c ) ∗ ( b + c ) ∗ ( a + c ) 。
从本题可以看出，在一些概率的计算问题中只要选取合适的分类，那么计算也会相应变得清楚和简单了。培养自己多角度思考问题和观察问题的能力还是很重要的。

讯享网#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { LL a, b, c; while (~scanf("%I64d %I64d %I64d", &a, &b, &c)) { LL sum = a + b + c; LL fraa = b * c * (sum + a), numa = sum * (a + b) * (a + c); LL frab = a * c * (sum + b), numb = sum * (a + b) * (b + c); LL frac = b * a * (sum + c), numc = sum * (c + b) * (a + c); LL ga = __gcd(fraa, numa), gb = __gcd(frab, numb), gc = __gcd(frac, numc); printf("%I64d/%I64d %I64d/%I64d %I64d/%I64d\n", fraa / ga, numa / ga, frab / gb, numb / gb, frac / gc, numc / gc); } return 0; } 

csu 1917 There is no SSR
传送门
题意：阴阳师抽奖，得到R的概率为p，得到SR的概率为1-p，求抽m次奖连续获得n个SR的概率。

分析：多校时这题题意都没看懂。。。in succession是连续的意思，本蒟蒻一眼看上去以为是成功得到n个SR的概率。。。。。
可以反过来考虑，求出不会连续得到n个SR的概率，这个利用dp便可以很简单的求出了，令dp[i]为抽i次奖不会连续得到n个SR的概率，