自动搬运

查看原文

来自洛谷，原作者为

	Huami360 菜是原罪

搬运于2025-08-24 22:05:26，当前版本为作者最后更新于2018-10-23 08:01:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实呢这题没必要搞的那么复杂。无需建图跑拓扑排序。

仍然是官方题解满分做法的思路，只不过我们把连边改成$DP$。

设$f[i]$表示以$i$这个值结尾的最长链的长度

则有

$v[i]$表示数列里是否存在这个数，是则为$1$。

然后怎么实现少一个$1$呢。

只需要定义一个$j=i$，每次$i\ xor\ (j\&-j),j=j\ xor\ j\&-j$

$j\&-j$即$lowbit$运算，取出二进制表示下最后一个$1$，

$i\ xor\ (j\&-j)$就是删掉$i$中$j$的最后一位，同时$j$每次删去一位，我们就能实现每次删去$i$中的一个$1$了。

去掉快读后代码其实很短，不开氧气跑$484ms$

#include <cstdio>
#include <vector>
#define re register
const int MAXN = 2000010;
namespace IO{
    int xjc; char ch;
    inline int read(){
        xjc = 0; ch = getchar();
        while(ch < '0' || ch > '9') ch = getchar();
        while(ch >= '0' && ch <= '9'){ xjc = xjc * 10 + ch - '0'; ch = getchar(); }
        return xjc;
    }
}using namespace IO;
inline int max(int a, int b){
    return a > b ? a : b;
}
int f[MAXN], v[MAXN], n, k;
std::vector <int> g[30];
int main(){
    n = read(); k = read();
    for(re int i = 1; i <= n; ++i) v[read()] = 1;
    int Max = (1 << k) - 1;
    for(re int i = 0; i <= Max; ++i){
       for(re int j = i; j; j ^= j & -j) f[i] = max(f[i], f[i ^ (j & -j)]);
       if(v[i]) g[++f[i]].push_back(i);
    }
    printf("1\n%d\n", f[Max]);
    for(int i = 1; i <= f[Max]; ++i){
       printf("%d ", g[i].size());
       for(std::vector <int> :: iterator it = g[i].begin(); it != g[i].end(); ++it) printf("%d ", *it);
       putchar('\n');
    }
    return 0;
}