PKUWC2019题解

这里其实只放一下题面和一些提示,大家评一评有几道题可做

题面全部蒯自xzz的博客

Day 1

T1

题面

一个有向图,每一条边可能存在也可能不存在,求拓扑序列数量的期望乘$2^m$

没有重边自环,$n\leq 20$

提示

签到题

T2

题面

定义虚树$T(S)$表示一些点的集合,$x$存在于$T(S)$中当且仅当$x\in S$或者在树上删除$x$后$S$集合存在两个点不连通

树上每个点都有一个颜色$a_i$,$A_i=\left{x|a_x=i\right}$,对每个$k(k\in [1,m])$求一个序列$x_1,x_2,\cdots,x_k$满足$x_1<x_2<\cdots<x_k$而且存在一个$y$满足对于所有的$i$都有$y\in T(A_{x_i})$
$$
1\leq m\leq n\leq 10^5
$$
提示

我不会

T3

题面

两个地主打牌,每个地主有$20$张牌

定义两副牌不相等为,任意出一手牌,两副牌有一副能接上,有一副不能接上。否则这两副牌相等

规定两个地主的牌必须包含一些牌,剩下的可以任意选(但是必须可以从一副扑克中选出),问方案数

提示

我不会

结果

$Day\;1:7+0+0=7$

Day 2

T1

题面

求满足以下条件的序列$x_1,x_2,\cdots,x_n$数量:

  1. $x_i$是非负整数,而且$x_i\;\mathrm{and}\;a_i=a_i$

  2. $x_i\in [l_i,r_i]$且对$\forall i > 1,x_{i-1} < x_i$

其中$a,l,r$是给定的。

$$
n\leq 100,l_i,r_i,a_i\leq 2^{60}
$$
提示

区间数位$dp$

T2

题面

有一张有向图,建一个新图,对这个有向图的每个环(环要满足没有重复的点)在新图中建一个点,如果两个环有公共边就在新图中给这两个环对应的点连一条无向边。问新图的联通块数。

提示

$SCC$里面求点双

T3

题面

有一堆点$a_i​$,每次选一个新点$O​$,对原来的每个点$a_i​$做一个圆,半径为$a_i​$到$O​$的距离

问最多可以删掉多少个圆满足删圆后圆的面积并不变

提示

$n^2$很简单正解差不多

结果

$Day\;2: 23+21+0=44$

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×