【概率&数学期望】A Dangerous Maze LightOJ

【概率&数学期望】A Dangerous Maze LightOJ - 1027

梦里梦外; 2022-06-06 01:52 278阅读 0赞

Think:
1知识点：概率＆数学期望
2题意：
（１）：T组测试数据
（２）：每组测试数据，n扇门，每扇门对应一个xi，等概率进入任意一扇门，若进入门的xi为正，则xi秒之后离开迷宫，若进入们的xi为负，则xi秒之后返回初始点
（３）：询问离开迷宫的数学期望
（４）：输出格式：测试数据　期望值最简分子/期望值最简分母
3解题思路：
（１）xi > 0: d1 = (1/n) * (x1+x2+…+xu)
（２）xi < 0: d2 = (1/n) * (abs(y1)+abs(y2)+…+abs(yv) + v*d)
即d = d1 + d2 = (1/n) * (x1+x2+…+xu) +(abs(y1)+abs(y2)+…+abs(yv) + v*d)
即(n-v) * d = x1 + x2 + … + xu + abs(y1) + abs(y2) + … + abs(yv)
即：
若v == n 则 d = inf
除此之外:
sum = x1 + x2 + … + xu + abs(y1) + abs(y2) + … + abs(yv)
t = gcd(sum, n-v)
d = p/q
p = sum/gcd(sum, n-v)
q = (n-v)/gcd(sum, n-v)

vjudge题目链接
建议参考博客——题意分析

以下为Accepted代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int gcd(int x, int y);
int main(){
    int cas = 1, T, n, m, sum, i, x;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        m = 0, sum = 0;
        for(i = 0; i < n; i++){
            scanf("%d", &x);
            if(x > 0) sum += x;
            else {
                sum += -x;
                m++;
            }
        }
        if(m == n){
            printf("Case %d: inf\n", cas++);
        }
        else {
            int t = gcd(sum, n-m);
            printf("Case %d: %d/%d\n", cas++, sum/t, (n-m)/t);
        }
    }
    return 0;
}
int gcd(int x, int y){
    if(!y) return x;
    else return gcd(y, x%y);
}