BZOJ3450:Easy 题解

主要思路

一道非常好的题,适合我这种概率期望新手来搞。

首先,我们设\(dp[i]\)为以\(i\)结尾的期望长度。其次,我们发现\((x+1)^2-x^2=2x+1\),如果要求连续的根据字符的情况,有以下几种转移:

  1. 当\(str[i]=’o’\)时,那么\(dp[i] = dp[i-1]+1\),对答案的贡献为\(2dp[i-1]+1\)。
  2. 当\(str[i]=’x’\)时,不进行转移,对答案贡献为\(0\)。
  3. 当\(str[i]=’?’\)时,为\(o\)的概率为\(\frac{1}{2}\),转移为\(dp[i]=\frac{dp[i-1]+1}{2}\),对答案的贡献为\(\frac{2dp[i-1]+1}{2}\)。

乱搞即可。

代码

// BZ3450.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 300200;
int n;
char str[MAX_N];
long double dp[MAX_N], ans;
int main()
{
    scanf("%d%s", &n, str + 1);
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        switch (str[i])
        {
        case 'o':
            dp[i] = dp[i - 1] + 1;
            ans += 2 * dp[i - 1] + 1;
            break;
        case 'x':
            dp[i] = 0;
            break;
        case '?':
            dp[i] = 1.0 * (dp[i - 1] + 1) / 2.0;
            ans += 1.0 * (2.0 * dp[i - 1] + 1) / 2.0;
            break;
        }
    printf("%.4Lf", ans);
    return 0;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注