题目描述
__stdcall决定给你n个礼物，每个礼物有一个魔力值ai。这些礼物的魔力值都是独一无二的，两两互不相同。这些礼物都有着神奇的魔力，如果两个礼物 i,j的魔力值满足 ai&aj≥min(ai,aj) ，那么这两个礼物的魔力将会相互抵消，因此它们不能放在一个箱子里。这里的 &是按位与运算符，如果你对这一运算不够了解，请参考：https://baike.baidu.com/item/%E6%8C%89%E4%BD%8D%E4%B8%8E/9601818?fr=aladdin
作为发礼物苦力的ljt12138的箱子并不多，不过幸运的是，每个箱子都足够大。现在他请求你帮助他合理分配，用尽可能少的箱子装下所有礼物。换言之，使得每个礼物都被恰好装入一个箱子中，且同一个箱子中的礼物魔力不会相互抵消。如果有多种合法的方案，你只需要给出任意一种。
ljt12138十分善良，如果你只能求出所需要的箱子数，也可以获得该测试点60%的分数，关于这一点，请参考下面的提示与说明。
输入输出格式
输入格式：
-
第一行两个数n和k，n为礼物总数，k为一个参数，方便你进行计算。
-
第二行n个两两不同的数ai，满足0≤ai<2k，表示礼物的魔力值。
输出格式：
-
第一行输出一个数。如果你不希望输出方案，请输出0；如果你希望输出方案，请输出1。如果你在这一行输出了不符合要求的信息，将被判为WA。
-
第二行一个数m，表示你将礼物装到了m个箱子里。
-
如果你在第一行输出了1，接下来m行，每行表示一个箱子：首先一个数 si，表示当前箱子中礼物的个数；接下来 si个数，表示当前子集。
输入输出样例
说明
附加样例：
你可以在 https://pan.baidu.com/s/1A8_ZA4yXXi5y6771x9JKUw 下载附加样例。
关于输出方案：
-
如果你在第一行输出了0，而正确回答了最小所需的箱子数，将获得测试点60%的分数。
-
如果你在第一行输出了1，正确回答了最小所需的箱子数，但没有给出正确的方案，也将获得该测试点60%的分数。
-
如果你没有正确回答最小所需的箱子数，将不会获得该测试点的分数。
-
请选手注意，如果你未按照上述格式输出答案，将无法获得任何分数。
数据 n,k的关系由下面的表格给出：
| 数据编号 | nn | kk |
|---|---|---|
| 11 | 55 | 33 |
| 22 | 66 | 33 |
| 33 | 77 | 1010 |
| 44 | 88 | 1010 |
| 55 | 1616 | 77 |
| 66 | 1717 | 88 |
| 77 | 1717 | 99 |
| 88 | 1717 | 2020 |
| 99 | 20002000 | 1717 |
| 1010 | 25002500 | 1818 |
| 1111 | 30003000 | 1919 |
| 1212 | 30003000 | 2020 |
| 1313 | 2500025000 | 1515 |
| 1414 | 2500025000 | 1515 |
| 1515 | 5000050000 | 1616 |
| 1616 | 5000050000 | 1616 |
| 1717 | 250000250000 | 1818 |
| 1818 | 500000500000 | 1919 |
| 1919 | 10000001000000 | 2020 |
| 2020 | 10000001000000 | 2020 |
一句话题解：偏序集最小反链覆盖等于最长链，优化建图。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int siz=2000050; 4 int n,m,a[siz],t; 5 int dis[siz]; 6 bool vis[siz]; 7 int head[siz],nex[siz],tot[siz]; 8 vector <int > s[20]; 9 void add(int x,int y) 10 { 11 ++tot[x]; 12 nex[y]=head[x]; 13 head[x]=y; 14 } 15 int main() 16 { 17 scanf("%d%d",&n,&m); 18 t=(1<<m)-1; 19 for(int i=0;i<n;++i) 20 { 21 scanf("%d",&a[i]); 22 vis[a[i]]=true; 23 } 24 for(int i=t;i>=0;--i) 25 { 26 if(vis[i]) 27 ++dis[i]; 28 for(int j=1;j<t;j<<=1) 29 if(i&j) 30 dis[i^j]=max(dis[i^j],dis[i]); 31 } 32 for(int i=0;i<=t;++i) 33 if(vis[i]) 34 s[dis[i]].push_back(i); 35 printf("%d %d",1,dis[0]); 36 for(int i=dis[0];i>=1;--i) 37 { 38 int tmp=s[i].size(); 39 printf(" %d",tmp); 40 for(int j=0;j<tmp;++j) 41 printf(" %d",s[i][j]); 42 43 } 44 return 0; 45 }