ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年5月3日 1200点热度 0人点赞 0条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ lightoj 算法竞赛 组合数学
最后更新:2022年7月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 题目大意 / Problem
  • 思路 / Thought
  • 代码 / Code

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号