下面是 [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++ 代码
三、要点说明
高位优先:按位与的结果高位更重要,所以从第 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