首页 > 代码库 > BestCoder7 1002 Little Pony and Alohomora Part I(hdu 4986) 解题报告
BestCoder7 1002 Little Pony and Alohomora Part I(hdu 4986) 解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4986
题目意思：有 n 个box（从左到右编号依次为1~n），每个box里面有一个随机的钥匙，有可能这条钥匙恰好可以开到这个box，但大多数情况下是不能够的。问期望值是多少。（例如对于两个box，有可能装着1 2 或者 2 1的 key，如果是1 2，那么就需要用两次咒语，而对于2 1（打开其中一个box就可以得到要开到另一个box的钥匙）只需要用一次即可。期望值就是 1/2 * 2 + 1/2 * 1 = 1.5 。1/2 是表示情况数。
据说要用到调和级数的化简，欧拉常数，数论题，留个纪念。真是如果缺乏某些知识点，考数学这些题目是完全不会做的。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 using namespace std; 6 7 const int maxn = 100000; 8 //const int r = 0.57721566490153286060651209; // 欧拉常数0.577218; 9 double f[maxn];10 11 int main()12 {13 int n;14 double ans;15 f[0] = 0;16 for (int i = 1; i < maxn; i++)17 f[i] = f[i-1] + 1.0/i;18 19 while (scanf("%d", &n) != EOF)20 {21 if (n < maxn)22 ans = f[n];23 else24 ans = log(n*1.0) + 0.57721566490153286060651209; // 用 r 来表示这个常数会错，很奇怪25 printf("%.4lf\n", ans);26 }27 return 0;28 }
BestCoder7 1002 Little Pony and Alohomora Part I(hdu 4986) 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。