考新郎(错排)
发布日期:2022-02-17 09:51:12
浏览次数:10
分类:技术文章
本文共 1828 字,大约阅读时间需要 6 分钟。
先说说心得
刚刚打完所谓的校赛
并不如意。 学长们口口声声说的简单的题 我做起来却是一次又一次的WA(wrong answer) 之前总是觉得自己很行 就很漂 所以就炸了 ————————————————分界线———————————————— 我个人的反思和感受: 打ACM 肯定不是三天两天就能够速成的 需要不断积累不断学习新的算法和技巧。 不能浮躁 要有耐心。下面是补题(训练7):
1:考新郎 国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;
然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个. 最后,揭开盖头,如果找错了对象就要当众跪搓衣板…看来做新郎也不是容易的事情…
假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
Input输入数据的第一行是一个整数C,表示测试实例的个数,然后是C行数据,每行包含两个整数N和M(1<M<=N<=20)。
Output
对于每个测试实例,请输出一共有多少种发生这种情况的可能,每个实例的输出占一行。
Sample Input
2
2 2 3 2Sample Output
1
3 —————————————————分界线————————————————————— 这是一个错排题,需要运用错排公式 下面是错排公式的推导: 首先先理解一下什么是错排:考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。 其中n个元素的错排数记为D(n)。 现在想象一个情景 有n本书,现在要重新排列。 **假如说取的那本书命名为a,位置也是a。 取出它,放到另一个位置b。有(n-1)种情况 此时,b这个位置放的书是a,手中是书b,空位是a。 于是现在存在两种情况。 ** ①把书b放回a位置 ②不考虑空位a 第一种情况:把b书放入a空中,也就是a,b交换,其他的没有被移动,仍然是一一对应的。 那么对于剩下的几本书的错排,就回到了最初。求n-2本书的错排操作数D(n-2),结合前面的分析,共有(n-1)D(n-2)种情况。 第二种情况:不放入a空中,那么还剩下n-2个位置,那么现在要排的书是手中的那本和未排序的那n-2本,也就是n-1本。这就是相当于把这n-1本书进行错排。所以问题就变成了求n-1本书的错排操作数D(n-1),结合前面的分析,共有(n-1)D(n-1)种方法。综合两种情况,相加就可以得到错排公式。
D(n)=(n-1)*[D(n-1)+D(n-2)] ———————————————分界线————————————————— 回到这个题,这个题也是一个错排题,但是又不仅仅是一个错排题。 从N个新郎,挑出M个错排,那就是有N-M个新郎选对了。 此时就要用到高中时学到的排列组合 所以 最后的公式为:S=C(N,N-M)*D[M] (其中D[M]是错排公式的值) 搞清楚了这些,代码写起来就不麻烦了。#includeint main(){ long long f[25]; int n; scanf("%d",&n); while(n--) { int a,b; scanf("%d%d",&a,&b); f[1] = 0; f[2] = 1; for(int i = 3; i <= 20; i++) f[i] = (i-1)*(f[i-1]+f[i-2]); //错排公式 long long sum1 = 1; long long sum2 = 1; for(int i = a; i > a-b; i--) sum1 *= i; for(int i = 2; i <= b; i++) sum2 *= i; printf("%lld\n",sum1/sum2*f[b]); //sum1/sum2为C(M,N-M) } return 0;}
转载地址:https://blog.csdn.net/qq_43826794/article/details/84963820 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年03月23日 11时01分23秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
C++深度解析 内联函数分析 内联inline和宏#define(5)
2019-04-25
C++深度解析 函数重载分析(7)
2019-04-25
报表的 SQL 注入风险是什么意思?如何防范?
2019-04-25
JS-part3.3-复杂数据类型之 数组和排序方法
2019-04-25
求和与平均值
2019-04-25
if选择结构
2019-04-25
switch多选择结构
2019-04-25
计算1+2+3+...+100
2019-04-25
用while或for循环输出1-1000之间能被5整除的数,并且每行输出3个
2019-04-25
学习的总结
2019-04-25
学习的总结
2019-04-25
66天街欢抢节 北京长安天街 6.5-6.6
2019-04-25
武田中国创新挑战赛重磅启动,诚邀初创企业共赴数字医疗之途
2019-04-25
九巨龙集团安全大检查行动,践行“客户满意工程”牢筑安全防线!
2019-04-25
最好吃的8款粽子,看看有没有你家乡的!
2019-04-25
端午前后湿热当道,这些祛湿的好方法一定要收好
2019-04-25