【JSOI2015】非诚勿扰

本文主要是介绍【JSOI2015】非诚勿扰，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

Output

Sample Input

5 5
0.5
5 1
3 2
2 2
2 1
3 1

Sample Output

0.89

Solution

设f[i,j]表示第i个女选择第j个男的概率
设这个男的在这个女的中排名第r，这个女的的如意郎君列表长度为l
那么第一轮选中的概率是$(1-p)^{(r-1)}*p$
第二轮是$(1-p)^{(r-1)}*p*(1-p)^l$
第三轮是$(1-p)^{(r-1)}*p*(1-p)^{2l}$
第n轮是$(1-p)^{(r-1)}*p*(1-p)^{(n-1)l}$
这是一个等比数列！！！！
用公式求和，得

$$(1-p)^{(r-1)}*p*(1-(1-p)^{nl})\over 1-(1-p)^l$$
当 $n\rightarrow\infty$
因为 $1-p<0$
所以 $(1-(1-p)^{nl})\rightarrow 0$
所以概率为
$$(1-p)^{(r-1)}*p\over 1-(1-p)^l$$
f[i,j]就可以O（1）做了
那么答案就是 $\sum f[i,j]*f[k,l](k>i,l<j)$
这样直接枚举可以得30分
可以考虑优化
因为有值的f只有m个，那么只枚举这m个f
先将i从大到小枚举，这是为了保证k>l这个条件
然后枚举i这个女的的所有的男的，也就是j，在树状数组中查询1~j中的和就是答案
然后把f[i, ]加入树状数组
时间复杂度 $O(mlog_2(n))$

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define db double
#define N 501000
using namespace std;
int n,m,l[N],last[N],next[N],to[N],tot,b[N];
db p,t[N];
struct node{int x,y;
}a[N];
void putin(int x,int y)
{next[++tot]=last[x];last[x]=tot;to[tot]=y;
}
db mi(db a,int b)
{if(b==0) return 1;if(b==1) return a;db k=mi(a,b/2);k=k*k;if(b%2==1) k*=a;return k;
}
int lowbit(int a){return a&(-a);}
void insert(int x,db z)
{for(;x<=n;x+=lowbit(x)) t[x]+=z;
}
db get(int x)
{db ans=0;for(;x;x-=lowbit(x)) ans+=t[x];return ans;
}
int main()
{freopen("cross.in","r",stdin);freopen("cross.out","w",stdout);scanf("%d%d",&n,&m);scanf("%lf",&p);fo(i,1,m){int x,y;scanf("%d%d",&x,&y);putin(x,y);l[x]++;}db ans=0;fd(i,n,1){b[0]=0;for(int k=last[i];k;k=next[k]) b[++b[0]]=to[k];if(b[0]==0) continue;sort(b+1,b+b[0]+1);fo(j,1,b[0]){db jy=mi((1-p),j-1)*p/(1-mi(1-p,l[i]));ans+=jy*get(b[j]-1);}fo(j,1,b[0]){db jy=mi((1-p),j-1)*p/(1-mi(1-p,l[i]));insert(b[j],jy);}}printf("%.2lf",ans);
}

这篇关于【JSOI2015】非诚勿扰的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---