ACM学习历程—HDU2068 RPG的错排(组合数学)
2024-10-20 16:22:45
Description
今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜,第一次猜:R是公主,P是草儿,G是月野兔;第二次猜:R是草儿,P是月野兔,G是公主;第三次猜:R是草儿,P是公主,G是月野兔;......可怜的野骆驼第六次终于把RPG分清楚了。由于RPG的带动,做ACM的女生越来越多,我们的野骆驼想都知道她们,可现在有N多人,他要猜的次数可就多了,为了不为难野骆驼,女生们只要求他答对一半或以上就算过关,请问有多少组答案能使他顺利过关。
Input
输入的数据里有多个case,每个case包括一个n,代表有几个女生,(n<=25), n = 0输入结束。
Output
对应每组数据输出最小移动距离。
Sample Input
1
2
0
Sample Output
1
1
假设i个人在他本来位置,其余人错排的种数是f[i],那么题目要求的就是所有大于等于(n+1)/2的f[i]的和,n+1是为了对奇数偶数情况统一。
假设k个人错排是p[k],
那么就是n个人先取出i个人在自己位置C(n, i),其余人再错排p[n-i],然后控制i的范围就OK了。
这里需要注意的是由于题目没有模的情况,所以所有数可能会很大,所以在求p和c的时候最好是相邻项间递推。
代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
#define LL long long using namespace std; int n;
LL p[], c[], ans; void init()
{
p[] = ;
p[] = ;
p[] = ;
for (int i = ; i < ; ++i)
p[i] = (i-)*(p[i-]+p[i-]);
} void cal()
{
c[] = ;
for (int i = ; i <= n; ++i)
c[i] = c[i-]*(n-i+)/i;
} void work()
{
ans = ;
int half = (n+)/;
for (int i = ; i+half <= n; ++i)
ans += c[i+half]*p[n-i-half];
printf("%I64d\n", ans);
} int main()
{
//freopen("test.in", "r", stdin);
init();
while (scanf("%d", &n) != EOF && n)
{
cal();
work();
}
return ;
}
最新文章
- 故障review的一些总结
- Excel中VBA进行插入列、格式化、排序
- java单例的几种实现方法
- java-commons-HttpClient超时设置setConnectionTimeout和setSoTimeout
- Linux下的原子操作
- (转帖)C++中自己实现的split函数
- Java中的Double类型计算
- myeclipse2014破解版本链接
- Windows环境自动获取AWR报告
- 苹果iphone4s完美越狱后破解4g网络方法
- 机器学习中的数学(4)-线性判别分析(LDA), 主成分分析(PCA)
- BootStrap 智能表单系列 首页 (持续更新中...)
- 如何压缩UUID长度?
- HTNL表单详解
- 关于HashSet集合add元素
- sass编写高质量的css---(基础语法结构)
- checkbox jquery操作总结
- schema举例二
- 父页面操作嵌套iframe子页面的HTML标签元素
- beat冲刺(7/7)
热门文章
- jQuery--基础(查询标签)
- caffe-ubuntu1604-gtx850m-i7-4710hq----bvlc_reference_caffenet.caffemodel
- Android 逐帧动画( Drawable 动画),这一篇就够了
- DWR3.0(Direct Web Remoting)实践
- 【Java】事件驱动模型和观察者模式
- 【Caffe】源码解析----caffe.proto (转载)
- Spark源代码分析之六:Task调度(二)
- 短信计时器Utils
- python 基础 7.7 json--上
- Python 深入剖析SocketServer模块(二)(V2.7.11)