跳转至

WJMZBMR打osu!/easy

题目链接

题目链接

题解

令\(f[i]\)表示到第i个字符的期望长度,\(g[i]\)表示以第i个字符为结尾的连续o串长度的期望,此时就有三种情况

  • \(s[i] == o 时, f[i] = f[i - 1] + (g[i-1] + 1)^2 -g[i-1]^2 = f[i - 1] + 2 * g[i - 1] + 1,g[i] = g[i -1] + 1\)
  • \(当s[i] == x时,g[i] = 0,f[i] = f[i - 1]\)
  • \(当s[i] == ?时,f[i] = f[i] + (2 * g[i - 1] + 1.0) * p,g[i]=(g[i - 1] + 1)*p(p为?为o的概率，这题是0.5)\)

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
double f[N], g[N];
char s[N];
int main() {
    int n;
    cin >> n >> s + 1;
    for(int i = 1; i <= n; i ++ ) {
        if(s[i] == 'o') {
            g[i] = g[i - 1] + 1.0;
            f[i] = f[i - 1] + 2.0 * g[i - 1] + 1.0;
        } else if(s[i] == 'x') {
            g[i] = 0;
            f[i] = f[i - 1];
        } else if(s[i] == '?') {
            g[i] = (g[i - 1] + 1.0) / 2.0;
            f[i] = f[i - 1] + (2.0 * g[i - 1] + 1.0) / 2.0;
        }
    }
    printf("%.4lf", f[n]);
    return 0;