题解：P6969 [NEERC 2016] Foreign Postcards

IC0CI · 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;
}