三倍经验。
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 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 \left [ i \right ]$ 为一次幂，$b \left [ i \right ]$ 为二次，$f \left [ i \right ]$ 为三次，$p$ 为正确概率。
那么有：
$a \left [ i \right ] = p \left (a \left [i-1 \right ]+1 \right )$
$b \left [ i \right ] = p \left ( b \left [i-1 \right ] + 2 \times a \left [i-1 \right ] + 1 \right )$
$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;
}
|