《P1365 WJMZBMR打osu! / Easy》

题目背景

原 维护队列 参见 P1903

题目描述

某一天 WJMZBMR 在打 osu，但是他太弱了，有些地方完全靠运气:(。

我们来简化一下这个游戏的规则

有 n 次点击要做，成功了就是o，失败了就是x，分数是按 combo 计算的，连续 a 个 combo 就有 a×a 分，combo 就是极大的连续o。

比如ooxxxxooooxxx，分数就是 2×2+4×4=4+16=20。

Sevenkplus 闲的慌就看他打了一盘，有些地方跟运气无关要么是o要么是x，有些地方o或者x各有 50% 的可能性，用?号来表示。

比如oo?xx就是一个可能的输入。 那么 WJMZBMR 这场 osu 的期望得分是多少呢？

比如oo?xx的话，?是o的话就是oooxx（9），是x的话就是ooxxx（4），期望自然就是 (4+9)/2=6.5 了。

输入格式

第一行一个整数 n（n≤3×105），表示点击的个数

接下来一个字符串，每个字符都是o，x，?中的一个

输出格式

一行一个浮点数表示答案

四舍五入到小数点后 4 位

如果害怕精度跪建议用 long double 或者 extended。

输入输出样例

输入 #1复制

4 ????

输出 #1复制

4.1250

代码实现：

#include <bits/stdc++.h> using namespace std; const int N = 3e5 + 10; char c[N + 10]; int m; long double dp[N]; int main () { scanf("%d" , &m); scanf("%s" , c + 1); dp[1] = 0; double len = 0.0; for(int i = 1 ; i <= m ; i ++) { if(c[i] == 'o') { dp[i] = dp[i - 1] - len * len + (len + 1.0) * (len + 1.0); len ++; } else if(c[i] == 'x') { len = 0.0; dp[i] = dp[i - 1]; } else if(c[i] == '?') { dp[i] = (dp[i - 1] - len * len + (len + 1.0) * (len + 1.0) + dp[i - 1]) / 2.0; len = (len + 1) / 2; } } printf("%.4Lf" , dp[m]); return 0; }