bzoj 4001 概率论

Posted on | Views:

小水题.

感觉和那次考试的题差不多啊.

答案等于所有情况的叶子数目之和 除以 不同构的二叉树数目.

后者显然是卡特兰数 $C_n$ .

前者的计算也很简单,考虑有 $n-1$ 个点的时候,剩下的一个点可以有 $n$ 个位置插入作为叶子.

于是答案为
$$
ans=\frac{nC_{n-1}}{C_n}=\frac{n(n+1)}{2(2n-1)}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
int main()
{
	double n=(double)read();
	double ans=n*(n+1)/2/(2*n-1);
	printf("%.9lf\n",ans);
	return 0;
}