自动搬运

查看原文

来自洛谷，原作者为

	HPXXZYY 笑看世事似水变迁

搬运于2025-08-24 21:24:15，当前版本为作者最后更新于2019-10-05 10:46:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先，这是一道期望 dp 题。

我们按照 dp 的一般思路来思考这道题。

先考虑设计状态，我们记期望连续的 o 个数为 $\texttt{len}$，$f_i$ 表示以第 $i$ 个字符结尾的期望得分。

然后，我们考虑如何转移，很明显，转移需要分 o,x,? 考虑。

当当前字符为 o 时，$f_i=f_{i-1}+[(\texttt{len}+1)^2-\texttt{len}^2]=f_{i-1}+2 \times \texttt{len}+1$，而 $\texttt{len}=\texttt{len}+1$（注意先后顺序，先修改 $f_i$，再修改 $\texttt{len}$，下同）。

当当前字符为 x 时，$f_i=f_{i-1},\texttt{len}=0$。

前两个很显然，重点在 ? 的转移，我们发现 ? 为 x 和 o 的概率是一样的，所以 ? 的转移就相当于把 x 和 o 的转移合在一起，然后乘上概率 $50\%$，即除以 $2$。

也就是说，当当前字符为 ? 时，有：

$$f_i=f_{i-1}+\dfrac{[(\texttt{len}+1)^2-\texttt{len}^2]+0}{2} =f_{i-1}+\texttt{len}+0.5 $$

而 $\texttt{len}=\dfrac{\texttt{len}+1}{2}$，$(\texttt{len}+1)^2-\texttt{len}^2$ 和 $\texttt{len}+1$ 是 o 的转移，其他都是 x 的转移，注意 $\texttt{len}$ 的转移应是 $\texttt{len}=\dfrac{(\texttt{len}+1)+0}{2}$，也就是 $\texttt{len}=\dfrac{\texttt{len}+1}{2}$。

（主要思路来源于洛谷网校老师的课件）

【主要代码】：

const int N=3e5+100;
long double len,f[N];
string s;int l,i;
int main(){
	cin>>l>>s;
	for(i=1;i<=l;i++){
		switch(s[i-1]){
			case 'x':f[i]=f[i-1];len=0;break;
			case 'o':f[i]=f[i-1]+2*len+1;len++;break;
			case '?':f[i]=f[i-1]+len+0.5;len=(len+1)/2;break;
		}
	}
	printf("%.4Lf",f[l]);
//	注意long double的输出需要一个大写的L
	return 0;
}

当然，这道题可以做到空间复杂度 $O(1)$。

const int N=3e5+100;
char s[N];//用string慢 
long double ans,len;int n;
int main(){
	scanf("%d%s",&n,s+1);
	for(int i=1;i<=n;i++){
		if (s[i]=='o'){
			ans+=2*len+1;
			len++;
		}
		else if (s[i]=='x') len=0;
		else{
			ans+=len+0.5;
			len=(len+1)/2;
		}
	}
	printf("%.4Lf",ans);
	return 0;
}

【补充】：

1. 因为编者不想让某些人抄代码，又不想放一个反作弊系统影响其他人正常的阅读，所以编者决定，仅仅删去代码的头文件，主体部分全部是原汁原味的！这点请读者放心！

2. 关于概率 dp 的题，重点在你能不能想到如何转移，因为这种题目一般状态定义很简单。在考虑转移时，必要的话，需要一定的分类讨论或数学知识，所以数学学得好，对 OI 还是很有帮助的。

3. 关于万能头，现在网络上还存在很多争论，所以建议读者平时用用就好，考试还是要稳一点！