开锁魔法II 哈尔滨理工大学第五届ACM程序设计竞赛

朱雀 2022-08-07 09:55 212阅读 0赞

规律： **a\[i\]\[j\]= 1/i \* a\[i-1\]\[j-1\] + (i-1)/i \* a\[i-1\]\[j\];**   
(少一个盒子时使用j-1 次魔法的概率) (少一个盒子时使用j次魔法的概率)  
  
公式推导如下：  
  
**设a\[i\]\[j\]为打开i个盒子正好需要j次魔法的情况。**  
①  
1->1  
  
  
②  
1->1 , 2->2; 两次  
1->2 , 2->1; 一次  
  
  
③  
1->1 , 2->2 , 3->3; 三次  
1->2 , 2->1 , 3->3; 两次 3->3(n->n) 的这种情况单独考虑(因为 必需要使用一次魔法) 含有 (n->n)的情况发生的概率为 1/n,  
所以 比如a\[3\]\[2\] = 1/n \*a\[2\]\[1\] (2个盒子时使用1次魔法的情况 <加上当前这次正好使用2次魔法>) + ....(先不考虑)  
1->3 , 2->1 , 3->2; 一次  
1->1 , 2->3 , 3->2; 两次 仔细观察会发现当3->2时 其中的 1次2次 和①中的 1次2次 相同 3->1也是如此.  
  
  
1->3 , 2->2 , 3->1; 两次 上式的....就是这种情况，而这种 不含有n->n的概率会是  (n-1)/n  所以为 (n-1)/n \* a\[i-1\]\[j\] (少一个盒子时使用j次魔法的概率)

1->2 , 2->3 , 3->1; 一次

#include <cstdio>
    using namespace std;
    
    double a[5001][5001];   //当时不知道能开辣么大 ~~~~(>_<)~~~~ 
    
    int main()
    {
        int n, k;
        double ans;
       
        for(int i=1; i<=5000; i++)  a[i][1]=1.0/i;
        for(int i=2; i<=5000; i++){
            for(int j=2; j<=i; j++){
                if(i==j)    a[i][j] = a[i-1][j-1]*1.0/i;
                else        a[i][j] = 1.0/i*a[i-1][j-1]+(i-1)*1.0/i*a[i-1][j];
            }
        }
        while( scanf("%d%d", &n, &k)!=-1 ){
            ans = 0.0;
            for(int i=1; i<=k; i++)
                ans += a[n][i];
            printf("%.4f\n", ans);
        }
    
        return 0;
    }

开锁魔法II  
Time Limit: 3000 MS Memory Limit: 256000 K  
Total Submit: 6(4 users) Total Accepted: 3(3 users) Rating: Special Judge: No  
Description  
一日，崔克茜来到小马镇表演魔法。  
其中有一个节目是开锁咒：舞台上有 n 个盒子，每个盒子中有一把钥匙，对于每个盒子而言有且仅有一把钥匙能打开它。崔克茜可以通过魔法，暴力打开一个盒子。但是崔克茜最多只可以使用 k 次魔法，问在 k 次魔法内，打开所有盒子的概率是多少。  
Input  
多组测试数据。  
每组数据第一行有一个整数 n 和一个整数 k。(1 <= k <= n <= 5000)  
Output  
对于每组数据，输出一行表示对应的答案。结果保留四位小数。  
Sample Input  
3 1  
3 2  
3 3  
10 3  
Sample Output  
0.3333  
0.8333  
1.0000  
0.7061  
Source  
哈尔滨理工大学第五届ACM程序设计竞赛