洛谷 1365 WJMZBMR打osu! / Easy

【题解】

　　期望题。设f[i]为到第i位的期望得分，g[i]为到第i位的期望combo.

　　若s[i]为o，f[i]=f[i-1]+2*g[i-1]+1(也就是f[i]-f[i-1]=(g[i-1]+1)^2-g[i-1]^2), g[i]=g[i-1]+1;

　　若s[i]为x，f[i]=f[i-1], g[i]=0;

　　若s[i]为?，f[i]=0.5*f[i-1]+0.5*(f[i-1]+2*g[i-1]+1)=f[i-1]+g[i-1]+0.5, g[i]=0.5*(g[i-1]+1)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define LL long long
 5 #define rg register
 6 #define N 500010
 7 using namespace std;
 8 int n;
 9 double f[N],g[N];
10 char s[N];
11 int main(){
12     scanf("%d
",&n); scanf("%s",s+1);
13     for(rg int i=1;i<=n;i++){
14         if(s[i]=='o') f[i]=f[i-1]+2*g[i-1]+1,g[i]=g[i-1]+1;
15         else if(s[i]=='x') f[i]=f[i-1],g[i]=0;
16         else f[i]=f[i-1]+g[i-1]+0.5,g[i]=0.5*(g[i-1]+1);
17     }
18     printf("%.4lf
",f[n]);
19     return 0;
20 }