绝渡逢舟系列题解

题面链接: http://pan.baidu.com/s/1gdQi0fD 密码: ji8k

绝渡逢舟1

绝渡逢舟2

绝渡逢舟3

期望问题

题目大意

按顺时针或逆时针给定凸包上的n个点,随机选取内部或边上的整点,求两点为正方形对角线的正方形面积的期望

题解

有 sum 个合法点(内部或边上),那么面积的期望为

ans=12∑sumi=1∑sumj=1(xi−xj)2+(yi−yj)2n⋅(n−1)

对于分子 x和y是同一形式 所以我们只看 ∑sumi=1∑sumj=1(xi−xj)2
打开括号后我们得到

   ∑i∑j(xi2+xj2)−2⋅∑i∑jxi⋅xj=2⋅sum⋅∑ixi2−2⋅(∑ixi)2

这样我们只需要求两个前缀和即可
剩下的问题就是统计所有点的个数和坐标
如果暴力用扫描线去扫会T,但是我们发现对于一条扫描线所扫到的点 x 坐标相同,所以用个数*坐标值直接计入即可
一条扫描线同一时间会扫到凸包上的两条边,用交到的两个点求一下个数即可

const
  maxn=100005;
  maxm=1000005; 
var
  x,y:array[0..maxn]of int64; 
  wy,wx:array[0..maxm*2,1..2]of real; // k=(y1-y2)/(x1-x2); b=(x1y2-x2y1)/(x1-x2); 
  i,j,k:longint; 
  n,l,r,u,d,e,f,xxx,yyy:longint; 
  sum,summ,a,b,c:int64; 
  ans,x1,x2,y1,y2:real; 
procedure swap(var a,b:real); 
var c:real;
begin
  c:=a; a:=b; b:=c;
end;

function xx(a:real):int64;
begin
if trunc(a)<a
then exit(trunc(a)+1)
else exit(trunc(a));
end; 

function g(a,b:real):int64; 
var d,c:int64;
begin
  d:=trunc(b);
  c:=xx(a); 
exit(d-c+1);
end; 

begin
  assign(input,'square.in'); assign(output,'square.out'); reset(input); rewrite(output);
  readln(n);
  readln(x[1],y[1]);
  l:=x[1]; r:=x[1]; u:=y[1]; d:=y[1]; 
  x[n+1]:=x[1]; y[n+1]:=y[1];
for i:=2 to n do
begin
      readln(x[i],y[i]); 
if x[i]<l then l:=x[i];
if x[i]>r then r:=x[i]; 
if y[i]<d then d:=y[i];
if y[i]>u then u:=y[i]; 
end; 
for i:=0 to r-l do
begin
      wx[i,1]:=maxm;
      wx[i,2]:=maxm;
end;
for i:=0 to u-d do
begin
      wy[i,1]:=maxm;
      wy[i,2]:=maxm; 
end;
  xxx:=l; yyy:=d; 
if xxx<0 then inc(x[1],-xxx);
if yyy<0 then inc(y[1],-yyy); 
  l:=maxm; r:=-maxm; u:=-maxm; d:=maxm;
for i:=2 to n+1 do
begin
if xxx<0 then inc(x[i],-xxx); 
if yyy<0 then inc(y[i],-yyy);
if x[i]<l then l:=x[i]; 
if x[i]>r then r:=x[i];
if y[i]<d then d:=y[i]; 
if y[i]>u then u:=y[i];
if x[i]=x[i-1]
then begin a:=0; b:=1; c:=x[i]; end
else begin a:=y[i]-y[i-1]; b:=x[i]-x[i-1]; c:=x[i]*y[i-1]-x[i-1]*y[i]; end; 
if x[i]<x[i-1]
then begin e:=x[i]; f:=x[i-1]; end
else begin e:=x[i-1]; f:=x[i]; end;
for j:=e to f-1 do
if wx[j,1]=maxm
then wx[j,1]:=(a*j+c)/b 
else
if wx[j,2]=maxm 
then wx[j,2]:=(a*j+c)/b;
if y[i]=y[i-1] 
then begin a:=1; b:=0; c:=-y[i]; end
else begin a:=y[i]-y[i-1]; b:=x[i]-x[i-1]; c:=x[i]*y[i-1]-x[i-1]*y[i]; end; 
if y[i]<y[i-1]
then begin e:=y[i]; f:=y[i-1]; end
else begin e:=y[i-1]; f:=y[i]; end;
for j:=e to f-1 do
if wy[j,1]=maxm
then wy[j,1]:=(j*b-c)/a 
else
if wy[j,2]=maxm
then wy[j,2]:=(j*b-c)/a;
end; 
  sum:=0;
for i:=l to r do
begin
if wx[i,1]>wx[i,2] then swap(wx[i,1],wx[i,2]); 
      sum:=sum+g(wx[i,1],wx[i,2]);
end; 
  x1:=0; x2:=0;
for i:=l to r do
begin
      x1:=x1+(g(wx[i,1],wx[i,2])*int64(i)); 
      x2:=x2+(g(wx[i,1],wx[i,2])*int64(i)*int64(i));
end;
  ans:=0;
  ans:=(2*sum*x2-2*x1*x1)/2/sum/(sum-1); 
  y1:=0; y2:=0;
for i:=d to u do
begin
if wy[i,1]>wy[i,2] then swap(wy[i,1],wy[i,2]); 
      y1:=y1+(g(wy[i,1],wy[i,2])*int64(i));
      y2:=y2+(g(wy[i,1],wy[i,2])*int64(i)*int64(i)); 
end;
  ans:=ans+(2*sum*y2-2*y1*y1)/2/sum/(sum-1); 
  writeln(ans:0:10);
  close(input); close(output);
end.

亦或问题

题目大意

给定n(n≤50000)个数,询问前m大的ai  xor  aj的和

题解

首先因为每对会出现2次,所以最后要除以2,我们考虑求前2∗m大的答案
亦或,还是最值相关,我们对所有数建立Trie树
如果我们求出了第 2∗m 大的得数是多少,我们只要对每个数求出它亦或别的数后大于 2∗m 大的数的和计入答案即可
具体来说就是,