P2059 [JLOI2013] 卡牌游戏

方杰123 · 2022-10-13 21:21:24 · 个人记录

题目

思路

这题跟约瑟夫问题思路其实一样。

回忆：(编号从0开始)设f[i]表示i个人游戏时活到最后的人的编号。那么f[i]=(f[i-1]+k)\%i，因为杀了第k个人后剩下的i-1个人可以看成从新开始游戏，只不过新游戏的编号+k=原游戏编号。

这题也是同理，设计dp[i][j]表示i个人游戏中编号为j（编号从0开始方便取余）的获胜概率，那么剩下的就很简单了。

code

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
double dp[N][N];int n,m,card[N];
int main(){
    n=read();m=read();for(int i=1;i<=m;i++)card[i]=read()-1;
    dp[1][0]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++){
            int die=card[j]%i;
            int match=(die+1)%i;
            for(int k=0;k<=(i-2);k++){
                dp[i][match]+=dp[i-1][k]*(1.0/m);
                match=(match+1)%i;
            }
        }
    }
    for(int i=0;i<n;i++){
        printf("%.2lf",dp[n][i]*100);
        cout<<"% ";
    }
    return 0;
}