感觉今天人均 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$ 次。

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

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

本文链接：https://pst.iorinn.moe/archives/jzsim-3-13.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆