发现各位DL的时复和空复都太低了，所以给一种 逆天 的双log做法

满足 j<i 且 a[j]&a[i]!=0 的j才能对i有贡献 所以DP

设f[i]表示以i为结尾的最长子序列长度

为方便说明，设f[j]_k表示满足条件的f[j]是通过二进制下第k位向f[i]转移的

可以发现，对于每个a[i]的每个k，只有最后那个可向i转移的j有用

证明:

• 1.若f[j]可向f[i]转移，则最终的f[i]一定比此f[j]大 (否则就可让f[i]=f[j]+1，使结论继续成立)
• 2.将结论1推广到每个i，即可证明

那么，只需预处理每个a[i]的每个k的最后一个j,再对每个a[i]的每个k进行遍历就好了

可设s[k][i]为1到i的a[i]中，(a[i]>>k)&1 的数量

遍历每个a[i]的每个k时再二分查找就好了

感觉自己说的不大清楚

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],s[39][100005],f[100005];
void prepare(int a,int id)
{
	int cnt=0; 
	while(a){
		if(a&1) s[cnt][id]=1;
		cnt++;a>>=1;
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		prepare(a[i],i);
		for(int j=0;j<31;j++) s[j][i]+=s[j][i-1];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<31;j++)
		{
			int w;
			if((a[i]>>j)&1){
				w=lower_bound(s[j],s[j]+n+1,s[j][i]-1)-s[j];
				f[i]=max(f[i],f[w]+1);
			}
		}
	}
	cout<<*max_element(f+1,f+n+1);
	return 0;
}

$dp_i$ 表示以 $a_i$ 结尾的最长子序列长度。

显然

$$dp_i=\max{(dp_j+1)[dp_i \operatorname{and} dp_j \ne 0]} $$

直接转移是 $\operatorname{O}(n^2)$ 的。

但可以通过按位拆分后，记录前缀最大值做到 $\operatorname{O}(n \log V)$。

code:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
long long maxn[40];
long long a[N];
long long dp[N];
int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=30;j++)
		{
			if(a[i]&(1<<j))
			{
				dp[i]=max(dp[i],maxn[j]+1);	
			} 
		}
		for(int j=0;j<=30;j++)
		{
			if(a[i]&(1<<j))
			{
				maxn[j]=max(dp[i],maxn[j]);	
			} 
		}
	}
	long long ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}

动态规划比较人性的一道题

设dp[i][j]表示：考虑前i个数，最后一个数的第j位为1的最长子序列（有点绕）

怎么转移QwQ

假设将x放到某一个序列末尾，那这个序列的最后一个数（设为y），需要与x有共同为1的位（即x&y!=0）。共同是1的位可以是任意一位，只要这一位上x是1就可以。

将可以转移的序列长度取max

while (x) {
	s++; //第几位 
	if (x&1) //如果当前这位x是1，即可以转移 
		sum = max(sum, dp[s]); //那就取max 
	x>>=1; //>>去掉考虑完的这一位 
}
sum++; //要把x放到序列末尾，所以长度加一 

现在最后一位变成了x，那x为一的位也要更新答案

//原理同上 
s = 0; //好习惯 
while (x) {
	s++;
	if (x&1)
		dp[s] = max(dp[s], sum);
	x>>=1;
}

完结散花~~~

80pts

题意与“最长上升子序列”相似，只需将 a[i]<a[j] 换成 a[i]&a[j] 即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int n,tmp,ans,a[N],dp[N];
signed main(){
	cin>>n;
	for(int i = 1;i<=n;i++)cin>>a[i],dp[i]=1;
	for(int i = 2;i<=n;i++){
		for(int j = 1;j<i;j++)
			if(a[i]&a[j])dp[i]=max(dp[i],dp[j]+1);
		ans=max(ans,dp[i]);
	}
	cout<<ans<<'\n';
	return 0;
}

100pts

设dp[i]为结尾第i位为1的最长子序列长度。 因为1<=n<=1e5，2^31绝对能满足，按位&即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int n,tmp,ans,a[N],dp[32];
int check(int x,int y){
	if(x&(1<<y))return 1;
	return 0;
}
signed main(){
	cin>>n;
	int c,ans=0;
	for(int i = 1;i<=n;i++)cin>>a[i];
	for(int i = 1;i<=n;i++){
		tmp=1;//赋初值！ 
		for(int j = 0;j<=31;j++)
			if(check(a[i],j))
				tmp=max(tmp,dp[j]+1);
		for(int j = 0;j<=31;j++)
			if(check(a[i],j))
				dp[j]=max(dp[j],tmp);
		ans=max(ans,tmp);
	}
	cout<<ans<<'\n';
	return 0;
}

本人tmp忘记赋初值。。。

（崩溃

要记得写暴力对拍来检查代码 （也可以再开一个数组f[]来保存每一次的tmp，最后ans取max）

题解

思路

子序列中相邻两位与起来不等于 $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;
}