题解

思路

子序列中相邻两位与起来不等于 $0$，就是说明至少有一个位置使得这两个数该位置皆为 $1$，不难想到定义一个数组 $g_i$ 统计以第 $i$ 位为 $1$ 的数结尾的最长符合要求子序列长度，具体操作如下：

当放入一个数的时候，遍历其每一位为 $1$ 的位置，找到其中 $g_i$ 最大值，然后将所有其每一位为 $1$ 的位置的 $g_i$ 更新为该位置长度 $+1$，最后输出 $g_i$ 数组中的最大值即可。

时间复杂度 $O(n\cdot\log_2 V)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define getchar getchar_unlocked
template<typename T>
void read(T& x) {
	x=0;
	char ch=getchar();
	long long f=1;
	while(!isdigit(ch)) {
		if(ch=='-')f*=-1;
		ch=getchar();
	}
	while(isdigit(ch)) {
		x=x*10+ch-48;
		ch=getchar();
	}
	x*=f;
}
template<typename T,typename... Args>
void read(T& first,Args&... args) {
	read(first);
	read(args...);
}
template<typename T>
void write(T arg) {
	T x=arg;
	if (x<0) {
		putchar('-');
		x=-x;
	}
	if(x>9) {
		write(x/10);
	}
	putchar(x%10+'0');
}
template<typename T,typename... Args>
void write(T arg,Args... args) {
	write(arg);
	if(sizeof...(args) !=0) {
		putchar(' ');
		write(args...);
	}
}
const int N=1e5+10,mod=1e9+7;
ll n,x,d,s;
ll g[40];
int main() {
	read(n);
	for(int i=1;i<=n;i++){
		read(x);
		s=x;
		d=0;
		for(int j=1;j<=32;j++){
			ll y=x&1;
			if(y)d=max(d,g[j]);
			x>>=1;
		}
		for(int j=1;j<=32;j++){
			ll y=s&1;
			if(y)g[j]=max(d+1,g[j]);
			s>>=1;
		}
	}
	ll ans=0;
	for(int i=1;i<=32;i++)ans=max(ans,g[i]);
	write(ans);
	return 0;
}