【BZOJ4481&JSOI2015】非诚勿扰（数学期望）

听说JSOI有版权问题就不放图了

如果前面的文章里的图需要删掉请通知我

题意:有一些女的要挑一些男的，挑中的几率均为p。一个男的可以无限次被挑中。若女a选中男b，女c选中男d,a<c,b>d则对答案有1的贡献。问期望总贡献。

思路：我们设女x选中男y的几率是p(X,Y)，可以预处理出。

设y为女x喜欢的第a人。

则P(x,y)=(1-p)^a-1*p+(1-p)^m+a-1*p+... 无限等差数列求和

=a1/(1-q) a1=(1-p)^(a-1)*p,q=(1-p)^m

先将关系双关键字递增排序那么用树状数组统计前缀概率和

没了

 var x,y:array[..]of longint;

     t:array[..]of extended;

     mi:array[..]of extended;

     n,m,i,now,j,k:longint;

     tmp,ans,p:extended;

 function lowbit(x:longint):longint;

 begin

  exit(x and (-x));

 end;

 procedure add(x:longint;y:extended);

 begin

  while x> do

  begin

   t[x]:=t[x]+y;

   x:=x-lowbit(x);

  end;

 end;

 function sum(x:longint):extended;

 begin

  sum:=;

  while x<=n do

  begin

   sum:=sum+t[x];

   x:=x+lowbit(x);

  end;

 end;

 procedure swap(var x,y:longint);

 var t:longint;

 begin

  t:=x; x:=y; y:=t;

 end;

 procedure qsort(l,r:longint);

 var mid1,mid2,i,j:longint;

 begin

  i:=l; j:=r; mid1:=x[(l+r)>>]; mid2:=y[(l+r)>>];

  repeat

   while (mid1>x[i])or(mid1=x[i])and(mid2>y[i]) do inc(i);

   while (mid1<x[j])or(mid1=x[j])and(mid2<y[j]) do dec(j);

   if i<=j then

   begin

    swap(x[i],x[j]);

    swap(y[i],y[j]);

    inc(i); dec(j);

   end;

  until i>j;

  if l<j then qsort(l,j);

  if i<r then qsort(i,r);

 end;

 begin

  assign(input,'cross.in'); reset(input);

  assign(output,'cross.out'); rewrite(output);

  readln(n,m);

  readln(p);

  for i:= to n do read(x[i],y[i]);

  qsort(,m);

  mi[]:=;

  for i:= to n do mi[i]:=mi[i-]*(-p);

  now:=;

  for i:= to n do

  begin

   j:=now;

   while x[j]=i do inc(j);

   for k:=now to j- do

   begin

    tmp:=mi[k-now]*p/(-mi[j-now]);

    //writeln(tmp);

    ans:=ans+tmp*sum(y[k]+);

    add(y[k],tmp);

   end;

   now:=j;

  end;

  writeln(ans::);

  close(input);

  close(output);

 end.

巴特西

【BZOJ4481&JSOI2015】非诚勿扰（数学期望）

最新文章

热门文章