链接:https://www.nowcoder.com/acm/contest/156/C
来源:牛客网
第一行输入一个整数 n, 第二行输入 a1...an
第一行输出最大的整数 k, 第二行输出 k 个整数 b1... bk, 按原数列的相对顺序输出 (如果行末有额外空格可能会格式错误)
5 1 2 3 4 5
2 4 5
n≤ 105, a1... an < 2^31
题意:从n个数中挑出k个数,这k个数组成的序列的值为每个数按位与运算,序列值求出最大的能被2^v整除的数,然后在求出最大的数后要求k的个数也是尽量最大
思路:因为我们是优先求最大的,所以我们贪心取最大的,因为范围是31次方,所以我们暴力二进制位从高到底,
例如我们要取按位与之后8 我们取所有二进制位包含8的数相与,如果与后等于8了,那么直接退出,因为是从高到底,肯定算的是最大的值
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int a[N], n, b[N], m; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 30; i >= 0; i--) {//从高到低进行枚举 m = 0; int s = (1ll << 31) - 1; for(int j = 1; j <= n; j++)//遍历每个数 if(a[j] >> i & 1) s &= a[j], b[++m] = a[j];//如果找到包含当前二进制位1的就进行与运算,并且把数存下来 // printf("%d %d\n", i, s); if((s & -s) == (1 << i)) break;//判断最低位是否是二进制位1 } cout << m << endl; bool first = 1; for(int i = 1; i <= m; i++) { if(first) first = 0; else cout << " "; cout << b[i]; } cout << endl; }
原文:https://www.cnblogs.com/Lis-/p/9380451.html