题解 P5415 【[YNOI2019]游戏】

· · 题解

这是YNOI的题目（

高斯消元

考虑DP

首先，发现只需要记录当前所在位置以及擂主的连局数

设a_{i,j}表示当前在第i个位置，擂主连局数为j时的胜率

这时候需要分类讨论一下

边界情况：已经连胜m局

如果擂主是自己，那么胜率为1

a_{1,m}=1

否则，胜率为0

a_{i,m}=0,2 \leq i \leq n

情况1：是擂主

两种可能：

\frac{1}{4}$的概率当擂主，$\frac{3}{4}$的概率到第$n-2$个位置，连局数变为$1 a_{1,j}=\frac{1}{4}a_{1,j+1}+\frac{3}{4}a_{n-2,1},1\leq j <m

情况2：将要进行游戏

这时候需要根据位置讨论每个人胜利后的结果

a_{2,j}=\frac{1}{4}a_{1,1}+\frac{1}{4}a_{n-2,j+1}+\frac{1}{2}a_{n-1,1},1\leq j <m a_{3,j}=\frac{1}{4}a_{1,1}+\frac{1}{4}a_{n-1,j+1}+\frac{1}{4}a_{n-1,1}+\frac{1}{4}a_{n,1},1\leq j <m a_{4,j}=\frac{1}{4}a_{1,1}+\frac{1}{4}a_{n-2,j+1}+\frac{1}{2}a_{n,1},1\leq j <m

情况3：在队伍中

这时就看当前擂主是否能胜利即可

a_{i,j}=\frac{1}{4}a_{i-3,j+1}+\frac{3}{4}a_{i-3,1},5\leq i\leq n,1\leq j <m

最后答案：

很简单，就是a_{k,0}

然而，搞完这些，发现了问题：这些状态间依赖关系有环

也就是：不能直接DP

不过发现状态最多n(m+1)个

而n\leq 10,m\leq 10

于是就可以高斯消元了

如果不会，就去题库搜板子学习一下

最后复杂度O(n^3m^3)

其实有种做法可以做到O(n^2m+m^3)

另外，可以发现可能的输入只有490种

于是可以考虑打表（滑稽

最后是代码：

高斯消元：

#include<cstdio>
int t,m,n,k;
const int N=128;
const bool DEBUG=0;
double list[N][N];
#define abs(x) ((x)>=0?(x):-(x))
void solve(int c){
    double maxn;int maxp;
    for(int i=0;i<c;i++){
        maxn=0;
        for(int j=i;j<c;j++){
            if(abs(list[j][i])>maxn){
                maxn=abs(list[j][i]);
                maxp=j;
            }
        }
        if(maxn==0)throw 1;
        double t;
        for(int j=0;j<=c;j++){
            t=list[i][j];list[i][j]=list[maxp][j];list[maxp][j]=t;
        }
        t=list[i][i];
        for(int j=0;j<=c;j++){
            list[i][j]/=t;
        }
        for(int j=i+1;j<c;j++){
            t=list[j][i];
            for(int k=0;k<=c;k++){
                list[j][k]-=t*list[i][k];
            }
        }
    }
    for(int i=c-1;i>=0;i--){
        for(int j=i-1;j>=0;j--){
            list[j][c]-=list[j][i]*list[i][c];
            list[j][i]=0;
        }
    }
}
#define gid(x,y) ((m+1)*(x-1)+(y))
#define ls (n*(m+1))
int cnt;
double ans;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&k);
        cnt=0;
        for(int i=0;i<ls;i++){
            for(int j=0;j<=ls;j++){
                list[i][j]=0;
            }
        }
        //1,m
        list[cnt][gid(1,m)]+=1;
        list[cnt][ls]+=1;
        cnt++;
        //i,m
        for(int i=2;i<=n;i++){
            list[cnt][gid(i,m)]+=1;
            list[cnt][ls]+=0;
            cnt++;
        }
        //1,j
        for(int j=0;j<m;j++){
            list[cnt][gid(1,j)]+=1;
            list[cnt][gid(n-2,1)]+=-0.75;
            list[cnt][gid(1,j+1)]+=-0.25;
            list[cnt][ls]+=0;
            cnt++;
        }
        //2,j
        for(int j=0;j<m;j++){
            list[cnt][gid(2,j)]+=1;
            list[cnt][gid(1,1)]+=-0.25;
            list[cnt][gid(n-2,j+1)]+=-0.25;
            list[cnt][gid(n-1,1)]+=-0.5;
            list[cnt][ls]+=0;
            cnt++;
        }
        //3,j
        for(int j=0;j<m;j++){
            list[cnt][gid(3,j)]+=1;
            list[cnt][gid(1,1)]+=-0.25;
            list[cnt][gid(n-1,j+1)]+=-0.25;
            list[cnt][gid(n-1,1)]+=-0.25;
            list[cnt][gid(n,1)]+=-0.25;
            list[cnt][ls]+=0;
            cnt++;
        }
        //4,j
        for(int j=0;j<m;j++){
            list[cnt][gid(4,j)]+=1;
            list[cnt][gid(1,1)]+=-0.25;
            list[cnt][gid(n,j+1)]+=-0.25;
            list[cnt][gid(n,1)]+=-0.5;
            list[cnt][ls]+=0;
            cnt++;
        }
        //i,j
        for(int i=5;i<=n;i++){
            for(int j=0;j<m;j++){
                list[cnt][gid(i,j)]+=1;
                list[cnt][gid(i-3,j+1)]+=-0.25;
                list[cnt][gid(i-3,1)]+=-0.75;
                list[cnt][ls]+=0;
                cnt++;
            }
        }
        solve(ls);
        ans=list[gid(k,0)][ls];
        printf("%.6lf\n",ans);
    }

}

打表生成器：

//将标程编译后，重命名为5415.exe
//然后就会自动生成5415_biao.cpp
#include<bits/stdc++.h>
using namespace std;
ofstream fout,gans;ifstream anf;
string res;
int main(){
    gans.open("5415_biao.cpp");
    gans<<"#include<iostream>"<<endl;
    gans<<"using namespace std;"<<endl;
    gans<<"const string ans[11][11][11]={"<<endl;
    gans<<"    ";
    for(int n=0;n<4;n++){
        gans<<"{},";
    }
    gans<<endl;
    for(int n=4;n<=10;n++){
        gans<<"    {"<<endl;
        gans<<"        {},"<<endl;
        for(int m=1;m<=10;m++){
            gans<<"        {\"\",";
            for(int k=1;k<=n;k++){
                fout.open("5415.in");
                fout<<1<<endl;
                fout<<n<<" "<<m<<" "<<k<<endl;
                fout.close();
                system("5415.exe <5415.in >5415.out");
                anf.open("5415.out");
                anf>>res;
                anf.close();
                gans<<"\""<<res<<"\",";
            }
            gans<<"},"<<endl;
        }
        gans<<"    },"<<endl;
    }
    gans<<"};"<<endl;
    gans<<"int t,n,m,k;"<<endl;
    gans<<"int main(){"<<endl;
    gans<<"    cin>>t;"<<endl;
    gans<<"    while(t--){"<<endl;
    gans<<"        cin>>n>>m>>k;"<<endl;
    gans<<"        cout<<ans[n][m][k]<<endl;"<<endl;
    gans<<"    }"<<endl;
    gans<<"}"<<endl;
}