【ICPC】2022 昆明站 G题 题解及推导思路

题目大意

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

题目链接

思路

设经过无数次操作后，编号为 $i$ 的豆子前面豆子的数量期望是 $cnt_i$，则答案为 $\sum p_i \cdot cnt_i$。

若 $i$ 在第 $j$ 个豆子之前，那么就说明在 $i, j$ 之中，选择了 $i$ 进行移动，那么概率就是

$$v_{i,j} = \frac{p_i}{p_i+p_j}$$

而 $cnt_i = \sum_j v_{j,i}$，表示所有豆子 $j$ 排在 $i$ 前面的概率之和。

所以答案为

$$ans = \sum_{i \neq j} \frac{p_i \cdot p_j}{p_i+p_j}$$

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

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

期望公式 $E(x) = \sum p(x_i) \cdot v(x_i)$ 中，$p(x_i)$ 是 $x_i$ 出现的概率，$v(x_i)$ 是该状态的代价。若所有 $i, j$ 豆子的左右关系能够完整地描述出所有可能状态，那么这么求期望就是正确的。而假如我们知道了所有 $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;
}