首页 > 代码库 > uva 11637 - Garbage Remembering Exam(概率)
uva 11637 - Garbage Remembering Exam(概率)
题目链接:uva 11637 - Garbage Remembering Exam
题目大意:大白数里有很详细的题意。
解题思路:对于有序的序列来说,考虑每个位置为有效性的概率。C(2?kn?1?x)?A(2k2k)?A(n?1?xn?1?x)A(n?1n?1)
x为考虑当前位置,然后与该位置距离小于等于k的位置个数。该位置有效的话,则对应的要将原先邻近的2*k个单词放到另外的位置上。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1e5;
int N, K;
long double frc[maxn+5];
double solve () {
if (N == 1)
return 0;
if (N - 2 * K - 1 <= 0)
return N;
double ret = 0;
for (int i = 1; i <= N; i++) {
int x = min(K, i - 1) + min(K, N - i);
if (N >= x + 2 * K + 1)
ret += exp(frc[N-1-2*K] + frc[N-1-x] - frc[N-1] - frc[N - 1 - x - 2 * K]);
}
return N - ret;
}
int main () {
int cas = 1;
frc[0] = 0;
for (int i = 1; i <= maxn; i++)
frc[i] = frc[i-1] + log((long double)i);
while (scanf("%d%d", &N, &K) == 2 && N + K) {
printf("Case %d: %.4lf\n", cas++, solve());
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。