【CF367D】Sereja and Sets 题解

题目大意

  有 $m$ 个非空集合，他们两两交集为空，并集为 $[1, n]$。
  要你选若干个集合，假设他们的并排序后是数组 $b_1,\cdots,b_{|b|}$，给定 $d$，要求

1. $b_1 \le d$
2. $b_{i+1}−b_i \le d$
3. $n−d+1 \le b_{|b|}$

  最后问你最少选几个集合能满足要求。
  $n,d\le10^5,\ m \le 20$

题解

  问题转化成：$1$~$n$ 每个数都有一个颜色，要你在这个数轴上选一些数，使得两两间隔（包括开头、结尾）不超过 $d$，并且选出的颜色种类数最少。

  也就是说任意连续的 $d$ 个数中，至少有一个被选。假设这 $d$ 个数的颜色集合是 $S$，那么答案的颜色集合 $ans$ 必须与 $S$ 有交。
  也就是现在有 $n-d+1$ 个限制，你要求一个最小的 $ans$，使得 $ans$ 与所有限制有交。

  有交不好做，于是考虑无交，即看看哪些 $ans$ 是不可行的。

$$S1 \cap S2= \emptyset \Rightarrow S1 \subseteq \complement S2$$

  于是开一个 $2^{20}$ 的标记数组，把所有限制打上标记，然后从大到小合并标记，这样就知道哪些东西可以作为 $ans$ 哪些不可以了。