Sengxian's Blog

题目地址

描述

某一天 WJMZBMR 在打 osu~~~ 但是他太弱逼了，有些地方完全靠运气:(
我们来简化一下这个游戏的规则：
有 $n(n\le 300000)$ 次点击要做，成功了就是 o，失败了就是 x，分数是按 comb 计算的，连续 $a$ 个 comb 就有 $a^2$ 分，comb 就是极大的连续 o。
比如 ooxxxxooooxxx，分数就是 $2\times 2+4\times 4=4+16=20$。
Sevenkplus 闲的慌就看他打了一盘，有些地方跟运气无关要么是 o 要么是 x，有些地方 o 或者 x 各有 $50\%$ 的可能性，用 ? 号来表示。
那么 WJMZBMR 这场 osu 的期望得分是多少呢？

分析

这个题如果一段一段的处理，实际上并不是很好做。我们观察到 $(x + 1) ^ 2 - x ^ 2 = 2x + 1$，那么根据期望的线性性质，我们可以单独算每一个字符的贡献。我们设 $dp_i$ 为考虑前 $i$ 个字符的期望得分，$l_i$ 为以 $i$ 为结尾的 comb 的期望长度，$s_i$ 为第 $i$ 个字符，那么有 3 种情况：

1. $s_i = \texttt{o}$，则 $dp_i = dp_{i - 1} + l_{i - 1} \cdot 2 + 1$，$l_i = l_{i - 1} + 1$。
2. $s_i = \texttt{x}$，则 $dp_i = dp_{i - 1}$，$l_i = 0$。
3. $s_i = \texttt{?}$，则 $dp_i = dp_{i - 1} + \frac {l_{i - 1} \cdot 2 + 1} 2$，$l_i = \frac {l_{i - 1} + 1} 2$。

对于前两种情况，其实是非常直观的，对于第三种情况，实际上是求了一个平均长度。例如 ?oo，两种情况的长度 $l_i$ 分别是 $[0, 1, 2]$ 和 $[1, 2, 3]$，但是求了平均之后，长度 $l_i$ 变成了 $[0.5, 1.5, 2.5]$，这样由于我们的贡献是一个关于长度的一次多项式（$2x + 1$），所以长度平均之后，贡献也相当于求了一个平均，自然能够求得正确的得分期望。

思考：如果长度为 $a$ 的 comb 的贡献为 $a^3$，怎么做呢？
提示：由于 $(a + 1)^3 - a^3 = 3a^2 + 3a + 1$，所以我们需要维护 $a^2$ 和 $a$ 的期望，注意 $E_{a^2} \neq E^2_a$，所以维护 $a^2$ 的期望是必要的。这个题是：BZOJ 4318

代码

//  Created by Sengxian on 2016/11/28.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3450 期望 DP
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 300000 + 3;
char str[MAX_N];
double dp[MAX_N], len[MAX_N];
int n;

int main() {
    scanf("%d%s", &n, str);
    for (int i = 0; i < n; ++i)
        if (str[i] == 'o') {
            dp[i] = dp[i - 1] + len[i - 1] * 2 + 1;
            len[i] = len[i - 1] + 1;
        } else if (str[i] == 'x') {
            dp[i] = dp[i - 1];
            len[i] = 0;
        } else {
            dp[i] = dp[i - 1] + (len[i - 1] * 2 + 1) / 2;
            len[i] = (len[i - 1] + 1) / 2;
        }
    printf("%.4f\n", dp[n - 1]);
    return 0;
}