绝世好题

形式化题目

给定长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$ , 其中 $a_i \leqslant 10^9$ .

求最长的下标递增子序列 $i_1 < i_2 < \dots < i_k$ , 使得对每个 $2 \leqslant j \leqslant k$ 都有

a_{i_j} \land a_{i_{j-1}} \neq 0

输出最大的 $k$ . 这里 $\land$ 是按位与.

样例

样例 $a = [1, 2, 3]$ , 二进制分别是 $01, 10, 11$ .

$1 \land 2 = 0$ , 接不上.
$1 \land 3 = 1 \neq 0$ , $1$ 与 $3$ 能接上.
$2 \land 3 = 2 \neq 0$ , $2$ 与 $3$ 也能接上.

所以能取到长度 $2$ (如 $1, 3$ 或 $2, 3$ ), 无法取到长度 $3$ (因为 $1$ 和 $2$ 之间接不上). 答案为 $2$ .

暴力解法

思路

按定义做子序列 DP. 令 $f_i$ 表示以第 $i$ 个数结尾的最长合法子序列长度, 转移枚举上一个被选的元素:

f_i = 1 + \max\big\{ f_j : j < i,\ a_j \land a_i \neq 0 \big\}

初值 $f_i = 1$ , 答案为 $\max_i f_i$ .

这个转移不漏方案: 任何合法子序列的最后两项一定是一对能接上的 $(j, i)$ , 而 $f_j$ 已经取到以 $j$ 结尾的最优长度.

代码

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-26 13:20
 * update_at: 2026-10-26 16:36
 */
// brute.cpp：小数据暴力解，直接枚举子序列的上一个元素，O(n^2)。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 5005;

ll n;
ll a[MAXN]; // 输入的数列
ll f[MAXN]; // f[i]：以第 i 个数结尾的最长合法子序列长度

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

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }

    ll ans = 1;
    // 枚举每一对 (j, i)，j < i 且 a[j] & a[i] != 0 时可以把 i 接在 j 后面。
    for (ll i = 1; i <= n; i++) {
        f[i] = 1;
        for (ll j = 1; j < i; j++) {
            if ((a[j] & a[i]) != 0 && f[j] + 1 > f[i]) {
                f[i] = f[j] + 1;
            }
        }
        if (f[i] > ans) {
            ans = f[i];
        }
    }

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

复杂度

时间 $O(n^2)$ : 每个 $i$ 都要扫过它前面的所有 $j$ . 空间 $O(n)$ 存输入和 $f$ .

瓶颈

瓶颈是内层扫描要为每个 $i$ 检查全部 $j < i$ . $n = 10^5$ 时约 $5 \times 10^9$ 次位与判断, 必然超时.

不过转移只用到历史元素的一个性质: 它和 $a_i$ 有公共的 1 位. $a_i \leqslant 10^9 < 2^{30}$ , 公共位只可能落在 $0 \sim 29$ 这 30 个位置里. 真正需要的区分度只有 30 种, 不需要记住"上一个数具体是谁".

正解

关键观察

把状态从"末项的具体数值"放宽成"末项含有哪一位".

令 $g_b$ 表示: 在已经处理过的前缀里, 以某个第 $b$ 位为 $1$ 的数结尾的最长合法子序列长度.

为什么会想到这样合并? 因为" $a_j$ 能接到 $a_i$ 前面"这个条件, 对同一个位 $b$ 来说是完全一样的: 只要 $a_j$ 与 $a_i$ 都含第 $b$ 位, 两者一定满足 $a_j \land a_i \neq 0$ . 所以在"含第 $b$ 位"这一整类末项中, 只有最长的那个可能产生更优答案, 其余的具体数值信息都用不到.

于是转移变成两步:

读出: $len = 1 + \max\{ g_b : b \text{ 是 } a_i \text{ 的 } 1 \text{ 位} \}$ . 没有可用位时( $a_i = 0$ )取 $1$ .
写回: 对 $a_i$ 的每个 $1$ 位 $b$ , 令 $g_b = \max(g_b, len)$ .

样例推演

表里用 $b = 0, 1$ 两列(样例只用到低两位). "读"是从自身 1 位对应的桶里取最大值,"写"是把新长度写回这些桶.

处理到	$a_i$ 的 1 位	读到的 $g_0, g_1$	$len$	写回后 $g_0, g_1$	答案
初始	—	$0, 0$	—	$0, 0$	0
$a_1 = 1$	$\{0\}$	$0, 0$	$1$	$1, 0$	1
$a_2 = 2$	$\{1\}$	$1, 0$	$1$	$1, 1$	1
$a_3 = 3$	$\{0, 1\}$	$1, 1$	$2$	$2, 2$	2

第三行最能说明问题: $a_3 = 3$ 同时含两位, 两个桶都是 $1$ , 取最大再加一得到 $2$ . 若按暴力写法要在 $j = 1, 2$ 两处分别比较, 这里是合成一次查表.

思路

对每个读入的数 $x$ , 先求 $len$ , 再写回, 两轮分开.

顺序不能交换. 若写成边读边写, 处理 $x$ 时可能读到自己刚写进去的 $g_b$ , 长度就多算了一次, 相当于让 $x$ 接在自己后面.

正确性由两条夹逼给出:

$len$ 不超过 $f_i$ : 设 $b$ 给出最大值 $g_b$ . 按归纳, 前缀里存在一个下标 $j < i$ 、含第 $b$ 位、长度为 $g_b$ 的合法子序列. $a_j$ 与 $a_i$ 共享第 $b$ 位, 所以 $a_j \land a_i \neq 0$ , 接上 $a_i$ 就得到长度 $len$ 的合法子序列.
$f_i$ 不超过 $len$ : 取达到 $f_i$ 的合法子序列, 前一项是 $j$ . $a_j \land a_i \neq 0$ , 取一个公共位 $b$ . 由归纳 $g_b \geqslant f_j$ , 而 $b$ 也是 $a_i$ 的 1 位, 所以 $len \geqslant g_b + 1 \geqslant f_j + 1 = f_i$ .
两条合起来 $len = f_i$ , 写回操作与 $g$ 的定义一致, 归纳成立.

代码

main.cpp 是正式主解. main.py 是同一算法的 Python 实现, 复杂度同阶, 与 C++ 并列放在这一节.

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/**
 * 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-26 13:20
 * update_at: 2026-10-26 16:36
 */
// main.cpp：按二进制位维护最长合法子序列长度，把 O(n^2) 的枚举压成 O(n * 30)。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXB = 31; // a_i <= 1e9 < 2^30，最多用到第 30 位

ll n;
ll best[MAXB]; // best[b]：以某个含第 b 位的数结尾的、最长合法子序列的长度

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

    cin >> n;

    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        ll x;
        cin >> x;

        // 第 i 个数能接在任何一个末项与它有公共位的子序列后面，取这些长度里的最大值。
        ll cur = 0;
        for (int b = 0; b < MAXB; b++) {
            if (((x >> b) & 1) && best[b] > cur) {
                cur = best[b];
            }
        }
        cur = cur + 1; // 接上自己

        // 以 x 结尾的最优子序列长度 cur，可以更新 x 的每一个二进制位。
        for (int b = 0; b < MAXB; b++) {
            if (((x >> b) & 1) && cur > best[b]) {
                best[b] = cur;
            }
        }

        if (cur > ans) {
            ans = cur;
        }
    }

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

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#!/usr/bin/env python3
# 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-26 13:30
# update_at: 2026-10-26 13:30

import sys

BITS = 30  # a_i <= 1e9 < 2^30，只需要看低 30 位


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    seq = [next(data) for _ in range(n)]

    best = [0] * BITS  # best[b]：以某个含第 b 位的数结尾的最长合法子序列长度
    ans = 0
    for x in seq:
        # 所有与 x 有公共位的末项都能接上 x，取其中最长的那个
        length = 1 + max((best[b] for b in range(BITS) if x >> b & 1), default=0)
        for b in range(BITS):
            if x >> b & 1:
                best[b] = max(best[b], length)
        ans = max(ans, length)

    print(ans)


if __name__ == "__main__":
    solve()

复杂度

每个元素只扫 $30$ 个二进制位, 每步 $O(1)$ .

时间 $O(n \log A)$ , 其中 $\log A \leqslant 30$ .
空间 $O(\log A)$ , 只需要 30 个桶; C++ 实现读一个处理一个, 不保存整个序列.

总结

本题的关键不是位运算本身, 而是把 DP 转移条件里"用不到的信息"删掉.

$O(n^2)$ 的转移记住的是"上一个元素是谁", 但条件只关心"有没有公共的 1 位". 把这个条件提升成状态维度, 历史信息就压缩成 30 个桶, 扫描降为常数.

同一个套路可以迁移到其他"末项只需满足某个弱条件"的子序列问题, 例如按值域分桶的 LIS 优化.

目录

形式化题目

样例

暴力解法

思路

代码

复杂度

瓶颈

正解

关键观察

样例推演

思路

代码

复杂度

总结