[CSP-J 2026] 按位与 / and（民间数据）

GitHub跳转原题关系图返回列表

按测试点分档推进：枚举组合 → 固定 m 的四个特判 → 值域开桶的超集计数 → 从高到低逐位贪心，全范围 O(30n)。

OJ: luogu

题目 ID: P17829

难度:普及

标签:位运算贪心枚举sosdp

创建: 2026-10-31 18:55

更新: 2026-10-31 20:14

RBook 文章:
贪心算法

形式化题目

给定 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$ 和正整数 $m \leqslant n$ 。选取下标集合 $S \subseteq \{1, 2, \ldots, n\}$ ，要求 $|S| = m$ ，最大化

\bigwedge_{i \in S} a_i,

也就是所选 $m$ 个数的二进制按位与。同一个数值出现在不同下标时按不同下标分别计数，可以同时选中。约束为 $1 \leqslant m \leqslant n \leqslant 2 \times 10^5$ 和 $0 \leqslant a_i < 2^{30}$ 。下面把这样的 $m$ 元下标集合简称为“选法”。

解法路线

题面的测试点不是按难度均匀铺开的，而是卡在三种不同的条件上： $n$ 的大小、 $m$ 的固定取值、值域与数值结构。这几档里只有一条主线，另有一档是独立分支。

层次	适用约束	对应测试点	做法	复杂度	相对前层的推进
层 1：暴力	$n \leqslant 20$	$1 \sim 5$	枚举全部 $m$ 元下标组合，逐个求按位与	$O\left(\binom{n}{m}\cdot m\right)$	基线
层 2：固定 $m$	$m = 1, 2, n, n-1$	$6 \sim 12$	按 $m$ 的形状直接构造最优选法	$O(n)$ 、 $O(n^2)$ 、 $O(30n)$	不再枚举 $m$ 元组，用“ $m$ 等于多少”换掉组合枚举
层 3：值域开桶	$\max a_i < 2^{20}$	$13 \sim 19$	桶计数加超集和，取满足 $\mathrm{super\_cnt}[X] \geqslant m$ 的最大 $X$	$O(20 \cdot 2^{20} + n)$	换视角：不选数，只判断“掩码 $X$ 能不能被 $m$ 个数同时包含”；代价是值域必须能开桶
层 4：逐位贪心	全范围	$20$	从第 29 位到第 0 位维护必修掩码，候选数够 $m$ 个就保留这一位	$O(30n)$	取消值域限制： $2^{20}$ 个桶换成 $30$ 次 $n$ 元扫描
分支：性质 A	每个 $a_i = 2^k - 1$	$13$	这类数的按位与等于最小值，取最大的 $m$ 个	$O(n \log n)$	不在主线上，靠数值结构把问题化成排序

层 2 的四个 $m$ 之间互不包含。 $m = 2$ 的 $O(n^2)$ 和 $m = n - 1$ 的 $O(30n)$ 彼此没有依赖，它们只是“先知道会选几个，再直接造选法”这个想法的四个实例。
层 3 是主线上唯一一次换视角：从“挑哪 $m$ 个数”变成“某个掩码能不能被至少 $m$ 个数同时包含”。这个判据与 $m$ 的具体取值无关，代价是必须把整个值域开成桶。
性质 A 是分支，不是通向正解的一步。它对数值结构的依赖太强，换一组数据立刻失效。保留它的理由有两条：测试点 13 正是给这个观察留的档位；它也顺带说明按位与在高位上只看公共前缀。

性质 B（ $n = 2^k$ ， $a_i = i - 1$ ）没有单独立层。这组数据恰好铺满 $0$ 到 $n - 1$ ，层 3 和层 4 都能直接通过，没有自己的做法值得展开。顺带还能看出它的答案有闭式解：前 $t$ 位全为 1 的数在 $0$ 到 $n - 1$ 里恰好有 $2^{k-t}$ 个，只要 $2^{k-t} \geqslant m$ ，这 $t$ 位就都能保留；所以答案就是满足 $2^{k-t} \geqslant m$ 的最大 $t$ 所对应的 $(2^t - 1) \cdot 2^{k-t}$ 。

暴力解法

适用范围

$n \leqslant 20$ ，对应测试点 $1 \sim 5$ 。

思路

按定义枚举：把“选 $m$ 个下标”的所有组合都列出来，逐个算出按位与，取最大值。

brute.cpp 用递归决定每个下标选或不选，选满 $m$ 个就结算一次。加了一条剪枝：剩下的下标不够补齐 $m$ 个时直接返回。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-31 18:55
 * update_at: 2026-10-31 19:01
 */
// brute.cpp：枚举所有 m 元下标组合，取按位与的最大值。只适用于 n 很小的情况。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 25;
int n, m;
int a[maxn];
int best;

// 从下标 dep 开始决定选不选，已经选了 picked 个，当前与值为 cur
void dfs(int dep, int picked, int cur) {
    if (picked == m) {
        best = max(best, cur);
        return;
    }
    if (dep > n) return;
    if (n - dep + 1 < m - picked) return;   // 剩下的数不够选了
    // 选第 dep 个
    dfs(dep + 1, picked + 1, picked == 0 ? a[dep] : (cur & a[dep]));
    // 不选第 dep 个
    dfs(dep + 1, picked, cur);
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    best = 0;
    dfs(1, 0, 0);
    cout << best << '\n';
    return 0;
}

复杂度与瓶颈

组合数是 $\binom{n}{m}$ ，每组还要做 $m$ 次与运算，总时间 $O\left(\binom{n}{m} \cdot m\right)$ ，空间 $O(n)$ 。 $n = 20$ 的最坏情况是 $\binom{20}{10} \approx 1.8 \times 10^5$ 个组合，够用； $n = 2 \times 10^5$ 时完全没有希望。

真正的瓶颈不在常数，而在“把 $m$ 个位置当成一个整体来挑”。按位与的每一位只关心有没有至少 $m$ 个数在这一位上是 1，并不关心具体是哪 $m$ 个。这个观察是后面所有层的起点。

子任务解法：固定 m 的四个取值

适用范围

$m$ 取四个固定值： $m = 1$ （测试点 6）、 $m = n$ （测试点 7）、 $m = 2$ （测试点 $8 \sim 10$ ， $n \leqslant 2000$ ）、 $m = n - 1$ （测试点 11、12， $n \leqslant 2 \times 10^5$ ）。

思路

前三个都很直接：

$m = 1$ ：只选一个数，答案就是最大值，扫一遍。
$m = n$ ：所有数都要选，答案是全体按位与，扫一遍。
$m = 2$ ： $n \leqslant 2000$ 时数对只有约 $2 \times 10^6$ 个，直接枚举。

$m = n - 1$ 值得单独想。选 $n - 1$ 个数等价于从全部 $n$ 个数里丢掉一个，而要丢哪个数可以逐位判断。

先算全体按位与 base。第 $b$ 位在 base 里是 1，说明没有数在这一位为 0，丢谁都不影响；base 里为 0 的位，说明至少有一个数在这一位为 0，而丢掉一个数只能补回“恰好只有一个数为 0”的那些位。

于是统计每一位上为 0 的数的个数：

0 个：这一位已经在 base 里，不用管；
1 个：把那个在这位上为 0 的数丢掉，这一位就能补回 1；
2 个及以上：丢掉一个数后仍有数为 0，这一位救不回来。

把“只能靠丢掉第 $i$ 个数补回的位”记成 extra[i]，丢掉第 $i$ 个数得到的答案就是 base | extra[i]，枚举 $i$ 取最大即可。

以 $a = (7, 5, 3)$ 、 $m = 2$ 为例（ $n = 3$ ，恰好丢一个）：base = 7 & 5 & 3 = 1；第 1 位只有 5 是 0，丢 5 得到 $1 \mathbin{\mathrm{or}} 2 = 3$ ；第 2 位只有 3 是 0，丢 3 得到 $1 \mathbin{\mathrm{or}} 4 = 5$ 。取最大是 5，与真实最优（选 7 和 5）一致。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-31 19:50
 * update_at: 2026-10-31 19:50
 */
// main2.cpp：把 m 钉成四个具体取值来拿部分分，覆盖 m = 1、m = 2、m = n、m = n - 1。
// 其余 m 这一份代码不给答案，直接输出 0。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;
int n, m;
int a[maxn];      // a_i < 2^30，int 足够
int extra[maxn];  // extra[i]：只丢掉第 i 个数时能额外补回来的位

// m = 1：任选一个数，答案就是最大值
int solve_m1() {
    int best = 0;
    for (int i = 1; i <= n; ++i) best = max(best, a[i]);
    return best;
}

// m = n：全部数都要选，答案就是全体按位与
int solve_full() {
    int cur = a[1];
    for (int i = 2; i <= n; ++i) cur &= a[i];
    return cur;
}

// m = 2：直接枚举所有数对
int solve_m2() {
    int best = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j) best = max(best, a[i] & a[j]);
    return best;
}

// m = n - 1：恰好丢掉一个数。先算全体与 base，再逐位看这一位是不是只被一个数否决
int solve_drop_one() {
    int base = a[1];
    for (int i = 2; i <= n; ++i) base &= a[i];
    for (int i = 1; i <= n; ++i) extra[i] = 0;

    // 第 b 位上为 0 的数如果恰好只有第 who 个，那么丢掉 who 就能把这一位补回来
    for (int b = 0; b < 30; ++b) {
        int zero_cnt = 0, who = 0;
        for (int i = 1; i <= n; ++i)
            if (((a[i] >> b) & 1) == 0) {
                ++zero_cnt;
                who = i;
            }
        if (zero_cnt == 1) extra[who] |= 1 << b;
    }

    // 丢掉第 i 个数得到的答案就是 base | extra[i]，取最大
    int best = 0;
    for (int i = 1; i <= n; ++i) best = max(best, base | extra[i]);
    return best;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    int ans = 0;
    if (m == 1) ans = solve_m1();
    else if (m == n) ans = solve_full();
    else if (m == 2) ans = solve_m2();
    else if (m == n - 1) ans = solve_drop_one();
    // 其余 m 在二分点上没有对应的特判做法，这一支不做处理

    cout << ans << '\n';
    return 0;
}

这份代码只处理这四个 $m$ ，其他 $m$ 会输出 0。

复杂度与瓶颈

$m = 1$ 和 $m = n$ 是 $O(n)$ ， $m = 2$ 是 $O(n^2)$ ， $m = n - 1$ 是 $O(30n)$ ，空间 $O(n)$ 。 $n = 2 \times 10^5$ 的 $m = n - 1$ 数据本地实测约 31 ms。

这一层完全靠 $m$ 的形状。 $m = 3$ 或者 $m = n - 2$ 时四个分支一个都用不上； $m = 2$ 在 $n = 2 \times 10^5$ 时是 $2 \times 10^{10}$ 个数对，也跑不完。要往前走，必须放弃“按 $m$ 分类”这个前提，找一个对任意 $m$ 都成立的判据。

特例分支：全部是一串 1（性质 A）

适用范围

每个 $a_i$ 都能写成 $2^{k_i} - 1$ ，二进制下就是末尾一串连续的 1。对应测试点 13。

思路

设 $p \leqslant q$ ，比较 $2^p - 1$ 与 $2^q - 1$ ：前者的 1 位全部包含在后者的 1 位里，所以两者的按位与等于较小的那个。推广到 $m$ 个数，按位与等于其中最小的数。

于是题目变成“从 $n$ 个数里选 $m$ 个，让最小值尽量大”。答案就是第 $m$ 大的数，升序排序后取 $a_{n-m+1}$ 即可。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-31 19:50
 * update_at: 2026-10-31 19:50
 */
// main3.cpp：只对特殊性质 A 成立（所有 a_i 都是 2^k - 1 的形状）。
// 这种数末尾是一串连续的 1，两个这样的数按位与等于较小的那个，
// 所以选出 m 个数后的答案就是这 m 个数里的最小值，取最大的 m 个数即可。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;
int n, m;
int a[maxn];  // a_i < 2^30，int 足够

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // 升序排序后，第 m 大的数就在下标 n - m + 1 上
    sort(a + 1, a + n + 1);
    cout << a[n - m + 1] << '\n';
    return 0;
}

这份代码只在性质 A 的数据上正确，一般数据会算错。

复杂度与瓶颈

时间 $O(n \log n)$ （换成 nth_element 可以做到 $O(n)$ ），空间 $O(n)$ 。

局限很明显：结论依赖“每个数都是 $2^k - 1$ ”，题面只给了这一档。它不是通向正解的中间步骤，后面的层 3 和层 4 都能直接通过测试点 13。

子任务解法：值域能开桶就换一个刻画

适用范围

$\max a_i < 2^{20}$ ，对应测试点 $13 \sim 19$ 。时间上允许 $20 \cdot 2^{20} \approx 2.1 \times 10^7$ 次操作。

思路

层 2 留下的是“对任意 $m$ 都得有一个判据”这个问题。做法是把“挑 $m$ 个数”改写成对一个掩码的判定， $m$ 只出现在一个计数的门槛上，不再决定算法的形状。

对一个掩码 $X$ ，记 $\mathrm{super\_cnt}[X]$ 为满足 $(a_i \mathbin{\&} X) = X$ 的下标个数，也就是“包含 $X$ 全部位”的数的个数。下面证明“能不能选出按位与包含 $X$ 的 $m$ 个数”和“ $\mathrm{super\_cnt}[X] \geqslant m$ ”是一回事。

充分性（ $\mathrm{super\_cnt}[X] \geqslant m$ $\Rightarrow$ 能选出按位与包含 $X$ 的 $m$ 个数）

把满足 $(a_i \mathbin{\&} X) = X$ 的 $m$ 个下标选出来。
在 $X$ 为 1 的每一位上，这 $m$ 个数都是 1。
所以它们的按位与在这一位也是 1，即按位与包含 $X$ 的全部位。

必要性（能选出按位与包含 $X$ 的 $m$ 个数 $\Rightarrow$ $\mathrm{super\_cnt}[X] \geqslant m$ ）

设某个选法的按位与包含 $X$ 的全部位。
那么被选中的每个数都含 $X$ 的每一位，即每个被选中的数都是 $X$ 的超集。
这样的下标至少有 $m$ 个，所以 $\mathrm{super\_cnt}[X] \geqslant m$ 。

有了这个等价，答案就是满足 $\mathrm{super\_cnt}[X] \geqslant m$ 的最大 $X$ ：

最优选法的按位与 $A$ 本身就满足 $\mathrm{super\_cnt}[A] \geqslant m$ ，所以 $A$ 在可行集合里；
反过来，任何可行的 $X$ 都对应某个按位与 $Y \supseteq X$ 的选法，而 $Y \geqslant X$ ，所以 $X$ 不会超过答案；
两边的界合起来，可行集合的最大值就是答案。

剩下的事只有一件：把所有 $X$ 的 $\mathrm{super\_cnt}$ 算出来。值域小，开桶即可。

桶 $\mathrm{cnt}[v]$ 记值 $v$ 出现的次数。
按位做 20 轮：对每一位 $b$ ，把所有第 $b$ 位为 1 的桶加到“去掉这一位”的桶上，即 $\mathrm{cnt}[x] \leftarrow \mathrm{cnt}[x] + \mathrm{cnt}[x \mid 2^b]$ ，这里 $x$ 的第 $b$ 位为 0。
每一轮相当于允许这一位自由翻转，20 轮之后 $\mathrm{cnt}[X]$ 把 $X$ 的所有超掩码都统计过一遍，正是 $\mathrm{super\_cnt}[X]$ 。

拿样例 #1 验算（ $a = (3, 15, 12, 12)$ ， $m = 2$ ），只看真正有数的几个掩码：

掩码 $X$	包含 $X$ 全部位的数	$\mathrm{super\_cnt}[X]$	能选出 $m = 2$ 个
14	15	1	否
13	15	1	否
12	15、12、12	3	是

12 可行而 14、13 不可行，所以答案是 12，与逐位贪心的结论一致。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-31 19:50
 * update_at: 2026-10-31 19:58
 */
// main4.cpp：值域可枚举时的解法，要求 max a_i < 2^20。
// 换成另一种看问题的角度：一个掩码 X 能被选出来，当且仅当至少有 m 个数包含 X 的全部位。
// 于是先把每个值的出现次数放进桶，再用超集和（SOS DP）求出
// super_cnt[X] = 包含 X 全部位的数的个数，最后取 super_cnt[X] >= m 的最大 X。
#include <bits/stdc++.h>
using namespace std;

const int BITS = 20;           // 本层要求 max a_i < 2^20
const int SIZE = 1 << BITS;    // 桶的大小 2^20，int 数组约占 4MB
int n, m;
int super_cnt[SIZE];           // super_cnt[X]：包含掩码 X 全部位的数的个数，初值是该值的出现次数

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        ++super_cnt[x];
    }

    // 超集和：按位逐个把「多含一位」的计数并进来
    for (int b = 0; b < BITS; ++b)
        for (int x = 0; x < SIZE; ++x)
            if (((x >> b) & 1) == 0) super_cnt[x] += super_cnt[x ^ (1 << b)];

    // 从大到小找第一个能被选出 m 个数的掩码
    for (int x = SIZE - 1; x >= 0; --x)
        if (super_cnt[x] >= m) {
            cout << x << '\n';
            return 0;
        }

    cout << 0 << '\n';   // 只有 m > n 才会走到这里，题面保证不会出现
    return 0;
}

复杂度与瓶颈

时间由三部分组成：装桶 $O(n)$ ，超集和 $20 \cdot 2^{20} \approx 2.1 \times 10^7$ 次加法，倒序扫描 $2^{20}$ 。空间是 $2^{20}$ 个 int，约 4 MB。 $n = 2 \times 10^5$ 、 $a_i < 2^{20}$ 时本地实测 42 至 44 ms、内存 4.4 至 4.9 MB，都在限制内。

瓶颈在桶的大小。 $\max a_i < 2^{30}$ 时桶要 $2^{30}$ 个 int，也就是 4 GB，测试点 20 过不去。想过它，必须把“枚举整个值域”换成“只看这 $n$ 个数自己的 30 个位”。

正解

关键观察

第 $b$ 位的权值 $2^b$ 比所有更低位权值之和还大：

2^b > 2^b - 1 = \sum_{j=0}^{b-1} 2^j .

所以只要存在 $m$ 个数能让第 $b$ 位为 1，就绝不该为了低位的任何组合放弃它。位的判断可以从第 29 位往第 0 位依次做，做完的位不必回头。

思路

把层 3 的“可行掩码”换成按位决策，并且只统计这 $n$ 个数本身，不开桶。

用 ans 记已经确定必须为 1 的位。判断第 $b$ 位时先假设它也取 1，得到试探掩码 want = ans | (1 << b)；再数一数有多少个数同时含 ans 的全部位和第 $b$ 位，也就是满足 (a[i] & want) == want 的个数。个数不少于 $m$ 就把 ans 换成 want，否则这一位放弃。

正确性靠按位归纳：

归纳假设：处理完高于 $b$ 的位后，ans 的每一位都出现在最优答案里。
候选数不少于 $m$ 个时，这 $m$ 个数同时含 ans 和第 $b$ 位，能凑出包含 want 的按位与。而任何按位与含 ans、第 $b$ 位却是 0 的选法，在高于 $b$ 的位上只能与 ans 完全一致：更高的位如果还能再多含一位，那一步就已经把它保留进 ans 了。高位相同而第 $b$ 位为 0，它的值就严格小于保留这一位得到的结果。所以这一位必须保留。
候选数不足 $m$ 个时，不存在 $m$ 个数同时含 ans 和第 $b$ 位，最优答案的第 $b$ 位只能是 0，放弃它不损失任何东西。
每一步都不破坏最优性，循环结束时 ans 就是答案。

以样例 #1 为例， $a = (3, 15, 12, 12)$ ， $m = 2$ ，只看真正起作用的低四位：

位 $b$	试探掩码	同时含这些位的数	个数	决策
$29 \sim 4$	逐位试探	无（所有数都在低四位以内）	0	放弃，`ans` 保持 0
3	8	15、12、12	3	$\geqslant 2$ ，保留，`ans = 8`
2	12	15、12、12	3	$\geqslant 2$ ，保留，`ans = 12`
1	14	15	1	$< 2$ ，放弃，`ans` 仍为 12
0	13	15	1	$< 2$ ，放弃，答案 12

第 3、2 位定下来之后，第 1、0 位无论怎么挑都凑不出两个同时含这些位的数，所以答案是 $8 + 4 = 12$ 。第 1 位那一步也说明了为什么不能先试 14：只有 15 一个数含 14，凑不满 $m = 2$ 个，强行保留会让后面的判断全部失去候选。

还有一个看起来很像、实际错误的直觉：直接选数值最大的 $m$ 个数。取 $a = (8, 7, 7)$ 、 $m = 2$ ，最大的两个是 8 和 7，与出来是 $0$ ；而选两个 7 得到 7。按数值排序和按二进制位决策是两件事。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-31 18:55
 * update_at: 2026-10-31 19:01
 */
// main.cpp：从高位到低位逐位贪心。
// 已经确定的位必须被选中的每个数都含有，再看当前位能不能也凑够 m 个数。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;
int n, m;
int a[maxn];

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    int ans = 0;   // 已确定必须为 1 的位构成的掩码
    for (int b = 29; b >= 0; --b) {
        int want = ans | (1 << b);   // 假设第 b 位也取 1
        int cnt = 0;                 // 有多少个数同时含有 want 的全部位
        for (int i = 1; i <= n; ++i) {
            if ((a[i] & want) == want) ++cnt;
        }
        if (cnt >= m) ans = want;    // 够 m 个，第 b 位可以取 1
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间： $30$ 个位，每一位扫一遍 $n$ 个数， $O(30n)$ 。 $n = 2 \times 10^5$ 时约 $6 \times 10^6$ 次与运算，本地实测 36 至 49 ms。
空间：存下输入的 $n$ 个数， $O(n)$ ，实测 1.3 至 1.6 MB。
位掩码用 int 就够：题面限定 $a_i < 2^{30}$ ，最高只探到第 29 位，1 << 29 在 32 位 int 内不会溢出。如果值域扩到 $2^{31}$ 以上，这里要改成 1ll << b，否则会碰到有符号整数的溢出。

总结

这题的入手点是把“选 $m$ 个数”换成“定 30 个二进制位”。

按位与的每一位只关心“够不够 $m$ 个数”， $m$ 个数的具体身份只通过“必须是同一批数”这一条约束串起来。层 3 用超集计数把这条约束也解掉，代价是必须枚举值域；正解退回逐位决策，用候选过滤代替整个值域，代价是每位都要扫一遍全部数。两条路的复杂度都是“值域或位宽”乘上另一个量，值域小就走桶，值域大就走扫描。

分档的意义也在这里。固定 $m$ 、性质 A、小值域，都只是某一条约束被额外收紧后的简化版本，抓住收紧的那一条就能拿到对应分数，而正解是把这些约束一起松开的结果。

再往外推一步：目标是最大化一个按位组合出来的值、并且每一位的贡献按指数递减时，都可以从高位到低位贪心，判定一位时只保留满足已定高位的那批候选，看这一位还能不能凑够所需的个数。

知识点	对应文章	用在哪
位运算基础	《二进制与位运算》	第 $k$ 位怎么取、权值是 $2^k$ ；正解里 `(a[i] & want) == want` 就是在检查若干位
子集枚举	《子集枚举》	值域能开桶那一层，按掩码统计“包含它全部位的数有多少个”
贪心与正确性证明	《贪心算法》	从高位到低位“能保就保”，靠 $2^b$ 大于低位之和论证这一步不会破坏全局最优

P17829 [CSP-J 2026] 按位与 / and（民间数据）

题目描述

小 R 有 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ 。

小 X 给了小 R 一个正整数 $m$ ，并要求小 R 从这 $n$ 个非负整数中选出恰好 $m$ 个，使得选出的 $m$ 个数的二进制按位与的值最大。

你需要帮助小 R 求出，他能选出的 $m$ 个数的按位与的最大值。

输入格式

从文件 and.in 中读入数据。

输入的第一行包含两个正整数 $n,m$ 。

输入的第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ ，依次表示小 R 的 $n$ 个非负整数。

输出格式

输出到文件 and.out 中。

输出一行一个非负整数，表示小 R 能选出的 $m$ 个数的按位与的最大值。

输入输出样例 #1

输入 #1

text

1
24 2
3 15 12 12

输出 #1

text

输入输出样例 #2

输入 #2

text

1
25 3
31 3 1 15 7

输出 #2

text

说明/提示

样例 1 解释

小 R 有 $4$ 个非负整数： $3,15,12,12$ 。

若小 R 选择 $3,15$ ，则按位与的值为 $3\mathbin{\mathrm{and}}15=3$ ；
若小 R 选择 $3,12$ ，则按位与的值为 $3\mathbin{\mathrm{and}}12=0$ ；
若小 R 选择 $15,12$ ，则按位与的值为 $15\mathbin{\mathrm{and}}12=12$ ；
若小 R 选择 $12,12$ ，则按位与的值为 $12\mathbin{\mathrm{and}}12=12$ 。

因此，小 R 能选出的 $m$ 个数的按位与的最大值为 $12$ 。

样例 2 解释

若小 R 选择 $31,15,7$ ，则按位与的值为 $31\mathbin{\mathrm{and}}15\mathbin{\mathrm{and}}7=7$ 。可以证明，小 R 能选出的 $m$ 个数的按位与的最大值为 $7$ 。

样例 3

见题目目录下的 and/3.in 与 and/3.ans。

该样例满足测试点 $8\sim 10$ 的约束条件。

样例 4

见题目目录下的 and/4.in 与 and/4.ans。

该样例满足测试点 $14,15$ 的约束条件。

样例 5

见题目目录下的 and/5.in 与 and/5.ans。

该样例满足测试点 $18,19$ 的约束条件。

数据范围

对于所有测试数据，均有：

$1\le m\le n\le 2\times 10^5$ ；
对于所有 $i$ （ $1\le i\le n$ ），均有 $0\le a_i<2^{30}$ 。

::cute-table{tuack}

测试点编号	$n\le$	$m$	$\max_{i=1}^{n}a_i<$	特殊性质
$1\sim 5$	$20$	$\le n$	$2^{20}$	无
$6$	$2000$	$=1$	$2^{20}$	无
$7$	$2000$	$=n$	$2^{20}$	无
$8\sim 10$	$2000$	$=2$	$2^{20}$	无
$11,12$	$2\times 10^5$	$=n-1$	$2^{20}$	无
$13$	$2\times 10^5$	$\le n$	$2^{20}$	A
$14,15$	$2\times 10^5$	$\le n$	$2^{20}$	B
$16,17$	$2\times 10^5$	$\le n$	$4$	无
$18,19$	$2\times 10^5$	$\le n$	$2^{10}$	无
$20$	$2\times 10^5$	$\le n$	$2^{30}$	无

特殊性质 A：对于所有 $i$ （ $1\le i\le n$ ），均存在非负整数 $k_i$ 满足 $a_i=2^{k_i}-1$ 。

特殊性质 B：存在非负整数 $k$ 满足 $n=2^k$ ，且对所有 $i$ （ $1\le i\le n$ ），均有 $a_i=i-1$ 。

[CSP-J 2026] 按位与 / and（民间数据）

目录

形式化题目

解法路线

暴力解法

适用范围

思路

代码

复杂度与瓶颈

子任务解法：固定 m 的四个取值

适用范围

思路

代码

复杂度与瓶颈

特例分支：全部是一串 1（性质 A）

适用范围

思路

代码

复杂度与瓶颈

子任务解法：值域能开桶就换一个刻画

适用范围

思路

代码

复杂度与瓶颈

正解

关键观察

思路

代码

复杂度

总结

相关 rbook 文章