#include<bits/stdc++.h>
#define il inline
#define ll long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
using namespace std;
int n,cnt;
char s;
double f[2],g[2];
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    For(i,1,n){
        cin>>s;
        if(s=='x') f[cnt^1]=f[cnt],g[cnt^1]=0;
        else if(s=='o') f[cnt^1]=f[cnt]+2*g[cnt]+1,g[cnt^1]=g[cnt]+1;
        else f[cnt^1]=f[cnt]+g[cnt]+0.5,g[cnt^1]=g[cnt]/2+0.5;
        cnt^=1;
    }
    printf("%.4lf",f[cnt]);
    return 0;
}

题意简述

• 给定一个长度为 $n$ 字符串，由 o、x、? 组成。字符串中每个字符 ?，分别有 $50\%$ 的概率变成 o 或 x。

• 字符串变化至不存在字符 ? 时，即可计算它的得分。对于每段连续的字符 o，对得分的贡献为 o 个数的平方。

• 求最终得分的期望值。

• $1\leq n\leq 3\times 10^5$

题目分析

我们尝试遍历整个字符串，递推出答案。

但是如果遇到 o 字符，这时候就无法递推到这一位为止的期望得分了。

所以我们再维护一个变量 $t$ 表示当前连续的 o 的期望数量。然后对每种字符分类讨论：

• 对于 x 字符，这时候连续 o 的期望数量 $t$ 就要清零，而且答案不会受到影响。

• 对于 o 字符，原本这一段连续 o 对得分的期望贡献为 $t^2$，现在变成了 $(t+1)^2$，这样便需要给当前答案加上 $(t+1)^2-t^2$，并且 $t$ 也要加上 $1$。

• 对于 ? 字符，由于概率都是 $50\%$，故只需要把以上两种情况求平均值即可。即答案加上 $\dfrac 12[(t+1)^2-t^2]$，$t$ 变为 $\dfrac {t+1}2$。

代码

#include<bits/stdc++.h>
using namespace std;

double t,ans; 
//t表示当前连续o的个数的期望值，
//ans表示当前得分的期望值 
string s; int n;

int main(){
	cin>>n>>s; s=' '+s;
	for(int i=1;i<=n;i++)
		if(s[i]=='o')ans+=(t+1)*(t+1)-t*t,t++;
		else if(s[i]=='x')t=0;
		else ans+=((t+1)*(t+1)-t*t)/2,t=(t+1)/2;
	printf("%.4lf",ans);
	return 0;
}