长沙集训 $ Day 1 $ 2019-08-19

得分： $ 70 / 300 $

T1梦境

基本思路

此题是一个基本的贪心，将区间升序排序后，对于每个转折点，将包括该点的所有区间右端点放入小根堆中，取堆顶元素进行匹配后删除即可。

程序

program dream;

type tp=record
  l,r:longint;
end;

var
   a:array[0..200005]of tp;
   b,heap:array[0..200005]of longint;
   n,m,tot:longint;

procedure qsort1(l,r:longint);
var i,j,mid:longint;
    t:tp;
begin
  i:=l;
  j:=r;
  mid:=a[(i+j) shr 1].l;
  repeat
    while a[i].l<mid do inc(i);
    while a[j].l>mid do dec(j);
    if i<=j then begin
      t:=a[i];
      a[i]:=a[j];
      a[j]:=t;
      inc(i);
      dec(j);
    end;
  until i>j;
  if l<j then qsort1(l,j);
  if i<r then qsort1(i,r);
end;

procedure qsort2(l,r:longint);
var i,j,mid,t:longint;
begin
  i:=l;
  j:=r;
  mid:=b[(i+j) shr 1];
  repeat
    while b[i]<mid do inc(i);
    while b[j]>mid do dec(j);
    if i<=j then begin
      t:=b[i];
      b[i]:=b[j];
      b[j]:=t;
      inc(i);
      dec(j);
    end;
  until i>j;
  if l<j then qsort2(l,j);
  if i<r then qsort2(i,r);
end;

procedure insert(q:longint);
var i,j,t:longint;
begin
  inc(tot);
  i:=tot;
  heap[tot]:=q;
  while (i shr 1)<>0 do begin
    j:=i shr 1;
    if heap[j]>heap[i] then begin
      t:=heap[j];
      heap[j]:=heap[i];
      heap[i]:=t;
    end
      else exit;
    i:=j;
  end;
end;

procedure del;
var i,j,t:longint;
begin
  heap[1]:=heap[tot];
  heap[tot]:=2000000000;
  dec(tot);
  i:=1;
  while (i shl 1)<=tot do begin
    j:=i shl 1;
    if (j+1<=tot) and (heap[j+1]<heap[j]) then inc(j);
    if heap[i]>heap[j] then begin
      t:=heap[i];
      heap[i]:=heap[j];
      heap[j]:=t;
    end
      else exit;
    i:=j;
  end;
end;

procedure re;
var i:longint;
begin
  for i:=1 to n do
    read(a[i].l,a[i].r);
  for i:=1 to m do
    read(b[i]);
  qsort1(1,n);
  qsort2(1,m);
end;

procedure main;
var i,j:longint;
    ans:int64;
begin
  for i:=1 to 200005 do heap[i]:=2000000000;
  tot:=0;
  j:=1;
  ans:=0;
  for i:=1 to m do begin
    while (a[j].l<=b[i]) and (j<=n) do begin
      insert(a[j].r);
      inc(j);
    end;
    while heap[1]<b[i] do del;
    if heap[1]<>2000000000 then begin
      inc(ans);
      del;
    end;
  end;
  writeln(ans);
end;

begin
  read(n,m);
  re;
  main;
end.

T2玩具

基本思路

本题可以转化为，有一棵树，开始时只有一个根节点，之后有 $ n-1 $ 次操作，每次会将一个新的节点等概率的连接到一个已有的节点上，问操作完成后树的期望深度。

显然的概率 $ Dp $ ，假设已放入 $ i $ 个节点后，形成的森林中深度最大的子树中有 $ j $ 个节点。用 $ Dp[i,j] $ 记录其概率，则该状态只可能由两种情况扩展得到，分别是 $ Dp[i-1,j] $ 和 $ Dp[i-1,j-1] $ ，可得转移方程：

Dp[i,j]=Dp[i−1,j−1]⋅j−1i+Dp[i−1,j]⋅i−jiDp[i,j]=Dp[i-1,j-1] \cdot \frac{j-1}{i} + Dp[i-1,j] \cdot \frac{i-j}{i}

Dp[1,1]=1Dp[1,1]=1

用 $ f[i,j] $ 记录树中节点个数为 $ i $ 时，树的深度不超过 $ j $ 的概率， $ g[i,j] $ 记录节点个数为 $ i $ 的森林中，深度最深的子树深度不超过 $ j $ 的概率。可得状态转移方程：

g[i,j]=∑k=1if[k,j]⋅g[i−k,j]⋅Dp[i,k]g[i,j]=\sum_{k=1}^{i} f[k,j] \cdot g[i-k,j] \cdot Dp[i,k]

f[i,j]=g[i−1,j−1],j>0f[i,j]=g[i-1,j-1] , j>0

g[0,i]=1,i∈[0,n]g[0,i]=1 , i \in [0,n]

f[1,0]=1f[1,0]=1

f[i,0]=0,i∈[2,n]f[i,0]=0 , i \in [2,n]

则树的深度为 $ i $ 的概率可用 $ f[n,i]-f[n,i-1] $ 得到。

程序

program toy;
var
   dp:array[0..205,0..205]of longint;
   n,p:longint;

procedure first;
var i,j:longint;
    f:array[0..1005]of int64;
begin
  f[0]:=0;
  f[1]:=1;
  for i:=2 to 1000 do
    f[i]:=p-(p div i)*f[p mod i] mod p;
  dp[1,1]:=1;
  for i:=2 to n do
    for j:=1 to i do
      dp[i,j]:=(dp[i-1,j-1]mod p*(j-1)mod p*f[i]mod p+dp[i-1,j]mod p*(i-j)mod p*f[i]mod p) mod p;
end;

procedure main;
var i,j,k,ans:longint;
    f,g:array[0..205,0..205]of longint;
begin
  fillchar(f,sizeof(f),0);
  fillchar(g,sizeof(g),0);
  for i:=0 to n do
    g[0,i]:=1;
  for i:=1 to n do
    for j:=0 to n do begin
      if j=0 then begin
        if i=1 then f[i,j]:=1
          else f[i,j]:=0;
      end
        else f[i,j]:=g[i-1,j-1];
      for k:=1 to i do
        g[i,j]:=(g[i,j]+f[k,j] mod p*g[i-k,j] mod p*dp[i,k] mod p) mod p;
    end;
  ans:=0;
  for i:=1 to n do
    ans:=(ans+(f[n,i]-f[n,i-1])*i) mod p;
  if ans<0 then inc(ans,p);
  writeln(ans);
end;

begin
  read(n,p);
  first;
  main;
end.

T3飘雪圣域

基本思路

这题看上去像是在树上找连通块，其实和树根本没啥关系。容易想到，在 $ k $ 个节点中，只要两个节点之间连边，则连通块就会减少 $ 1 $ 个，所以我们只要知道区间内节点之间连边的数量，就可以算出连通块个数。

为了维护边的条数，可以将询问离线，将所有询问区间左端点升序排序，并将所有边按小顶点升序排序。之后用树状数组维护区间内边的条数，首先将所有边的大顶点放入树状数组，之后按照区间进行枚举，对于每一个区间，将小顶点小于区间左端点的边的大顶点从树状数组中删去，之后计算答案（$ l-r+1-边数 $)。

程序

program icekingdom;

type tp=record
  l,r:longint;
end;

type tp2=record
  l,r,num:longint;
end;

var
   e:array[0..200005]of tp;
   f:array[0..200005]of tp2;
   tree,ans:array[0..200005]of longint;
   n,q:longint;

procedure qsort1(l,r:longint);
var i,j,mid:longint;
    t:tp;
begin
  i:=l;
  j:=r;
  mid:=e[(i+j) shr 1].l;
  repeat
    while e[i].l<mid do inc(i);
    while e[j].l>mid do dec(j);
    if i<=j then begin
      t:=e[i];
      e[i]:=e[j];
      e[j]:=t;
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<r then qsort1(i,r);
  if l<j then qsort1(l,j);
end;

procedure qsort2(l,r:longint);
var i,j,mid:longint;
    t:tp2;
begin
  i:=l;
  j:=r;
  mid:=f[(i+j) shr 1].l;
  repeat
    while f[i].l<mid do inc(i);
    while f[j].l>mid do dec(j);
    if i<=j then begin
      t:=f[i];
      f[i]:=f[j];
      f[j]:=t;
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<r then qsort2(i,r);
  if l<j then qsort2(l,j);
end;

procedure re;
var i,x,y:longint;
begin
  for i:=1 to n-1 do begin
    read(x,y);
    if x>y then begin
      e[i].l:=y;
      e[i].r:=x;
    end
      else begin
        e[i].l:=x;
        e[i].r:=y;
      end;
  end;
  for i:=1 to q do begin
    read(f[i].l,f[i].r);
    f[i].num:=i;
  end;
  qsort1(1,n-1);
  qsort2(1,q);
end;

function low(q:longint):longint;
begin
  exit(q and -q);
end;

procedure add(x,q:longint);
begin
  while x<=n do begin
    inc(tree[x],q);
    inc(x,low(x));
  end;
end;

function sum(x:longint):longint;
begin
  sum:=0;
  while x>=1 do begin
    inc(sum,tree[x]);
    dec(x,low(x));
  end;
end;

procedure main;
var i,j:longint;
begin
  for i:=1 to n-1 do
    add(e[i].r,1);
  j:=1;
  for i:=1 to q do begin
    while (j<n) and (e[j].l<f[i].l) do begin
      add(e[j].r,-1);
      inc(j);
    end;
    ans[f[i].num]:=f[i].r-f[i].l+1-sum(f[i].r)-sum(f[i].l);
  end;
  for i:=1 to q do
    writeln(ans[i]);
end;

begin
  read(n,q);
  re;
  main;
end.