luogu4934 礼物

题目描述

__stdcall决定给你$n$个礼物,每个礼物有一个魔力值$a_i$。这些礼物的魔力值都是独一无二的,两两互不相同。这些礼物都有着神奇的魔力,如果两个礼物$i, j$的魔力值满足 $a_i \& a_j \ge min(a_i, a_j)$ ,那么这两个礼物的魔力将会相互抵消,因此它们不能放在一个箱子里。

作为发礼物苦力的ljt12138的箱子并不多,不过幸运的是,每个箱子都足够大。现在他请求你帮助他合理分配,用尽可能少的箱子装下所有礼物。换言之,使得每个礼物都被恰好装入一个箱子中,且同一个箱子中的礼物魔力不会相互抵消。如果有多种合法的方案,你只需要给出任意一种

ljt12138十分善良,如果你只能求出所需要的箱子数,也可以获得该测试点60%的分数,关于这一点,请参考下面的提示与说明。

输入格式

  • 第一行两个数$n$和$k$,$n$为礼物总数,$k$为一个参数,方便你进行计算。
  • 第二行$n$个两两不同的数$a_i$,满足$0\le a_i < 2^k$,表示礼物的魔力值。

输出格式

  • 第一行输出一个数。如果你不希望输出方案,请输出0;如果你希望输出方案,请输出1。如果你在这一行输出了不符合要求的信息,将被判为$WA$

  • 第二行一个数$m$,表示你将礼物装到了$m$个箱子里。

  • 如果你在第一行输出了$1$,接下来$m$行,每行表示一个箱子:首先一个数$s_i$,表示当前箱子中礼物的个数;接下来$s_i$个数,表示当前子集。

样例输入

5 3
0 4 7 1 6 

样例输出

1
4
1 0
2 1 4
1 6
1 7 

说明

$n\le 1000000$,$k\le 20$。


分析

对于$a\&b=b$,即$a$包含$b$,则由$a$向$b$连边,建出DAG,则问题转化为最小反链覆盖,只要求出最长链即可。

但这样建图边数是$O(n^2)$的。可以发现,我们建了许多无用的边,例如$a\to b\to c$,这时候建$a\to c$的边就是无效的,因为不可能出现在最长链中。也就是说,我们只需要对层数较少的包含关系建边。

考虑如下建边方式:把$[0,2^k)$全部加入图中,并从$i$向【$i$去掉一个二进制位的$1$】连边。则:

$$f(u)=\max\{f(v)\}+p(u)$$

其中$p(u)$表示$u$是否在输入中出现。

这样建边就把边数优化到了$O(nk)$。事实上代码中并不需要建边,直接枚举去掉哪个$1$即可。

复杂度$O(nk)$。输出方案时,把最长链相等的点放在一起。

代码

#include <bits/stdc++.h>

const int N = 1e6+50;
const int S = (1 << 20) + 50;

int n, k;
bool p[S];
int f[S];
std::vector<int> box[25];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1, val; i <= n; i++) {
        scanf("%d", &val);
        p[val] = true;
    }
    int tot = 1 << k;
    for (int i = 0; i < tot; i++) {
        for (int j = i; j; j ^= j & -j)
            f[i] = std::max(f[i], f[i ^ (j & -j)]);
        if (p[i]) box[++f[i]].push_back(i);
    }
    printf("1\n%d\n", f[tot-1]);
    for (int i = 1; i <= f[tot-1]; i++) {
        int siz = box[i].size();
        printf("%d ", siz);
        for (int j = 0; j < siz; j++)
            printf("%d ", box[i][j]);
        puts("");
    }
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论