A. 岛屿
题面link
赛时
一眼期望概率,扔惹。
赛后&&正解
咳咳,以下思路和言论来自机房大蛇魔法少女
我只是记录一下!不是我说的!!!
考虑题目给出的第一个有用的样例
rtttttttttttttttttt:
按题目方式连边:
太恶心了!!移动一下它们的位置。
它们 ——> 他/她们
rt:
将以下结构命名为“成年人”和“儿童” (\(x\)个成年人\(y\)个儿童)
考虑先连(杀)儿童:
情况一:
自~ 己~ 连~ 自~ 己~(他管这个叫“水仙”)
形成了一个连通块,然后他就不能连边了,他死啦~
这是有贡献的死,我们把这个叫做好死法
情况二:
自~ 己~ 连~ 儿~ 童~(他管这个叫“***”)
没有形成一个连通块,但他不能连边了,因为他被合并了,他死啦~
这是没有贡献的死,我们把这个叫做坏死法
情况三:
自~ 己~ 连~ 成~ 人~(他管这个叫“***”)
同上,坏死法
所以儿童有两种死法,每次死掉一个儿童,是好死法(有贡献)的概率是:
\[\frac{1}{当前儿童数+当前成人数 \times 2}
\]
考虑再连(杀)成年人:
可以先钦定该边被连
(因为第一条边无论如何连都可以通过移动人的位置变成这样的连法)
情况一:
自~ 己(的)~ 连~ 自~ 己(的)~(他管这个叫“***”)
有贡献,是好死法
情况二:
自~ 己(的)~ 连~ 别~ 人(的)~(他管这个叫“***”)
没贡献,是坏死法。
以下是另一种情况二:
同样没贡献,是坏死法。
所以成年人有两种死法,每次死掉一个成年人,是好死法(有贡献)的概率是:
\[\frac{1}{当前成人数 \times2-1}
\]
一个一个杀,就杀光啦哈哈哈哈哈哈哈哈哈哈哈
代码
#include<bits/stdc++.h>
using namespace std;
int x,y;
int tot=1;
double ans;
int main()
{freopen("island.in","r",stdin);freopen("island.out","w",stdout);cin>>x>>y;for(int i=y;i>0;i--){ans+=1.0/(i+x*2);} for(int i=x;i>0;i--){ans+=1.0/(i*2-1);}printf("%.10lf",ans);return 0;
}