长沙集训 $ 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] $ ,可得转移方程:
用 $ f[i,j] $ 记录树中节点个数为 $ i $ 时,树的深度不超过 $ j $ 的概率, $ g[i,j] $ 记录节点个数为 $ i $ 的森林中,深度最深的子树深度不超过 $ j $ 的概率。可得状态转移方程:
则树的深度为 $ 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.