Cacti Lottery—2018徐州网络赛C题(暴力)

作者: qwq 分类: ACM 发布时间: 2018-09-09 20:59

题目链接:https://nanti.jisuanke.com/t/31455

大意:

在3*3的格子中有1~9这9个数字,每个数字只出现一次,Morgana可以选任意一行或一列和两个对角线,选出来的3个数字之和对应不同的得分,现在有些格子的数字不知道,还有些各种的数字他知道但不告诉你。让你求得分的期望。

解法:

假设Morgana把他知道的所有的格子都告诉你了,也就是没有*的格子,这个时候的数学期望就是暴力枚举所有的格子所有情况,计算出八种选择(横着选3种,竖着3种,对角线2种)中,哪种得分的期望最大。

而现在有某些各种他知道故意不告诉你,这个时候也需要枚举那些格子的数字是多少,计算一下平均数就可以了

/*build at 2018/9/9 15:01   #jetbrains #CLion*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include"iomanip"

using namespace std;

typedef long long ll;
int z[25] = {0, 0, 0, 0, 0, 0, 10000, 36, 720, 360, 80, 252, 108, 72, 54, 180, 72, 180, 119, 36, 360, 1080, 144, 1800,
             3600};
int jc[11] = {0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};//阶乘
int b[10];
int a[3][3];
int x[10];
int numx = 0, numj = 0;
int tot = 0;

int cal() {//计算每种的得分情况
    int t = 0;
    for (int i = 0; i < 3; i++) {
        x[t++] += z[a[i][0] + a[i][1] + a[i][2]];
    }
    for (int i = 0; i < 3; i++) {
        x[t++] += z[a[0][i] + a[1][i] + a[2][i]];
    }
    x[t++] += z[a[0][0] + a[1][1] + a[2][2]];
    x[t++] += z[a[0][2] + a[1][1] + a[2][0]];
}

void f() {//枚举#数字
    int flag = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (a[i][j] == -2) {
                flag = 1;
                for (int k = 1; k <= 9; k++) {
                    if (b[k] == 0) {
                        a[i][j] = k;
                        b[k] = 1;
                        f();
                        a[i][j] = -2;
                        b[k] = 0;
                    }
                }
                return;
            }
        }

    }
    if (flag == 0) {
        cal();
        return;
    }
}

int test() {//枚举*数字的每种可能
    int flag = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (a[i][j] == -1) {
                flag = 1;
                for (int k = 1; k <= 9; k++) {
                    if (b[k] == 0) {
                        a[i][j] = k;
                        b[k] = 1;
                        test();
                        a[i][j] = -1;
                        b[k] = 0;
                    }
                }
                return 0;
            }
        }

    }


    if (flag == 0) {
        memset(x, 0, sizeof x);
        f();

        int maxx = 0;
        for (int i = 0; i < 8; i++) {
            maxx = max(maxx, x[i]);
        }//选出得分最大的
        tot += maxx;

    }
}

int main() {
    ios::sync_with_stdio(0);

    int t;
    cin >> t;
    while (t--) {
        numx = 0;
        numj = 0;
        tot = 0;
        memset(b, 0, sizeof b);
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                char c;
                cin >> c;
                if (c >= '0' && c <= '9') {
                    a[i][j] = c - '0';
                    b[a[i][j]]++;
                } else {
                    if (c == '*') {
                        a[i][j] = -1;
                        numx++;
                    } else {
                        a[i][j] = -2;
                        numj++;
                    }
                }
            }
        }

        test();
        long double ans = 1.0 * tot / (jc[numx + numj] * 1.0);
        cout << setprecision(13) << ans << endl;


    }

    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注