题解：SP9507 MARIO2 - Mario and Mushrooms

分析

如有错误，还请各位大佬指正！

虽然这道题可以使用动态规划来完成，但是因为这道题目中空间限制比较特殊，使用动态规划的话并不现实，所以不考虑。在这道题目中，正解是 Raney 引理。

Raney 引理：如果有一个整数序列的所有数字之和为一，则在这个序列中有且仅有一种循环移位满足所有前缀和非负。而这道题目中，如果马里奥最终剩下了一点生命值，则马里奥可以存活，反之则不能。刚好满足了 Raney 引理的构成条件。所以这道题目使用 Raney 引理。

思路

因为序列长度就等于好蘑菇的个数加上坏蘑菇的个数，所以整个序列的长度就等于

{k\times m + 1 + k}

。因为 Raney 引理中有一句很重要的话：在这个序列中有且仅有一种循环移位满足所有前缀和非负。所以在这道题目中，合法序列对应着

{k\times m + 1 + k}

个循环移位，所以序列合法的概率（也就是马里奥生还的概率）是

\frac{1}{k\times m + 1 + k}

。

代码

CPP

#include<bits/stdc++.h>  
using namespace std;
int main()  
{  
    int m,k,t;  
    double f;
    cin>>t;  
   	for(int i=1;i<=t;i++) 
    {  
        cin>>m>>k;
		f=1.0/(k*m+k+1);
        printf("Case #%d: %.8lf\n",i,f);
    }  
    return 0;  
}

题解：SP9507 MARIO2 - Mario and Mushrooms

文章操作

分析

思路

代码

相关推荐

评论

题解：SP9507 MARIO2 - Mario and Mushrooms