BZOJ 3450: Tyvj1952 Easy

根据期望的线性性，可以求每个字符对答案的贡献
而每个字符对答案的贡献跟其期望后缀长度有关
设 \(l_i\) 表示以 \(i\) 结尾的连续 \(o\) 的期望长度
若 \(s_i = o\)，\(l_i = l_{i-1} + 1\)
若 \(s_i = x\)，\(l_i = 0\)
若 \(s_i = ?\)，\(l_i = \dfrac{l_{i-1} + 1}{2}\)
而当连续 \(o\) 长度为 \(x\) 时对答案的贡献是 \(x^2\)，长度变为 \(x+1\) 对答案的贡献是 \((x+1)^2\)
那么这个新加入的字符对答案的贡献就是 \((x+1)^2-x^2=2x+1\)
所以当 \(s_i = o\)，对答案的贡献是 \(2 \times l_{i-1} + 1\)
当 \(s_i = x\)，对答案的贡献是 \(0\)
当 \(s_i = ?\)，对答案的贡献是 \(\dfrac{2 \times l_{i-1} + 1}{2}\)

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define lp p << 1
#define rp p << 1 | 1
#define mid ((l + r) >> 1)
#define ll long long
#define db long double
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=b-1;i>=a;i--)
#define Edg int cnt=1,head[N],to[N*2],ne[N*2];void addd(int u,int v){to[++cnt]=v;ne[cnt]=head[u];head[u]=cnt;}void add(int u,int v){addd(u,v);addd(v,u);}
#define Edgc int cnt=1,head[N],to[N*2],ne[N*2],c[N*2];void addd(int u,int v,int w){to[++cnt]=v;ne[cnt]=head[u];c[cnt]=w;head[u]=cnt;}void add(int u,int v,int w){addd(u,v,w);addd(v,u,w);}
#define es(u,i,v) for(int i=head[u],v=to[i];i;i=ne[i],v=to[i])

const int N = 3e5 + 7;
db len[N];
char s[N];

int main() {
    int n;
    scanf("%d%s", &n, s + 1);
    db ans = 0;
    rep (i, 1, n + 1) {
        if (s[i] == 'o') {
            len[i] = len[i - 1] + 1;
            ans += 2 * len[i - 1] + 1;
        } else if (s[i] == 'x') {
            len[i] = 0;
        } else {
            len[i] = (len[i - 1] + 1) / 2.0;
            ans += (2 * len[i - 1] + 1) / 2.0;
        }
    }
    printf("%.4Lf\n", ans);
    return 0;
}

BZOJ 3450: Tyvj1952 Easy

原文：https://www.cnblogs.com/Mrzdtz220/p/12335297.html