题目描述
给定一个长度为 (n) 的数列 (a_i)，求 (a_i) 的子序列 (b_i) 的最长长度 (k)，满足 (b_i & b_{i-1} e 0)，其中 (2leq ileq k)， $ &$ 表示位运算取与。
输入格式
输入文件共 (2) 行。 第一行包括一个整数 (n)。 第二行包括 (n) 个整数，第 (i) 个整数表示 (a_i)。
输出格式
输出文件共一行。 包括一个整数，表示子序列 (b_i) 的最长长度。
输入输出样例
输入 #1
3
1 2 3
输出 #1
2
题解
对于任意一个数 (b_i) 要满足条件 (b_i&b_{i-1} e 0) ，(namo) (b_i) 中存在二进制为 (1) 的位置与 (b_{i-1}) 中二进制为 (1) 的位置存在交集
目前而言只知道 (b_i) 需要寻找交集，则就是去进行枚举每一个位置，当 (b_i) 的这个位置二进制为 (1) ，进行寻找最大值
(b[i] = max(b[j]+1)) 当 (b_i&b_j e 0)
算到这里时间复杂度是 (O(n^2)) ，需要进行优化，
(namo) 就是保存一下记录 (i) 最近的，当前位置的二进制为 (1) 的位置。
也就是说使用一个数组 (cnt) ，(cnt_j) 表示距离当前位置最近并且 (b_k) 的第 (j) 的二进制为 (1) 的位置
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e5+55;
int cnt[80];
ll a[maxn];
int b[maxn];
int main(){
memset(cnt,0,sizeof(cnt));
int n,maxx=0;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
for(int j=0;j<40;++j){
if((a[i]>>j)&1){
b[i]=max(b[cnt[j]]+1,b[i]);
cnt[j]=i;
}
}
maxx=max(maxx,b[i]);
}
printf("%d
",maxx);
return 0;
}