自动搬运

查看原文

来自洛谷，原作者为

	IC0CI Huh

搬运于2025-08-24 22:25:33，当前版本为作者最后更新于2025-07-18 09:45:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题面分析

首先想，一个元素被翻转有两种情况：

• 该元素是错误的且在一次操作中作为顶部被取出。
• 该元素的前一个元素被翻转且该元素在一次操作中不作为顶部被取出。

我们设 $dp_i$ 表示第 $i$ 个元素被翻转的概率，$p_i$ 为 $i$ 元素在一个操作中作为顶部被取出的概率。

根据上面的两种情况可以得到式子

$$\begin{cases} dp_i = p_i + dp_{i - 1} \times (1-p_i) \qquad (s_i = \texttt{W}) \\ dp_i = dp_{i - 1} \times (1-p_i) \qquad (s_i = \texttt{C}) \end{cases} $$

再考虑 $p_i$ 怎么计算，手模一下发现：

$$p_1 = 1\\ p_2 = \frac{1}{n}\\ p_3 = \frac{1}{n} + \frac{\frac{1}{n}}{n - 1}\\ p_4 = \frac{1}{n} + \frac{\frac{1}{n}}{n - 1} + \frac{\frac{1}{n} + \frac{\frac{1}{n}}{n - 1}}{n - 2}\\ \cdots\\ p_k = \sum_{i = 1}^{k - 1} \frac{p_i}{n - i + 1} $$

关于具体实现

注意一下 int 转 double。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1e6 + 5;
string s;
double dp[N],p[N],ans;

signed main()
{
    cin >> s;
    int n = s.length();
    s = ' ' + s;
    p[1] = 1;
    double res = (double)1 / n;
    for(int i = 2;i <= n;i++) p[i] = res,res += (double)p[i] / (n - i + 1);
    for(int i = 1;i <= n;i++)
    {
        if(s[i] == 'W') dp[i] += p[i];
        dp[i] += dp[i - 1] * (1 - p[i]);
        if(s[i] == 'W') ans += 1 - dp[i];
        else ans += dp[i];
    }
    cout << fixed << setprecision(12) << ans;
    return 0;
}