[Leaf] [P4310] 绝世好题

luogu-p4310-绝世好题">Luogu-P4310 绝世好题

1. 核心逻辑

• 问题本质: 求最长子序列，满足相邻元素按位与运算不为 0。

• 破局转换:

  1. 瓶颈分析: $N=10^5$，朴素 $O(N^2)$ LIS 模型无法接受。

  2. 数值特性: $a_i \And a_{i-1} \neq 0$ 意味着它们在二进制下至少共享一个为 1 的位。

  3. 状态坍缩: 值域虽然大，但二进制位仅 30 位。与其记录以哪个“数”结尾，不如记录以“第 $k$ 位为 1 的数”结尾的最长长度。

  4. 转移: 对于当前数 $x$，枚举它所有为 1 的位 $j \in [0, 30]$。

     • $len = \max \{ f[j] \} + 1$

     • 更新所有 $j$：$f[j] = len$。

2. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;

int f[ 32 ], n;

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

    cin >> n;
    int ans = 1;
    for( int i = 1; i <= n; ++ i ) 
    {
        int x, current_max = 0;
        cin >> x;
        for( int j = 0; j <= 30; ++ j ) 
        {
            if( ( x >> j ) & 1 ) current_max = max( current_max, f[ j ] + 1 );
        }
        for( int j = 0; j <= 30; ++ j ) 
        {
            if( ( x >> j ) & 1 ) f[ j ] = max( f[ j ], current_max );
        }
        ans = max( ans, current_max );
    }

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

3. 归档备注

• 复杂度: $O(30N)$。

• 关键点: 理解“从位置域到值域位域”的降维打击。