题目链接:CF1556H DIY Tree

题意:

给定 $n$ 个点,$\binom{n}{2}$ 条带权边,前 $k$ 个点是特殊点,每个特殊点 $i$ 有一个度数限制 $d_i$,求一棵边权和最小的生成树,使得该生成树中每个特殊点 $i$ 的度数 $\le d_i$。

$2\le n\le 50, 1\le k\le \min(n-1, 5)$。

- 阅读剩余部分 -

题目链接:[AGC028E] High Elements

题意:

你有一个 $1,2,\cdots,n$ 的排列 $P$。设一个长度为 $n$ 的 $01$ 字符串 $S$ 合法,当且仅当,先设两个空序列 $A,B$,我们按照 $1$ 到 $n$ 的顺序,若 $S$ 当前位为 $1$ 则把当前位的 $P$ 添加到序列 $A$ 的末尾,否则添加到序列 $B$ 的末尾,使得 $A,B$ 的前缀最大值个数相等。求字典序最小的合法字符串 $S$。

$1\le n\le 2\times 10^5$

- 阅读剩余部分 -

题目链接:[CTS2019] 珍珠

题意:

有 $n$ 个在范围 $[1,D]$ 内的整数均匀随机变量。

求至少能选出 $m$ 个瓶子,使得存在一种方案,选择一些变量,并把选出来的每一个变量放到一个瓶子中,满足每个瓶子都恰好装两个值相同的变量的概率。

$1\le D\le 10^5, 1\le n\le 10^9, 0\le m\le 10^9$。

- 阅读剩余部分 -