dw做旅游网站教程/北京网站优化推广方案

题目大意

给定一个正整数集合$S$与正整数$n$，你要构造出一个包含$n$个元素的新正整数集合$S$，使其包含该给定的集合$S$为子集，每个元素均不超过$2^{60}-1$，且满足下列条件：

1. 对于集合中的任意两个不同元素$A$和A&B>0;
2. 对于集合中的任意三个不同元素$A$、$B$、$C$，A&B&C=0。

其中，&是二进制下的按位与运算。假如满足要求的集合不存在，输出-1；否则，假如有多个解，输出将元素排序后字典序最小的一个。

题解

乱搞构造。

将已经给出来的数，转化为二进制，然后列出来。如15,20

$$\begin{matrix} 0&0&1&1&1&0\\ 0&1&0&1&0&1 \end{matrix}$$
如果我们要在下面构造一个新的数，为了满足条件1，我们要使新的数，从每一行选一个1，复制到新的数来，比如乱搞一个：
$$\begin{matrix} 0&0&1&1&1&0\\ 0&1&0&1&0&1\\ -&-&-&-&-&-\\ 0&0&1&1&0&0 \end{matrix}$$
但是，这种情况不符合条件2，如果把这三个数&起来，第三位将是1，所以我们必须保证每一列的1的个数不能超过2。

那就这样构造吧：

$$\begin{matrix} 0&0&1&1&1&0\\ 0&1&0&1&0&1\\ -&-&-&-&-&-\\ 0&0&1&0&0&1 \end{matrix}$$
如果这时候还要添加1个怎么办呢？刚刚我们添加的那一排数，已经没有1可以复制到下一排了，因为那两列的1的个数已经达到2了。
我们只能在刚刚构造的数上再添加1，来保证后面数的可以&它。
我们只能在没有1的列来添加这个新的1，才能使后面数的可以复制这个1。
由于后面每个数都要消耗这个数一个1，所以我们要在这个数上添加x个1（x为后面还要构造的数的个数）

在这个样例，我们还要构造一个数，所以此时只需要在第3行第6列变为1。

$$\begin{matrix} 0&0&1&1&1&0\\ 0&1&0&1&0&1\\ -&-&-&-&-&-\\ 1&0&1&0&0&1 \end{matrix}$$
这样下一个数就有办法构造了。
$$\begin{matrix} 0&0&1&1&1&0\\ 0&1&0&1&0&1\\ 1&0&1&0&0&1\\ -&-&-&-&-&-\\ 1&1&0&0&1&0 \end{matrix}$$
如果构造不出来，比如给定的数没有可用的1了，或没有空间添加更多的1了，那就无解，输出-1。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long MAXN=205,MAXB=61,MAXBIT=(1LL<<60LL);
int n,m;
long long S[MAXN];
int cnt[MAXB];
int main()
{scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%I64d",S+i);for(long long bit=1LL,j=0;bit<MAXBIT;bit<<=1LL,j++)if(S[i]&bit)cnt[j]++;}scanf("%d",&n);bool flag=true;for(int i=1;i<MAXB&&flag;i++)if(cnt[i]>2)flag=false;for(int i=1;i<=m&&flag;i++)for(int j=1;j<=m&&flag;j++)if((S[i]&S[j])==0LL)flag=false;if(flag){long long s;int cnt1;for(int i=m+1;i<=n;i++){s=0LL;for(int j=1;j<i;j++){for(long long bit=1LL,k=0;bit<MAXBIT;bit<<=1LL,k++)if((S[j]&bit)&&cnt[k]==1){s|=bit;cnt[k]++;break;}if((s&(S[j]))==0){flag=false;break;}}if(!flag)break;cnt1=n-i;for(long long bit=1LL,k=0;bit<MAXBIT&&cnt1;bit<<=1LL,k++)if(cnt[k]==0){s|=bit;cnt[k]++;cnt1--;}if(cnt1){flag=false;break;}S[i]=s;}if(flag){sort(S+1,S+n+1);for(int i=1;i<n;i++)printf("%I64d ",S[i]);printf("%I64d\n",S[n]);}}if(!flag)printf("-1\n");fclose(stdin);fclose(stdout);return 0;
}