ICPC2022KunMingG

题目大意

有\(n\)个豆子排成一排,每个豆子有\(p_i\)的概率被选中.每次随机选一个豆子,将其放到最前面,每次操作的代价是该豆子前面豆子的个数,问在操作无限次后再操作一次,操作代价的期望是多少？

题目链接 ## 思路

我们设经过无数次操作后，编号为\(i\)的豆子前面豆子的数量期望是\(cnt_i\)。那么答案就是\(\sum p_i * cnt_i\)

那么怎么求\(cnt_i\)呢？我们就需要两两计算了。第\(i\)个豆子在第\(j\)个豆子之前，那么就说明我们在\(i,j\)之中，选择了\(i\)进行移动,那么概率就是\(v_{i,j} = \frac{p_i}{p_i+p_j}\)。 而\(cnt_i = \sum v_{j,i}\)

所以\(ans = \frac{p_i*p_j}{p_i+p_j}\)

而答案就是枚举所有的\(i,j\)，求和即可。

本题的思维方向在于，我们很难求出一个序列的出现的概率，所以难以对此进行期望，而求得两个豆子的相对关系较为容易，所以可以以此作为突破口。

\(E(x) = \sum p(x_i) * v(x_i)\)，其中\(p(x_i)\)为状态\(x_i\)出现的概率，\(v(x_i)\)为该状态对答案的贡献。只要所有的\(x_i\)能够完整的描述出所有可能状态，那么这么求期望就是正确的。

而假如我们知道了所有\(i,j\)豆子的左右关系，那么显然可以得到整个序列.所以，所有豆子的左右顺序，可以被作为状态。

代码

#include <cstdio>
#include <iostream>
using namespace std;

int n;
const int maxN = 105;

double p[maxN], ans;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%lf", &p[i]);
    for(int i = 1; i <= n; ++i) 
        for(int j = 1; j <= n; ++j)
            if(i != j)
                ans += p[i] * p[j] / (p[i] + p[j]);
    printf("%lf\n", ans);
    return 0;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/04/23/ICPC2022KunMingG/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！