期望单调性

正睿OJ 石子

满分做法：

本题应用了期望的线性性：E（x+y）= E（x）+ E（y）。取走第一堆石子期望其实就是它之前的石堆数+1。这时我们的问题就转化为求取走第一堆之前的期望长度。

令Pi表示第 i 堆石子在第 1 堆之前被取走的概率，因为它只跟第一堆的相对位置有关，所以它的值就是为\(\frac{a[i]}{a[1]+a[i]}\),最后的期望长度就是他们相加。

ans=\(\sum_{i=2}^{n}\frac{a[i]}{a[1]+a[i]}+1\)。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int maxm=1e5+7;
int n;
int a[maxm];
double ans=0;
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
 scanf("%d",&a[i]);
 ans=1.0;
 for(int i=2;i<=n;i++)
 ans+=(double)a[i]/(double)(a[1]+a[i]);
 printf("%.7lf\n",ans);
 return 0;
}

CF280C Game on Tree

满分做法：

根据期望的线性性，答案应该为所有点被染的期望之和。而每个点被染色的方式为他的深度，需要一次操作，所以每个点被染色的期望为\(\frac{1}{dep[i]}*1\)。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int maxm=2e5+7;
int n;
int pre[maxm],last[maxm],other[maxm],l;
int dep[maxm];
double ans=0;
void add(int x,int y)
{
 l++;
 pre[l]=last[x];
 last[x]=l;
 other[l]=y;
}
void dfs(int x,int fa)
{
 ans+=1.0/(double)dep[x];
 for(int p=last[x];p;p=pre[p])
 {
   int v=other[p];
   if(v==fa) continue;
   dep[v]=dep[x]+1;
   dfs(v,x);
 }
}
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n-1;i++)
 {
   int x,y;
   scanf("%d%d",&x,&y);
   add(x,y);
   add(y,x);
 }
 dep[1]=1;
 dfs(1,0);
 printf("%.10lf\n",ans);
 return 0;
}