一、题目重现

椰程信奥 - T3 按位与

题目描述

小 R 有 n 个非负整数 a_1, a_2, …, a_n。小 X 给了他一个正整数 m，要求从这 n 个数中选出恰好 m 个，使选出的 m 个数的二进制按位与的值最大。求这个最大值。

输入格式

第一行两个正整数 n, m。第二行 n 个非负整数 a_1 ~ a_n。

输出格式

一行一个非负整数，表示能得到的按位与的最大值。

输入输出样例

样例 1

4 2
3 15 12 12

输出：

12

解释：选 15 和 12 得到 15 and 12 = 12，选两个 12 也是 12；其他挑法（3 和 15 得 3、3 和 12 得 0）都更小。

样例 2

5 3
31 3 1 15 7

输出：

7

解释：选 31、15、7，按位与为 7，可以证明这是最大值。

数据范围与约定

• 1 ≤ m ≤ n ≤ 2×10^5，0 ≤ a_i < 2^30；
• 部分测试点 m = 1、m = n、m = n−1，或所有数都很小；
• 原题时限 1.0 秒，内存 1024 MiB。

二、先补一小课：数字是一排小灯

计算机里的数写成二进制：每一位就是一盏灯，亮 = 1，灭 = 0。从右往左，每盏灯的值翻倍：

灯的位置： 第3位  第2位  第1位  第0位
值    ：    8     4     2     1

比如 1100 = 8+4 = 12，0011 = 2+1 = 3，1111 = 15。

两个常见坑：

• C++ 里 2^30 不是「2 的 30 次方」，^ 是异或；写「第 b 盏灯」要用 1 << b。
• 最左边那盏灯最值钱：1000(8) 比 0111(7) 大，哪怕右边三盏全亮也追不上。这是本题的关键。

三、按位与 = 全员举手才通过

把选出来的 m 个数竖着排好，一列一盏灯：

   15  →  1 1 1 1
   12  →  1 1 0 0
  ─────────────────
  与   →  1 1 0 0  = 12

规则：某一列要所有选中的数都是 1，结果这一列才是 1；只要有一个数是 0，这一列就灭。像班级投票，一盏灯要亮必须全票赞成。

四、妙招：从最值钱的灯开始，能亮就亮

笨办法是把 m 个数的所有组合都试一遍，n 到 20 万时组合数多到数不清，不可行。

因为高位最值钱，就一盏一盏从高位往低位决定：

试着问：「答案的这一盏灯能不能也亮着？」把「已确定要亮的灯 + 这一盏」写成一张清单 cand，再数一数有多少个数满足清单上所有亮灯。够 m 个就收下这盏灯，不够就让它灭着，继续看下一盏。

代码里就是 (x & cand) == cand：x & cand 只留下两边都亮的灯，结果正好等于清单，说明清单要求的灯 x 一盏不缺。

⚠️ 千万别写成 (x & cand) != 0：那只要求「至少有一盏灯一样」，太松了，会把不合格的数放进来。

五、逐位手算样例 1

n = 4, m = 2，四个数写成 4 位（更高的灯全是 0）：3=0011，15=1111，12=1100，12=1100。从 ans = 0 开始：

输出 12。想让答案变成 14，就得挑两个数都亮着第 3、2、1 位，可只有 15 一家做到，凑不够 2 票。

样例 2 同理：31=11111、15=01111、7=00111、3=00011、1=00001，m=3。16 和 8 两盏只有 31 够格（1 票，否）；4 这盏有 31、15、7 三票（是，ans=4）；2 这盏同样三票（是，ans=6）；1 这盏同样三票（是，ans=7）。正好对应题面说的「选 31、15、7」。

六、为什么「能亮就亮」不会吃亏

1. 决定第 b 盏灯时，更值钱的灯已经定死，不能改。这一盏亮着比灭着大 2^b；就算后面所有小灯全亮，最多只补回 2^b − 1，追不上。所以能亮必须亮。
2. 判定是准确的：清单上的灯能被 m 个数一起点亮，等价于真的存在 m 个数、它们的与至少亮着这些灯。数一数就够了。
3. 清单只会越加越长：多加一盏灯，够格的数只会变少或不变，绝不会变多。所以「现在能亮就亮」不会害得后面错过更好的答案。

还有个容易纠结的点：题目要「恰好 m 个」，我们数的是「≥ m 个」。这没问题——从够格的数里随便挑 m 个，它们每个都满足清单，与起来清单上的灯一定全亮。

七、参考代码（AC）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    // 答案的每一位可独立判定：若至少 m 个数含候选的所有位，该位就能保留。
    int ans = 0;
    for (int b = 29; b >= 0; --b) {
        int cand = ans | (1 << b);
        int cnt = 0;
        for (int x : a) {
            if ((x & cand) == cand) ++cnt;
            if (cnt >= m) break;
        }
        if (cnt >= m) ans = cand;
    }
    cout << ans << '\n';
    return 0;
}

八、代码逐段解析

• for (int b = 29; b >= 0; --b)：题目保证 a_i < 2^30，所以第 30 盏（值 2^30）永远不可能亮，29 就是最高的那盏。必须从高位往低位。
• int cand = ans | (1 << b);：1 << b 是只点亮第 b 盏灯的数，| 把新灯合进已确定的清单。每轮都要带上之前收下的灯。
• if ((x & cand) == cand) ++cnt;：用按位与检查 x 是否「一盏不缺」；括号别省，避免优先级出错。
• if (cnt >= m) break;：数到 m 票就够，剩下不用看，是纯提速。
• if (cnt >= m) ans = cand;：收下这盏灯，后续轮次在它的基础上继续试。

九、复杂度分析

外层固定 30 轮，每轮最多扫 n 个数：时间 O(30n)，n = 2×10^5 时约 600 万次判断，1 秒轻松跑完；内存 O(n)。注意 30 是常数，这其实是线性算法，不是平方级。

十、易错点清单

1. 必须从高位往低位贪心，从低位开始是错的。
2. 判定写 (x & cand) == cand，不是 != 0。
3. ^ 不是乘方，「第 b 盏灯」要用 1 << b。
4. 别漏 ans | (1 << b)：每轮都要带上已收下的灯，只试单独一盏会前功尽弃。
5. 「恰好 m」用 cnt >= m 判定，不要写成 == m。
6. ans 与 a_i 用 int 就够（都小于 2^30）；别顺手写 1 << 31（会溢出）。
7. 两种极端也成立：m = 1 时答案就是最大数，m = n 时答案就是全部数的与。
8. 文件输入输出：原题要求 and.in / and.out，本文代码改用标准输入输出；OJ 提交时请按题目要求加回 freopen。

十一、考点总结

一句话记住：先抢最值钱的那盏灯，凑够 m 票就留下，凑不够就放弃。

本文题面整理自 CCF CSP-J 2026 第二轮（入门组）试题，题目版权归中国计算机学会所有。题解与代码由椰程信奥整理撰写，参考答案仅供参考，最终以 CCF 官方公布为准。