2014
11-29

# 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


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;
}



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]）
这里写错了吧。