JZSIM 3.13

Author Avatar
空気浮遊 2019年03月13日
  • 在其它设备中阅读本文章

感觉今天人均 280...

过程

T1

昨天还是前天做的原题

T2

为什么也是异或生成树啊... 数据范围也好像... 撞 IDEA 了?后来发现好毒瘤啊...
水水分滚蛋算了...

T3

好像大家都做过原题的样子.jpg

估个 200 吧。打脸预定 ex


第七名草

最后是二十七名,海星

更正

T2 小凯的疑惑 DLC3

这 A 的方法是真 TM 傻逼...

T3 Yes or No

神仙题。

考虑一个网格图,钦定 $n\geq m$,从 $(n, m)$ 出发走到 $(0,0)$,以及一条直线 $y=x$。那么在 $y=x$ 的右方我们肯定会选择左走,在 $y=x$ 的上方我们肯定会选择下走。那么我们考虑实际上的某种方案代表了一个路径。如果在 $y=x$ 的右方我们左走,代表我们猜对了,否则代表我们猜错了。

那么考虑如果我们没有经过 $y=x$,将所有的路径的方案都列出来,我们发现每一条路径我们都猜对了(向左走了)至少 $n$ 个点。

如果是任意一条路径,我们考虑通过 $y=x$ 将各个部分拆开来看,我们最终还是一定会猜对 $n$ 次。

geogebra-export.png

对于其中的红色边,是我们走到了 $(i,i)$ 之后,我们随便选择的一个方向,猜对和猜错的概率各占一半。而我们可以很容易发现所有紫色的(猜对的)边长度加起来是 $n$。

那么我们只要统计所有路径的红色的边产生的期望贡献,加上每条边紫色部分所产生的基础贡献 $n$ 即可。