题目描述

链接：https://ac.nowcoder.com/acm/problem/16762 来源：牛客网

托米完成了1317的上一个任务，十分高兴，可是考验还没有结束 说话间1317给了托米 n 个自然数 a1... an, 托米可以选出一些带回家，但是他选出的数需要满足一些条件 设托米选出来了k 个数 b1,b2... bk, 设这个数列 b 的给值为 b 中所有数按位与的结果，如果你能找到一个整除 b 的最大的 2v,(v≥ 0)， 则设定 v 为这个数列的给价，如果不存在这样的 v，则给价值为 -1, 1317 希望托米在最大化给价的情况下，最大化 k

解题思路

反过来思考下，如果我们最终挑选出k个满足题意的数字，且被2^v整除，那么我们可以知道，b[1]&b[2]&....b[k]==1<<v; 也就是说在二进制表示下，b数组中的所有数字都能整除1<<v，且其他位都为0.

• 从题目角度出发，给价要最大化，所以我们从最高位出发开始枚举可能的v
• 再枚举能否通过按位与运算使结果变成1<<v.
• 因为要给价最大化，所以我们在找到第一种可以满足上述条件的情况，就可以停止程序。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,a[100010],ans[100010];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=31;i>=0;i--)
	{
		int sum=(1<<i)-1;//找到一种情况使二进制下第1位~第v-1位能够通过按位与操作变为0
		int res=0;       
		for(int j=1;j<=n;j++)//题目中要求k值尽可能大，所以sum=0时依然要继续寻找
        {
			if((a[j]>>i)&1)//该数能整除1<<v,就进行按位与操作并记录下来
            {
                sum=sum&a[j];
                ans[++res]=a[j];
            }
        }
		if(sum==0)
		{
			printf("%d\n",res);
			for(int j=1;j<res;j++)//注意末尾不要加空格
            {
                printf("%d ",ans[j]);
            }
            printf("%d",ans[res]);
			break;
		}
	}
	return 0;
}