[数据结构与算法]【ICPC】2022 昆明站 G题 题解及推导思路

题目大意

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

题目链接

思路

我们设经过无数次操作后，编号为$i$的豆子前面豆子的数量期望是$cn{t}_i$。那么答案就是$\sum p_i?cn{t}_i$

那么怎么求$cn{t}_i$呢？我们就需要两两计算了。第$i$个豆子在第$j$个豆子之前，那么就说明我们在$i,j$之中，选择了$i$进行移动,那么概率就是$v_{i,j}=\frac{p_i}{p_i+p_j}$。
而$cn{t}_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;
}

阅读世界，共赴山海

423全民读书节，邀你共读