NOI手拉手问题

问题描述:

n个人n双手,每一次选择两个空手让这两个空手拉起来,然后这两个手不再是空手。一个人有两只手,问最终所有手都拉起来构成环的个数的期望。PS:一个人的左手和右手也可以拉起来构成一个环。

例如:n为2时,期望为4/3,假设从第一个人的左手开始,他的左手和右手和第2个人的左手和右手拉起来的概率都为1/3,其中自己的左手和右手拉起来构成环数为2,其他为1,则期望为1/3*2+1/3*1+1/3*1

题解:

1+1/3+1/5+……1/(2n-1)

如果直接看公式很容易理解,每多一个人,就多了两只手,假设除了这个人以外其他人的期望都算出来了,假设期望为F(n),那么对于这个人来说无非两种情况,要么和自己拉,要么和别人拉,和自己拉的概率为1/(2n-1),和别人拉的概率为(2n-2)/(2n-1)。和自己拉的话很好理解,在之前的期望上加1就好了,和别人拉的话就可以把这两个人绑定起来当成一个人就好了,期望就是之前的期望。所以用公式的话就是F(n+1)=F(n)*(2n-2)/(2n-1)+(F(n)+1)*1/(2n-1),化简就得F(n+1)=F(n)+1/(2n-1),递归得F(n)=1+1/3+1/5+……1/(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
24
#include<bits/stdc++.h>
using namespace std;
#define ld long double
const int maxn = 1e7+7;
ld a[maxn];
void init(){
a[0] = 0;
a[1]=1;
for(int i = 2;i<maxn;i++){
a[i]=a[i-1]+1.0/(2*i-1);
}
}
int main(){
//freopen("head.in","r",stdin);
//freopen("head.out","w",stdout);
long long tmp;
init();
cin>>tmp;
if(tmp*1.0>=maxn)
cout<<log(2*tmp-1) - log(((2*tmp-1)-1)/2)/ 2 + 0.57721566490153286060651209 / 2<<endl;
else
cout<<a[tmp]<<endl;
return 0;
}

文章结束了,但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!