首页 > 代码库 > HDU4986 (Little Pony and Alohomora Part I )
HDU4986 (Little Pony and Alohomora Part I )
http://acm.hdu.edu.cn/showproblem.php?pid=4986
Little Pony and Alohomora Part I
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 259 Accepted Submission(s): 143
Problem Description
Trixie is a female unicorn pony and traveling magician, having been rumored to be "the most magical unicorn in all of Equestria". One day, Trixie arrives in Ponyville.
There is n boxes on the stage. There is a random key in each box and each box has a key match it. As a unicorn, Trixie can use "Alohomora"(the unlocking spell) to open any box.
Trixie would like to open all the boxes, also Trixie would like to minimize the spells she used. Help Trixie to calculate the expected number of spells she need to used in order to open all the boxes necessary.
There is n boxes on the stage. There is a random key in each box and each box has a key match it. As a unicorn, Trixie can use "Alohomora"(the unlocking spell) to open any box.
Trixie would like to open all the boxes, also Trixie would like to minimize the spells she used. Help Trixie to calculate the expected number of spells she need to used in order to open all the boxes necessary.
Input
Input contains multiple test cases (less than 100).
For each test case, only one line contains one integer n (1<=n<=1000000000).
For each test case, only one line contains one integer n (1<=n<=1000000000).
Output
For each case, output the corresponding result, rounded to 4 digits after the decimal point.
Sample Input
12
Sample Output
1.00001.5000
Hint
The second sample: There are two different permutations when n equal to 2: (1, 2) and (2, 1). Trixie need to use 2 spells in (1, 2) and 1 spell in (2, 1).
Source
BestCoder Round #7
看大神的解释 http://blog.csdn.net/accelerator_/article/details/38980295
题意:一些钥匙随机放在箱子里,现在问打开次数期望
思路:每种方式相当于一个置换的循环个数,那么考虑f[i]为i个箱子的情况,f[i + 1]要么就是放在最后多一个循环,要么就是插入中间循环个数不变,对应的转移为f[i + 1] = (f[i] + 1) / i + f[i] * (i - 1) / i 化简得到f[i] = f[i - 1] + 1 / i
这个式子i越大,越趋近lni + C,这个C为犹拉常数,所以先递推出数字小的情况,大的就直接计算
#include <iostream>#include <iomanip>#include <fstream>#include <sstream>#include <cassert>#include <algorithm>#include <string>#include <vector>#include <set>#include <map>#include <queue>#include <stack>#include <cmath>#include <numeric>#include <bitset>#include <cstdio>#include <cstring>using namespace std;#define rep(i, n) for (int i = 0, _n = (int)(n); i < _n; i++)#define fer(i, x, n) for (int i = (int)(x), _n = (int)(n); i < _n; i++)////////////////////////////////////////////////////////////////////////////////const int N = 1000000;double f[N];void init(){ f[1]=1; fer(i,2,N+1) f[i] = f[i-1] + 1.0/i;}int main(){ //freopen("in.txt","r",stdin); ios_base::sync_with_stdio(0); int n; init(); while(scanf("%d",&n)!=EOF){ printf("%.4lf\n", n > N ? 0.57721566490153286060651209+log(n+0.0) : f[n] ); } return 0;}
HDU4986 (Little Pony and Alohomora Part I )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。