题目传送门: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; }
Comments NOTHING