美团CodeM2018资格赛赛题官方版本详解（三）——世界杯

桃扇骨 2022-05-22 02:06 161阅读 0赞

# ![20180612213833827][]    #

![20180612213859811][]

![20180612213913444][]

![20180612213938633][] ![20180612214002356][]

**解题思路**

![20180612214039480][]

**标准程序**

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include <cmath>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    double v[6][16][16], p[16][16];
    
    int main() {
        for (int i = 0; i < 16; i++)
            for (int j = 0; j < 16; j++)
                scanf("%lf", &p[i][j]);
        memset(v, 0, sizeof(v));
        for (int i = 0; i < 16; i++)
            v[0][i][0] = 1.0;
        for (int i = 1; i <= 4; i++)
            for (int j = 0; j < 16 >> i; j++) {
                for (int x = 0; x < 1 << (i - 1); x++)
                    for (int y = 0; y < 1 << (i - 1); y++)
                        v[i][j][x] += v[i - 1][j << 1][x] * v[i - 1][(j << 1) + 1][y] * p[(j << i) + x][(j << i) + (1 << (i - 1)) + y],
                        v[i][j][(1 << (i - 1)) + y] += v[i - 1][j << 1][x] * v[i - 1][(j << 1) + 1][y] * (1.0 - p[(j << i) + x][(j << i) + (1 << (i - 1)) + y]);
                }
        for (int i = 0; i < 16; i++)
            printf("%.10f%c", v[4][0][i], i == 15 ? '\n' : ' ');
    }

[20180612213833827]: /images/20220522/4fb54cdc383c47e1b40c194219f1d49f.png
[20180612213859811]: /images/20220522/8835aed086734cd3997e042392cdff83.png
[20180612213913444]: /images/20220522/aa1960c59cbb4b90b013fefacb21aac1.png
[20180612213938633]: https://img-blog.csdn.net/20180612213938633
[20180612214002356]: /images/20220522/7125f54a9dda4dd4a22afd3bb490d498.png
[20180612214039480]: /images/20220522/a51ed3ea2ec14002bcfd0f6795941d64.png