NEFU 15 八阵图（概率）

￡神魔★判官ぃ 2022-02-01 19:17 111阅读 0赞

[Click Here ~~][Click Here]

八阵图  
Problem : 15  
Time Limit : 1000ms  
Memory Limit : 65536K  
description  
相传诸葛孔明御敌时以乱石堆成石阵，按遁甲分成生、伤、休、杜、景、死、惊、开八门，变化万端，可挡十万精兵。（见《三国演义》）。  
现将诸葛亮的“八阵图”示意如下：

现在一般认为，八阵图就是一个巨大的迷宫。当某人陷入其中时，他可以从很多门中选择第i个门，经过ri天后即可以逃出八卦阵，也就是所谓的“生门”；也可能经过ri天后回到原处，也就是所谓的“死门”。如果你不识得八卦阵，你只有随机选择一个门；在八卦阵中，无法留下是否经过的标记，也就是说，你如果选择了“死门”回到原处，你还是只能随机选择一个门。  
现在，富有冒险精神的你，携带了W天的粮食和水进入了诸葛亮的八卦阵。由于八卦阵变化多端，你不知道八卦阵的布置，你的运气平平（也就是你选择每个门的可能性相同），你能安全逃出八卦阵吗？  
input  
有多组测试数据，输入的第一行只有一个正整数T(1≤T≤100);  
每组测试数据占三行，具有如下形式：  
N r1 r2 rn  
M rn+1 rn+m  
W  
其中N（0≤N≤1000）是生门的数目，M（0≤M≤1000）是死门的数目，W（0≤W≤10^9）是你携带了W天的粮食和水。ri(1≤i≤n+m, 0≤ri≤10,000)是生门或死门经过的天数。  
所有的测试数据都是非负整数。  
output  
对于每组测试数据，输出”Alive”，如果你能在W天内走出八卦阵。否则，输出”Dead”。  
注意：你走出八卦阵所需要的天数，是你随机选择后走出八卦阵所需要的天数的平均值。

sample\_input  
3  
3 4 5 6  
7 8 9 10 11 12 13 14  
3  
0  
2 1 1  
1  
2 3 1  
2 1 1  
3

sample\_output  
Dead  
Dead  
Alive  
hint  
概率  
source  
湖大

代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <algorithm>
    #include <set>
    using namespace std;
    
    #define MM(a) memset(a,0,sizeof(a))
    
    typedef long long LL;
    typedef unsigned long long ULL;
    const int maxn = 3e3+5;
    const int mod = 1e9+7;
    const double eps = 1e-8;
    const int INF = 0x3f3f3f3f;
    LL gcd(LL a, LL b)
    {
        if(b == 0)
            return a;
        return gcd(b, a%b);
    }
    
    int m[maxn], n[maxn];
    int main()
    {
        int T, N, W, M;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d", &N);
            int summ = 0, sumn = 0;
            for(int i=0; i<N; i++)
            {
                scanf("%d",&n[i]);
                sumn += n[i];
            }
            scanf("%d", &M);
            for(int i=0; i<M; i++)
            {
                scanf("%d",&m[i]);
                summ += m[i];
            }
            scanf("%d", &W);
            if(N == 0)
            {
                puts("Dead");
                continue;
            }
            int ave = (sumn+summ)/N;
            if(ave <= W)
                puts("Alive");
            else
                puts("Dead");
        }
        return 0;
    }

[Click Here]: http://acm.nefu.edu.cn/JudgeOnline/problemshow.php