盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 4986 Little Pony and Alohomora Part I(递推+调和级数)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=4986

题意

有n个盒子,每个盒子都有唯一一把钥匙可以打开它。现在将钥匙随机放在盒子里,问最少需要撬开几个盒子才能打开所有的盒子,求期望。其实就是求随机排列的期望循环个数。

思路

递推:假设f[n]为打开n个盒子的期望,当多了一个盒子时,如果该盒子装的是自己的钥匙,则需要多撬一次。如果装的是其他盒子的钥匙,相当于之前有一个循环多了一个数,但是次数不变。所以f[n+1] = (f[n]+1 + f[n]*n)/(n+1) = 1/(n+1) + f[n]。而f[1] = 1
这是数列为调和级数:当n很大的时候为log2(n+1) + 0.57721566490153286060651209(欧拉常数)

一个数位于循环长度为k的概率为1/n(与k无关) 证明如下:

代码

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
using namespace std;
typedef long long ll;
double a[200000 + 100];
#define euler 0.57721566490153286060651209
int main () {
double ans = 0;
for (int i = 1; i <= 200000; i++) {
ans += 1.0 / i;
a[i] = ans;
}
int n;
while(~scanf("%d", &n)) {
if (n <= 200000) printf("%.4f\n", a[n]);
else printf("%.4f\n", log(n) + euler);
}
return 0;
}

更新日志

  • 14534921 2015-08-16 17:59:18 Accepted 4986 0MS 3140K 565 B G++ SIO__Five