题目概述
某人参加一场淘汰赛，实力排名为$r$，排名越高实力越强。一共有$2^k$支队伍参加比赛，问这个人获胜场次的概率。
数据范围
分析与解
这题还是一个要画画图，不能干想。其实把那张满二叉树的晋级图画出来，就明白是怎么回事了。
其实从图上显然看出，某人如果要至少赢$i$场，则应该战胜$2^i-1$个对手。这其实和线段树求区间最小值的原理是类似的。因此可以得到概率
设$f(i)$表示恰好赢$i$场的概率，那么答案
这里值得一提的是怎么快速计算$s[i]$，答案是取对数。
即
而
因此只要预处理即可。
代码
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
29
30
31
32
33
34
35
36
37
38
39
| #include <bits/stdc++.h>
using namespace std;
int mread() {
int ret=0,f=1;
char c=getchar();
while(c<'0' || c>'9') {
if(c=='-')f=-1;
c=getchar();
}
do {
ret=ret*10+c-'0';
c=getchar();
} while('0'<=c && c<='9');
return ret*f;
}
int r,k;
const int N = (1<<20)+50;
double my_pow[N],s[30];
double lnc(int n,int m) {
return my_pow[n] - my_pow[m] - my_pow[n-m];
}
int main() {
int n,now;
double ans=0.0;
k=mread(),r=mread();
for(int i=1; i<=(1<<k); i++)my_pow[i]=my_pow[i-1]+log((double)1.0*i);
n=(1<<k);
for(int i=1; i<=k; i++)
{
now=(1<<i)-1;
if(n-r < now)continue;
s[i]=exp(lnc(n - r,now) - lnc(n - 1,now));
}
for(int i=1; i<=k; i++)
ans+=s[i];
printf("%.5lf\n",ans);
return 0;
}
|