ACM-ICPC 2018 徐州赛区网络预赛 C Cacti Lottery(期望+暴力)

https://nanti.jisuanke.com/t/31455

题意

给一个3*3的方格填入 1-9 九个数 
有些数是已知的，有些数是对方已知但我未知的，有些数是大家都未知的 
我要计算取得最大的对应值的期望 

分析

题意有点难懂。

首先先枚举把剩下的数填入星号的情况（其实就是枚举星号的排列），这是对方所能知道的所有信息，然后对方将取八种决策中最优的情况，而因为井号的存在，所以其排列也会影响每种决策的分数，所以接着要枚举井号的排列情况，对于每种情况累加每个决策的分数，最后枚举完后，要除以井号排列数（期望=分数*概率），然后对方便会选择期望最高的决策，累加到最后答案中，枚举完所有星号的之后，需要将最后答案除以星号排列数

#include<bits/stdc++.h>
using namespace std;
double ans;
int cnt,tot;
bool vis[10];
char s[5][5];
int p[10],a[10],tmp[10];
int state[10];
int S[8][3]={
    0,1,2,
    3,4,5,
    6,7,8,
    0,3,6,
    1,4,7,
    2,5,8,
    0,4,8,
    2,4,6
};
int score[]={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 fac[10];
void work(){
    vector<int> num;
    for(int i=0;i<8;i++) state[i]=0;
    for(int i=1;i<=9;i++){
        if(!vis[i]){
            num.push_back(i);
        }
    }
    
    do{
        int na=0,nb=0;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(s[i][j]=='*') tmp[i*3+j]=p[na++];
                else if(s[i][j]=='#') tmp[i*3+j]=num[nb++];
                else tmp[i*3+j]=s[i][j]-'0';
            }
        }
        for(int i=0;i<8;i++){
            int sum=0;
            for(int j=0;j<3;j++){
                sum+=tmp[S[i][j]];
            }
            state[i]+=score[sum];
        }
    }while(next_permutation(num.begin(),num.end()));
    double res=0;
    for(int i=0;i<8;i++){
        res=max(res,state[i]*1.0/fac[num.size()]);
    }
    ans+=res;
}
void dfs(int pos){
    if(pos==tot){
        cnt++;
        work();
        return;
    }
    for(int i=1;i<=9;i++){
        if(!vis[i]){
            vis[i]=true;
            p[pos]=i;
            dfs(pos+1);
            vis[i]=false;
        }
    }
}

int main(){
    fac[0]=1;
    for(int i=1;i<10;i++) fac[i]=fac[i-1]*i;
    int T;
    scanf("%d",&T);
    while(T--){
        memset(vis,false,sizeof(vis));
        tot=0;
        for(int i=0;i<3;i++){
            scanf("%s",s[i]);
            int len = strlen(s[i]);
            for(int j=0;j<len;j++)
                if(s[i][j]=='*') tot++;
                else if(isdigit(s[i][j])) vis[s[i][j]-'0']=true;
        } 
        ans=cnt=0;
        dfs(0);
        ans=ans/cnt;
        printf("%.8f
",ans);
    }
    return 0;
}