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

梦里梦外; 2022-06-06 01:52 227阅读 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题目链接][vjudge]  
[建议参考博客——题意分析][Link 1]

以下为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);
    }

[vjudge]: https://vjudge.net/problem/LightOJ-1027
[Link 1]: http://blog.csdn.net/l123012013048/article/details/46418003