[LightOJ]Beating the Dataset(组合数学)

发布于 2022-05-03  1363 次阅读


题目传送门:Beating the Dataset | LightOJ

题目大意 / Problem

有一个ACM选手在刷题,这题答案多组"YES" or "NO",给定了数据组数和答案字节数(可以算出ye和no各有多少个),每一个数据提交后会返回正确答案并作为下一次的提交,问错误数据个数的期望。

思路 / Thought

别想复杂了。其实很简单。

首先算出X和Y,分别表示YES和NO的数目。

一共有N组数据,那么期望可以这么算 E = 错误组数 / 总组数,每一对"0 1"或者“1 0”肯定有且仅有第一个是错误的,特殊地当第一个输出为0时也是错的。

换句话说,就是这个选手的输出会形成一个01串,求这个01串的某个位置与前一个位置的数字不同或第一个数为0的期望。

现在假设每个数字1 0都是不同的,那么总方法数为(X + Y)!,要求01连在一起的方法数,那么就把01捆绑起来当做一个数字,和剩下的数字一起全排列,方法数为X * (X + Y - 1)!,为什么要乘X * Y呢?因为我们假设每个数字都是互异的,那么选出这样一个01数字的方法就有X * Y种。那么10也一样,另外一种情况是选出一个0放到首位方法数为Y。所以期望为:

代码 / Code

/*Copyright (C) Eriktse 2022*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int kase = 1;
void solve()
{
	int N, M;cin >> N >> M;
	int X = M - 2 * N, Y = N - c1; // X 为 yes 的数目, Y为 no 的数目 
	printf("Case %lld: %.7lf\n", kase ++, (2.0 * X * Y + Y) / N);
}

signed main()
{
	int T;cin >> T;
	while(T --)solve();
	return 0;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09