【ZRC-524】全排列 / 题解

Posted on

Description 有一个 $1$ 到 $n$ 的排列 $p_1,p_2,p_3,…,p_n$,你会对它进行若干轮操作,每一轮操作,你会保留序列中极大的数,也就是说对于每个数字,如果它比相邻的数字都大,那么会被保留下来。比如一个排列 $(3,2,5,1,4,6)$,经过一轮操作之后序列变成 $(3,5,6)$,第二轮操作之后序列变成 $(6)$,经过恰好 $2$ 轮之后序列里只有一个元素。 请问有多少个长度为 $n$ 的序列,经过恰好 $k$ 次操作之后,序列里只有一个元素,由于答案很大,对一个素数 $P$ 取模。 Idea ⾸先考虑给定⼀个排列,我们计算它⼏次会被消掉。 考虑这个排列的笛卡尔树,那么当⼀个数它的左⼦树或者右⼦树都被消掉的时候,它就会和它的祖先直接相邻,也就是⼀个⽐它⼤的数。 所以记 $dp[u]$ 表示笛卡尔树中 $u$ 这个点的⼦树什么时候被全部消完。那么有 $dp[u]=\max (dp[l],dp[r],\min (dp[l],dp[r])+1)$。 我们得到了⼀个 $\Theta(n)$ 的判断⼀个序列多少轮被消完的⽅法。 可以把这个 $dp$ 的过程直接改成计数。 令 $dp[u][k]$ 表示⼤⼩为 $u$ 的⼦树,能存活 $k$ 轮。$dp$ 的时候枚举最⼤值在哪⾥,分成左右两边计算。 因为最多存活 $\log n$ 轮,时间复杂度为 $\Theta(n^2\log ^2 n)$。 Code

【ZRC-529】Christmas Tree / 题解

Posted on

Description 众所周知,圣诞树是一棵 $n$ 个节点的树。 这意味着它将包含很多割点,这导致了结构不稳定。你需要为它添加一些边,使得割点不存在。 给出你的加边方案。 Idea 我们可以先考虑如果是割边的话应该怎么做。显然答案下界是 $\lceil \dfrac{l}{2} \rceil$ ,其中 $l$ 是叶节点个数 我们可以构造出这样的⽅案:令叶节点的权值为 1 ,⾮叶节点的权值为 0 ,求整棵树的带权重⼼ $c$。由于重⼼的每个⼉⼦的⼦树⾥都只有不超过 $\lfloor \dfrac{c}{2} \rfloor$ 个叶⼦,我们不难构造出⼀组⽅案使得每条边连接的两个叶⼦都来⾃于重⼼的不同⼉⼦的⼦树。 考虑割点。显然答案下界是 $\max(\max\{d_i\}-1,\lceil \dfrac{l}{2} \rceil)$ ,其中 $d_i$ 是点 $i$ 的度数。我们可以构造出这样的⽅案:注意到之前的⽅案⾥除了重⼼之外,每个点都保证了删掉它后,它的所有⼉⼦的⼦树依然是与重⼼所在的连通块连通的,固整个图也是连通的。 Code