CF235B Let's Play Osu!

洛咕

双倍经验

三倍经验

题意:一个01串中每个长度为\(X\)的全1子串可贡献\(X^2\)的分数.给出\(n\)次操作的成功率\(p[i]\)(成功即为1,失败则为0),求期望分数.

分析:设\(a[i]\)表示前i位中第i位为1的长度的期望,\(a[i]=(a[i-1]+1)*p[i]\),即在前面\(i-1\)位的基础上长度加1,然后乘这一位为1的概率.设\(b[i]\)表示前i位中第i位为1的长度的平方的期望,因为\((i-1+1)^2=(i-1)^2+2*(i-1)+1\),所以\(b[i]=(b[i-1]+2*a[i-1]+1)*p[i].\)

但是我们最终的答案是要求出\(b[n]\),所以b数组的意义实际上应该是前i位的长度的期望,即还要考虑为0的情况,即\(b[i]=(b[i-1]+2*a[i-1]+1)*p[i]+b[i-1]*(1-p[i])\).上式拆括号后可以化简即得\(b[i]=b[i-1]+(2*a[i-1]+1)*p[i].\)

\(CF235B\)的代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e5+5;
double p[N],a[N],b[N];
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;++i)cin>>p[i];
    for(int i=1;i<=n;++i){
        a[i]=(a[i-1]+1)*p[i];
        b[i]=b[i-1]+(2*a[i-1]+1)*p[i];
    }
    printf("%.10lf\n",b[n]);
    return 0;
}

\(1365\)这道题是将直接给概率改成了给定一个字符串,串中有\(o,x,?\)三种字符,那么分别对应概率为\(1,0,0.5\)就好了.

    int n;cin>>n;string s;cin>>s;
    for(int i=0;i<n;++i){
        if(s[i]=='o')p[i+1]=1.000;
        else if(s[i]=='x')p[i+1]=0.000;
        else if(s[i]=='?')p[i+1]=0.500;
    }
    for(int i=1;i<=n;++i){
        a[i]=(a[i-1]+1)*p[i];
        b[i]=b[i-1]+(2*a[i-1]+1)*p[i];
    }
    printf("%.4lf\n",b[n]);

\(1654\)这道题是要求三次方的期望,那么把b数组只记录为1的情况,然后同理推出\(c\)数组就好了.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=100005;
double p[N],a[N],b[N],c[N];
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%lf",&p[i]);
    for(int i=1;i<=n;++i){
        a[i]=(a[i-1]+1)*p[i];
        b[i]=(b[i-1]+2*a[i-1]+1)*p[i];
        c[i]=c[i-1]+(3*a[i-1]+3*b[i-1]+1)*p[i];
    }
    printf("%.10lf\n",c[n]);
    return 0;
}