HDUACM 2049 考新郎 解题报告

来源:互联网 时间:1970-01-01

简单的数学题,但也需要认真对待。

像我,一开始就用什么组合数学的知识解,就比较麻烦,还不知道解不解的出来,如果哪位牛人弄出来了,希望能指教一二。

这个题,最重要的是解决新郎选错的次数。这个次数是有规律的。我们可以用递归的方法或迭代方法求出来。

如 M = 2 3 4 5 6...(假设M == N)

则可能的次数依次为 1 2 9 44 265...

注意看,你会发现: 

           1 * 3  - 1 == 2;

           5 * 9 - 1 == 44;...

           4 * 2 + 1 == 9;

           6 * 44 + 1 == 265; ... 

所以我们可以用一个数组value保存与M值相对应的新郎错选的次数。

这里注意 随着M越来越大,其对应的值也越来越大,其值的增长速度是惊人的,很快就超出了long的范围。

所以我才用了_int64类型的整数。

当M != N 时,我们只需要在N个新郎中选择M个新郎,这是一个组合数学的问题,在此就不多说了。

下面是我的AC代码

#include "stdio.h"int main()
{
 int test,i,n,m;
 _int64 value[21] = {0,0,1,2},v;
 for(i = 4; i <= 20; i ++)
 {
  if(i % 2 != 0)
  {
   value[i] = value[i - 1] * i - 1;
  }
  else
  {
   value[i] = value[i - 1] * i + 1;
  }
 }
 while(scanf("%d",&test) == 1)
 {
  while(test --)
  {
   v = 1;
   scanf("%d%d",&n,&m);
   if(n != m)
   {
    for(i = n; i > n - m; i --)
    {
     v *= i;
    }
    for(i = m; i >= 1; i --)
    {
     v /= i;
    }
   }
   printf("%I64d/n",v * value[m]);
  }
 }
 return 0;
}

 这里,我想多说一句,至于前面的那个规律怎么求出来的,我目前还没想出来,也是Google之后才知道的。

希望同志们能指点迷津。


相关阅读:
Top