题目背景
原 维护队列 参见 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; }
