目录
写在前面
唉唉数学大傻逼来写写典题。
题目来源:
- 【数学2-3】概率与统计
- xzy的概率期望题单
- vp
- Codeforces 标签筛选
Easy
- P1297:仅需考虑相邻位置的选项数量,即可计算每个位置的期望得分。
- P2111:设状态 \(f_{i, j}\) 表示考虑到前 \(i\) 道题,对了 \(j\) 道的概率,枚举每道题的情况转移即可。
- P6154:典中典之 DAG 随机游走求路径数量/长度的期望,直接倒着 DP 即可。
- P5104:第一个人抢钱期望显然即 \(\frac{2}{w}\),剩余钱数的期望即 \(w-\frac{w}{2}=\frac{w}{2}\),递推可知第 \(k\) 个人期望抢 \(\frac{w}{2^k}\),抢完后期望剩余 \(\frac{w}{2^k}\)。
- SP1026:赠券收集问题,记 \(f_i\) 表示得到 \(i\) 个不同面时的期望次数,则再得到一个不同的面的单次概率为 \(\frac{n-i+1}{n}\),显然是一个几何分布,则期望次数为 \(\frac{n}{n-i+1}\),答案即 \(\sum_{1\le i\le n} \frac{n}{n-i+1}\)。
- CF148D:直接记搜。
- CF453A:记随机变量 \(X\) 为最终点数最大值,即求 \(\sum_{1\le i\le m} i\times P(X=i)\),套路地转化:\(\sum_{i} P(X\ge i) = \sum_{i}1-P(X<i) = \sum_i 1 - \left(\frac{i-1}{m}\right)^n\)。
Medium
P1365、CF235B、P1654
典中典之 OSU 题。
对于 \(E(X)\) 很好维护直接加就行。
对于 \(E(X^2)\) 考虑拆贡献 \((X+1)^2 = X^2 + 2X + 1\),则对于一长度为 \(X\) 的全 1 串,若贡献为 \(X^2\),则长度每增加 1,\(X^2\) 就增加 \(2X + 1\);则考虑期望的性质,可将期望拆为 \(E((X+1)^2)=E(X^2) + 2E(X) + 1\),仅需考虑长度每增加 1 时,期望的增量 \(2E(X) + 1\) 即可。
考虑设 \(f_{i}\) 表示以 \(i\) 结尾的全 1 串,贡献为 \(X\) 时的期望贡献,则显然有 \(f_{i} = a_i\times (f_{i-1} + 1)\);设 \(g_i\) 表示考虑前 \(i\) 个位置,全 1 串贡献为 \(X^2\) 时的期望贡献之和。则由上分析,每个位置的贡献为 \(a_i\times (2 f_{i} + 1)\),则有:
\[g_{i} = \sum_{1\le j\le i} a_j\times (2f_{j} + 1) = g_{i - 1} + a_{i}\times (2f_{i} + 1) \]对于 \(E(X^3)\) 仅需额外维护 \(f'_{i}\) 表示以 \(i\) 结尾的全 1 串,贡献为 \(X^2\) 时的期望贡献,再类似地再拆 \(X^3\) 即可。
CF280C
从组合角度考虑,问题即考虑构造若干对应删点顺序的排列,求排列长度的期望。发现每个节点在排列中出现,对长度的贡献均为 1,根据期望的线性性,考虑把每个点的贡献拆开,仅需考虑每个节点出现在排列中的概率即可。
发现一个点 \(i\) 被选中,当且仅当它的祖先都在它之后被选,考虑到根到该节点的链长为 \(\operatorname{dep}_i\),则该点是这条链上第一个被选中的概率即 \(\frac{1}{\operatorname{dep}_i}\)。答案即:
\[\sum_{1\le i\le n}\frac{1}{\operatorname{dep}_i} \]P4550
这题和 SP1026(见 Easy)的关系,和上面 OSU 三道题一样。
先拆贡献,若 \(k\) 次得到所有邮票,则总代价为 \(\sum_{1\le i\le k} i = \frac{k(k+1)}{2}\),则 \(E(\sum_{1\le i\le k} i) = \frac{E(k^2) + E(k)}{2}\)。
求 \(E(k)\) 即 SP1026,对于 \(E(k^2)\) 同样考虑拆式子,若多获得一张新邮票的操作次数为 \(x\),则有:
\[E((k + x)^2) = E(k^2) + 2E(x)E(k) + E(x^2) \]由几何分布的知识有:
\[\begin{cases} E(x) = \frac{1}{p} = \frac{n}{n-i+1}\\ E(x^2) = \frac{2 - p}{p^2} = 2E^2(x) - E(x) \end{cases}\]记\(f_i\) 表示得到 \(i\) 个不同面时的期望次数,则分别考虑新出现一个面的贡献之和,有:
\[\begin{cases} f_i = \sum_{1\le j\le i} E(x)\\ E(k) = f_n\\ E(k^2) = \sum_{1\le i\le n} 2E(x)f_{i} + E(x^2) \end{cases} \]答案即:
\[\frac{E(k^2) + E(k)}{2} \]CF1042E
按权值升序排序后,考虑从第 \(i\) 个格子开始跳的期望步数,发现只能往权值更小(注意不能相等)的位置跳,贡献的增量即为 \(d = \sum (x_i - x)^2 + \sum (y_i - y)^2 = \sum (x_i^2 + y_i^2) - 2x_i\sum{x} - 2y_i\sum y + \sum(x^2 + y^2)\)。
发现两维分别考虑没有影响,于是分别维护权值更小的位置的数量 \(c\) 与 \(\sum x^2, \sum y^2, \sum x, \sum y\),则很容易计算获得的贡献的期望增量 \(\frac{d}{c}\),再考虑从权值更小的位置开始跳的期望步数之和的期望即可。
除了有点难调呃呃就是水题。
ICPC2024 online 2 - L
dztlb 大神秒了我看都没看,上去给大神写了个整数三分就过了。
显然两种操作不会交替使用,因为先进行操作 1 后进行操作 2,发现本次操作 1 实际上是没有贡献的。则一定是先不断进行操作 2 直至某个阈值 \(c\),再不断进行操作 1 直至 0。
于是考虑枚举进行若干次操作 2 后的阈值 \(c\),求得第一次操作使得小于该阈值的期望步数。一次操作的概率为 \(p = \frac{c}{t}\),发现这是个典型的 \(r=1\) 的帕斯卡分布,仅需考虑不小于 \(k(k\ge 0)\) 次操作后使大于阈值的概率,考虑级数求和可知期望步数即:
\[p + p(1 - p) + p(1-p)^2 + \cdots = \frac{1}{p} = \frac{t}{c} \]然后考虑操作 2 使得小于阈值后的取值在 \(0\sim c\) 中概率均等,则进行操作 1 的期望次数显然即:
\[\frac{1}{c+1}(0 + 1 + 2 + \cdots + c) = \frac{c-1}{2} \]则对于某个阈值 \(c\) 的期望操作次数即为:
\[\frac{c-1}{2} + \frac{t}{c} \]显然是个对勾函数的形式,可以直接解出或三分求得极值点。
P6046
妈的数据范围这么小
Hard
错误的 hard 根本做不出来。