题解
2026-11-08 18:24:11
发布于:新疆
6阅读
0回复
0点赞
下面是 [CSP-J 2026] 按位与(and) 的 C++ 代码。
一、思路
按位贪心,从最高位(第 29 位)向低位枚举:
维护已确定的答案前缀 ans;
对每一位 bit,试探把它加进答案,得到候选值 tmp = ans | (1 << bit);
统计数组中有多少个数 x 满足 (x & tmp) == tmp,即这些数在已确定的位上全是 1;
若数量 ≥ m,说明这一位可以保留为 1,令 ans = tmp;否则该位只能为 0,跳过。
由于按位与要求选中的 m 个数在答案的每个 1 位上都必须为 1,而高位优先,贪心逐位确定即可得到最大值。
复杂度:每一位扫一遍数组,共 30 位 → O(30n),通过 n ≤ 2×10⁵ 极限数据无压力。
二、C++ 代码
#include <bits/stdc++.h>
using namespace std;
/*
* [CSP-J 2026] 按位与 (and)
*
* 题意:从 n 个非负整数中恰好选 m 个,使按位与值最大。
* 1 <= m <= n <= 2e5,0 <= a_i < 2^30。
*
* 做法:按位贪心(高位优先)
* ans 为已确定答案的前缀。从第 29 位到第 0 位:
* 试探 tmp = ans | (1 << bit),统计满足 (a[i] & tmp) == tmp 的个数,
* 若 >= m,则这一位可保留为 1(ans = tmp),否则跳过。
*
* 复杂度:O(30 * n)。
*/
const int MAXN = 200005;
int n, m;
int a[MAXN];
int main() {
freopen("and.in", "r", stdin);
freopen("and.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
int ans = 0;
// a_i < 2^30,故从第 29 位枚举到第 0 位
for (int bit = 29; bit >= 0; --bit) {
int tmp = ans | (1 << bit); // 试探把这一位置 1
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if ((a[i] & tmp) == tmp) ++cnt; // 该数包含 tmp 的全部 1 位
}
if (cnt >= m) ans = tmp; // 至少 m 个数满足,则保留这一位
}
cout << ans << '\n';
return 0;
}
三、要点说明
高位优先:按位与的结果高位更重要,所以从第 29 位往低位贪心,先保证高位尽量为 1。
判据 (a[i] & tmp) == tmp:表示 a_i 在 tmp 所有为 1 的位上也都是 1,即这些数在一起按位与能保留住 tmp。
不需要排序或额外数据结构:每个数只看一位条件,逐位扫描即可,常数很小。
数据范围:a_i < 2³⁰,故最高位取 29 即可;答案本身也落在 int 范围内。
样例验证
样例 #1:4 2、3 15 12 12 → 输出 12
样例 #2:5 3、31 3 1 15 7 → 输出 7
这里空空如也







有帮助,赞一个