解题报告：LightOJ - 1027 A Dangerous Maze 概率期望

75 阅读 0 评论 50 点赞

我是靠谱客的博主过时盼望，最近开发中收集的这篇文章主要介绍解题报告：LightOJ - 1027 A Dangerous Maze 概率期望，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

题意：

给定n个数，每次等概率的随机选一个数，直到选到正数，询问选到的数绝对值之和的期望，若为无穷大输出inf

思路：

考虑每次选择的贡献为，结束的概率为选中正数的概率，两者相乘就是最后的答案即：

所有数绝对值之和除以正数的个数，若不存在正数，那么为inf

这题还可以用公式解，先写出期望的公式，然后用错位相减法可以求的期望的通项公式，也是上面的结果

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
int T,cas=0;
scanf("%d",&T);
while(T--){
int n,cnt=0,x,sum=0;
scanf("%d",&n);
while(n--){
scanf("%d",&x);
if(x>0)cnt++;
sum+=abs(x);
}printf("Case %d: ",++cas);
if(!cnt)printf("infn");
else {
int gcd = __gcd(sum,cnt);
printf("%d/%dn",sum/gcd,cnt/gcd);
}
}return 0;
}