洛谷 P1654 OSU!

发表于 更新于 分类于

三倍经验。

CF235B Let’s Play Osu!

分类讨论一下再算下期望就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
//#define int long long
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define PII pair<int,int>
const int MOD=998244353;
const int N=1000002;
const int M=10000001;
using namespace std;
inline int read(){register char c=getchar();register int s=0,f=1;for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())s=(s<<3)+(s<<1)+c-'0';return s*f;}
inline double readd(){int y=0;char h=getchar();while(h<'0'||h>'9')h=getchar();while(h>='0'&&h<='9')y=y*10+h-'0',h=getchar();if(h=='.'){h=getchar();double t=0,t2=0.1;while(h>='0'&&h<='9')t=t+t2*(h-'0'),t2/=10,h=getchar();return y+t;}return y;}
int n;
long double p;
long double ff;
long double aa,bb;
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		p=readd();
		ff=ff+p*(2*aa+1);
		aa=p*(aa+1);
	}
	printf("%.15Lf",ff);
	return 0;
}

洛谷 P1365 WJMZBMR打osu! / Easy

同上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
const int N=1000001;
int n;
char a[N];
long double x,y;
long double len;
int main(){
	cin>>n;
	scanf("%s",a+1);
	for(int i=1;i<=n;i++){
		if(a[i]=='o'){
			x=y+len*2+1;
			len+=1.0;
		}
		else if(a[i]=='x'){
			x=y;
			len=0.0;
		}
		else {
			x=y+len+0.5;
			len=len/2.0+0.5;
		}
		y=x;
	}
	printf("%.4Lf",x);
	return 0;
}

洛谷 P1654 OSU!

需要注意推高次期望（这里是三次）时不能直接把原来的期望乘个几次，而要每次计算一遍。

如本题：

设 a[i]a \left [ i \right ] 为一次幂，b[i]b \left [ i \right ] 为二次，f[i]f \left [ i \right ] 为三次，pp 为正确概率。
那么有：

a[i]=p(a[i−1]+1)a \left [ i \right ] = p \left (a \left [i-1 \right ]+1 \right )

b[i]=p(b[i−1]+2×a[i−1]+1)b \left [ i \right ] = p \left ( b \left [i-1 \right ] + 2 \times a \left [i-1 \right ] + 1 \right )

f[i]=f[i−1]+p(3×b[i−1]+3×a[i−1]+1)f \left [ i \right ] = f \left [i-1 \right ] + p \left (3 \times b \left [i-1 \right ] + 3 \times a \left [i-1 \right ] + 1 \right )

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
inline int read(){register char c=getchar();register int s=0,f=1;for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())s=(s<<3)+(s<<1)+c-'0';return s*f;}
inline double readd(){int y=0;char h=getchar();while(h<'0'||h>'9')h=getchar();while(h>='0'&&h<='9')y=y*10+h-'0',h=getchar();if(h=='.'){h=getchar();double t=0,t2=0.1;while(h>='0'&&h<='9')t=t+t2*(h-'0'),t2/=10,h=getchar();return y+t;}return y;}
int n;
long double p,ff,aa,bb;
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		p=readd();
		ff=ff+p*(3*bb+3*aa+1);
		bb=(bb+2*aa+1)*p;
		aa=p*(aa+1);
	}
	printf("%.1Lf",ff);
	return 0;
}