BZOJ4481 JSOI2015非诚勿扰（概率期望+树状数组）-白红宇

BZOJ4481 JSOI2015非诚勿扰（概率期望+树状数组）

阅读量：4931 次

发布时间：2019-06-11

本文共 1174 字，大约阅读时间需要 3 分钟。

　　首先求出每个女性接受某个男性的概率。这个概率显然是一个无穷等比数列求和。

　　然后按编号从小到大考虑每个女性，维护出每个男性被选择的期望次数，BIT上查询后缀和即可。

　　需要long double。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 500010#define double long doubleint n,m;double p,tree[N],q[N],ans;vector
            
              a[N];double query(int k){ double s=0;while (k) s+=tree[k],k-=k&-k;return s;}void ins(int k,double s){ while (k<=n) tree[k]+=s,k+=k&-k;}int main(){#ifndef ONLINE_JUDGE freopen("bzoj4481.in","r",stdin); freopen("bzoj4481.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(),m=read();cin>>p; for (int i=1;i<=m;i++) { int x=read(),y=read(); a[x].push_back(y); } int cnt=0; for (int i=1;i<=n;i++) { sort(a[i].begin(),a[i].end()); int s=a[i].size(); double v=1; for (int j=0;j
             
              0; }#undef double double p=ans;printf("%.2f",p); return 0;}