题解 P4934 【礼物】

· · 题解

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

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

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

则有

f[i]=\max f[i\text{二进制表示下少一个}1]+v[i] 然后怎么实现少一个$1$呢。 只需要定义一个$j=i$，每次$i\ xor\ (j\&-j),j=j\ xor\ j\&-j $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;
}