「ACM 算法实践」[解题报告]沙滩拾贝

分析

因为是与运算，只有当这 \(m\) 个数的第 \(k\) 位上都是 \(1\) 的时候才能使得最后的数的第 \(k\) 位为 \(1\) 。

为了让最后的开心程度最大，我们优先将高位取 \(1\) ，也就是从高位开始枚举，选出数量大于 \(m\) 同时在第 \(k\) 位上为 \(1\) 的所有数，然后再以同样的方法从这些数中选取第 \(k - 1\) 位为 \(1\) 的数，依次选取下去直到可选取的数的数量等于 \(m\) 。

代码

#include <bits/stdc++.h>
using namespace std;

int gi() {
	char c = getchar(); int x = 0, f = 1;
	for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
	for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return x * f;
}

const int N = 1e5 + 5;

int n, m, ans;
int a[N], b[N], cnt[35];
bool vis[N][32];

vector <int> vec[35];

void choose(int k, int num) {
	ans += (1 << k);
	if (num == m) return;
	for (int i = k - 1; i >= 0; --i) {
		vec[i].clear();
		cnt[i] = 0;
		for (int j = 0; j < cnt[k]; ++j)
			if ((vec[k][j] >> i) & 1) {
				vec[i].push_back(vec[k][j]);
				cnt[i]++;
			}
	}
	for (int i = k - 1; i >= 0; --i)
		if (cnt[i] >= m) {
			choose(i, cnt[i]);
			break;
		}
}


int main() {
	n = gi(), m = gi();
	for (int i = 1; i <= n; ++i) a[i] = gi();
	for (int i = 30; i >= 0; --i)
		for (int j = 1; j <= n; ++j)
			if ((a[j] >> i) & 1) {
				vec[i].push_back(a[j]);
				cnt[i]++;
			}
	for (int i = 30; i >= 0; --i)
		if (cnt[i] >= m) {
			choose(i, cnt[i]);
			break;
		}
	printf("%d", ans);
	return 0;
}