Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2) 题解

[toc]

AC代码

A题和C题是屑题，不做了。

B. Lord of the Values

一种方案：2 1 1 2 1 1 。

D. Love-Hate

有 $n$ 个人，$m$ 种货币，每个人对于每种货币都有两种态度：$1$ 表示喜欢，$0$ 表示不喜欢，每个人喜欢的货币种类数量不超过 $p$ 。现在请你找出一个最大的货币子集，使得至少 $\lceil \frac{n}{2}\rceil$ 个人喜欢该子集中的所有货币。

$n\leq 2\times 10^5,m\leq 60,p\leq 15$ 。

看见至少 $\lceil \frac{n}{2}\rceil$ 个人这个条件后就容易想到随机化的思想，比如 ECF2019 H 。因为我们随机选一个人，那么他在答案子集中的概率至少是 $\frac{1}{2}$ ，只要枚举足够多次，那么就只有 $\frac{1}{2}^p(p为枚举次数)$ 的概率无法选中答案子集中的一个人，可以忽略不计。

选中某个人 $c$ 后，可供我们选择的子集就只能属于 $c$ 喜欢的所有货币这一全集了，根据数据范围，该子集大小不超过 $15$ ，显然可以暴力枚举。

然后考虑如何快速判断某个子集中是否至少含有一半以上的人喜欢该子集所代表的货币，注意到：如果某人喜欢集合 $(a,b,c)$ ，那么他必定喜欢 $(a,b,c)$ 的所有子集，例如 $(a,b),(a,c)$ 等。因此我们可以计算出一个子集前缀和，这个子集前缀和中的每个状态 $s$ 代表喜欢该状态的人数，这一操作可以通过 $O(3^p)$ 暴力枚举子集，或者 $O(p2^p)$ 进行SoSDP来完成。

E. Crypto Lights

有 $n$ 个灯泡排成一列，初始状态下所有灯泡都是灭的。现在执行一种操作：每一轮，在所有灭着的灯泡中等概率地选择一个，将其变为亮的，直到存在一段连续的长度为 $k$ 的区间中出现了两个亮着的灯泡时该操作结束。询问操作结束时亮着的灯泡的期望个数。

$2\leq k\leq n\leq 10^5$ 。

我们将结合样例1来解释如何解决本问题，如上图给出了样例1的排列树结构。

设 $p_i$ 表示恰好有 $i$ 个 $1$ 时出现了某一段连续 $k$ 个位置中出现了至少两个 $1$ 的概率。那么期望就是 $\sum_{i=1}^nip_i$ 。而 $p_i$ 在上方的排列树中可以表示为：

$$
\displaystyle{p_i=\frac{第i层中叶子节点个数}{第i层中节点个数}\times 到达第i层的概率}
$$

其中，到达第 $i$ 层的概率是从第 $i-1$ 层传递下来的，等于 $\frac{第i-1层中非叶子节点个数}{第i-1层中节点个数}\times 到达第i-1层的概率$ 。因此，我们需要考虑的就是：如何求出第 $i$ 层中叶子节点个数和第 $i$ 层中节点个数，这等价于一个子问题：大小为 $n$ 的二进制向量中已有 $i$ 个 $1$ ，且不存在一段长度为 $k$ 的区间中存在两个 $1$ 。

这个经典问题在前一场CF中刚刚出现过，CF1526E。。。我们将这个子问题用数学语言表达出来：设这 $i$ 个 $1$ 的位置分别为 $x_1,x_2,\cdots, x_i$ ，那么就满足一下的方程：

令 $y_i=x_i-(i-1)k$ 就变成了下方的连续不等式：

再令 $z_i=y_i+i$ 就变成了下方的连续不等式：

上式的合法序列数量可以直接求出是 $\binom{n-(i-1)(k-1)}{i}$ 。预处理组合数之后，本题即可 $O(n\log n)$ 求解了。