关于 [CYJian的水题大赛] 题目及题解

小粉兔 @ 2018-07-16 20:36:37

by 小粉兔 @ 2018-07-16 20:37:47

80分代码

100分代码

by Siyuan @ 2018-07-16 20:40:25

@小粉兔 比赛主页写了，数据出锅了（前排 %%% 粉兔！）

by Siyuan @ 2018-07-16 20:41:48

@siyuan 哦抱歉，是题目里的update

by CalvinJin @ 2018-07-16 20:42:15

= =我也发现数据应该是改过了 和月赛一样的情况 同样代码再交一遍就A了

by かなで @ 2018-07-16 20:45:47

AKdalao粉兔太强啦%%%

by HHCY @ 2018-07-16 20:49:54

@小粉兔 t2是不是卡空间

by Siyuan @ 2018-07-16 20:52:09

@小粉兔 求解公式推导？

by strangers @ 2018-07-16 20:55:12

前排 %%% 粉兔！

by 小粉兔 @ 2018-07-16 21:03:21

至于这个公式的推法：

显然，A 只红鲤鱼对应着 A 次 5 分钟罚时，而 B 只绿鲤鱼对应着 B+1 次 AC。

考虑到都是 5 分钟，后面把 5 分钟当 1 分钟考虑吧。

先把罚时和最后一次 AC 搞掉：A+(A+B+1)=2A+B+1。

考虑中间的每次 AC ，总共 A+B 个位置，均等/无差别的选 B 个，则每个位置被选中的概率显然是 B/(A+B) 。

或者从组合数的方面严格一点考虑：总方案 C_{A+B}^{B} ，这个位置有 AC 的方案 C_{A+B-1}^{B-1} 。则概率为 C_{A+B-1}^{B-1}/C_{A+B}^{B}=\frac{(A+B-1)!}{A!(B-1)!}/\frac{(A+B)!}{A!B!}=\frac{(A+B-1)!}{A!(B-1)!}\cdot \frac{A!B!}{(A+B)!}=\frac{B}{A+B}。

那么位置 i 的期望贡献就是 i\cdot\frac{B}{A+B}。总贡献就是 (A+B)(A+B+1)/2\cdot\frac{B}{A+B}=B(A+B+1)/2 。

那么 Ans=2A+B+1+B(A+B+1)/2=(AB+B^2+B+4A+2B+2)/2=[4(A+B)+B(A+B-1)+2]/2 。

最后把 5 分钟乘上。

by 小粉兔 @ 2018-07-16 21:03:43

至于这个公式的推法：

显然，A 只红鲤鱼对应着 A 次 5 分钟罚时，而 B 只绿鲤鱼对应着 B+1 次 AC。

考虑到都是 5 分钟，后面把 5 分钟当 1 分钟考虑吧。

先把罚时和最后一次 AC 搞掉：A+(A+B+1)=2A+B+1。

考虑中间的每次 AC ，总共 A+B 个位置，均等/无差别的选 B 个，则每个位置被选中的概率显然是 B/(A+B) 。

或者从组合数的方面严格一点考虑：总方案 C_{A+B}^{B} ，这个位置有 AC 的方案 C_{A+B-1}^{B-1} 。则概率为 C_{A+B-1}^{B-1}/C_{A+B}^{B}=\frac{(A+B-1)!}{A!(B-1)!}/\frac{(A+B)!}{A!B!}=\frac{(A+B-1)!}{A!(B-1)!}\cdot \frac{A!B!}{(A+B)!}=\frac{B}{A+B}。

那么位置 i 的期望贡献就是 i\cdot\frac{B}{A+B}。总贡献就是 (A+B)(A+B+1)/2\cdot\frac{B}{A+B}=B(A+B+1)/2 。

那么