首页 > ACM题库 > HDU-杭电 > HDU 3625-Examining the Rooms-数学相关-[解题报告]HOJ
2014
11-29

HDU 3625-Examining the Rooms-数学相关-[解题报告]HOJ

Examining the Rooms

问题描述 :

A murder happened in the hotel. As the best detective in the town, you should examine all the N rooms of the hotel immediately. However, all the doors of the rooms are locked, and the keys are just locked in the rooms, what a trap! You know that there is exactly one key in each room, and all the possible distributions are of equal possibility. For example, if N = 3, there are 6 possible distributions, the possibility of each is 1/6. For convenience, we number the rooms from 1 to N, and the key for Room 1 is numbered Key 1, the key for Room 2 is Key 2, etc.
To examine all the rooms, you have to destroy some doors by force. But you don’t want to destroy too many, so you take the following strategy: At first, you have no keys in hand, so you randomly destroy a locked door, get into the room, examine it and fetch the key in it. Then maybe you can open another room with the new key, examine it and get the second key. Repeat this until you can’t open any new rooms. If there are still rooms un-examined, you have to randomly pick another unopened door to destroy by force, then repeat the procedure above, until all the rooms are examined.
Now you are only allowed to destroy at most K doors by force. What’s more, there lives a Very Important Person in Room 1. You are not allowed to destroy the doors of Room 1, that is, the only way to examine Room 1 is opening it with the corresponding key. You want to know what is the possibility of that you can examine all the rooms finally.

输入:

The first line of the input contains an integer T (T ≤ 200), indicating the number of test cases. Then T cases follow. Each case contains a line with two numbers N and K. (1 < N ≤ 20, 1 ≤ K < N)

输出:

The first line of the input contains an integer T (T ≤ 200), indicating the number of test cases. Then T cases follow. Each case contains a line with two numbers N and K. (1 < N ≤ 20, 1 ≤ K < N)

样例输入:

3
3 1
3 2
4 2

样例输出:

0.3333
0.6667
0.6250
Hint
Sample Explanation When N = 3, there are 6 possible distributions of keys: Room 1 Room 2 Room 3 Destroy Times #1 Key 1 Key 2 Key 3 Impossible #2 Key 1 Key 3 Key 2 Impossible #3 Key 2 Key 1 Key 3 Two #4 Key 3 Key 2 Key 1 Two #5 Key 2 Key 3 Key 1 One #6 Key 3 Key 1 Key 2 One In the first two distributions, because Key 1 is locked in Room 1 itself and you can’t destroy Room 1, it is impossible to open Room 1. In the third and forth distributions, you have to destroy Room 2 and 3 both. In the last two distributions, you only need to destroy one of Room 2 or Room

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=3625

题意:

有N个房间,里面放着这N个房间的钥匙,不一定是放着自己的

你可以摧毁K个房间房间拿到K把钥匙(第一个房间你不能摧毁),为你能打开这N个房间的机会有多大

解题思路:

第二类斯特林数的应用

排除第一个这个例外,我们现在要用K把钥匙打开N个房间

也就相当于要有一些循环在里面,就是一把钥匙打开一个门以后,拿到的钥匙又可以打开下一个门。。。,这就相当于一个环

那么如果我们这N把钥匙组成一个环就可以,我们最多可以组成K个环

这就是斯特林数,即str[n][k]表示将n个数字分成K部分,并且每个部分组成一个环的种数(具体详见具体数学中文版P218-219)

如果不考虑那个VIP,N个房间可以被最多K把钥匙打开的情况,实际上就是1..N的置换组成最多K个环的情况,

这个就是第一类strling数之和S1[n][1]+S1[n][2]+…+S1[n][k]。

在这些情况里面,如果钥匙1恰好锁在房间1里也是不行的,所以还要减去N-1个房间被最多K-1把钥匙打开的情况数。

PS:如果想在ACM上有所建树,《具体数学》是一定要看的。

下面上代码:

#include<iostream>
#include<cstdio>
using namespace std;

const int maxn = 21;
#define LL long long

LL str[maxn][maxn];

void init_strling()
{
    str[1][1]=1;
    for(int i=1;i<maxn;i++)
        str[i][0]=0;
    for(int i=2;i<maxn;i++)
    {
        for(int j=1;j<=i;j++)
        {
            str[i][j] = (i-1)*str[i-1][j]+str[i-1][j-1];
        }
    }
}

LL cal(int n,int k)
{
    LL a1=0;
    LL a2=0;
    for(int i=1;i<=k;i++)
        a1+=str[n][i];
    for(int i=1;i<=k-1;i++)
        a2+=str[n-1][i];
    //printf("a1 %d a2 %d\n",a1,a2);
    return a1-a2;
}

LL cal2(int n)
{
    LL a1=1;
    for(int i=1;i<=n;i++)
        a1*=i;
    return a1;
}

int main()
{
    int t;
    scanf("%d",&t);
    init_strling();
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        LL a1=cal(n,k);
        LL a2=cal2(n);
        printf("%.4lf\n",a1*1.0/a2);
    }
    return 0;
}



参考:http://blog.csdn.net/dr5459/article/details/9204319


  1. 样例输出和程序输出不吻合,修改一下样例输出吧。我用的是VC编译器,会提示我的i和j变量重复定义

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  4. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。