题解 P1365 【WJMZBMR打osu! / Easy】

· · 题解

首先，这是一道期望 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. 关于万能头，现在网络上还存在很多争论，所以建议读者平时用用就好，考试还是要稳一点！