洛谷 P4310 绝世好题 题解

洛谷 P4310 绝世好题 题解

xiaoh 2020-7-22

题意

给定$n$个正整数$a_i$，求$a$最长的满足$b_i\&b_{i+1}\ne0$子序列$b$的长度。

数据范围

$1\leq n\leq 10^5,0\leq a_i\leq 10^9$

题解

首先考虑最朴素的$dp$方程。记$f_i$为以$a_i$为结尾的最长的$b$。那么转移方程为:

$f_i=[1\leq j<i,a_i\&a_j\ne 0]\;\max (a_j+1)$

但是这个转移方程是$O(n^2)$的，那么我们如何进行优化呢？我们想到了坐标转换。既然要求$b_i\& b_{i+1}\ne 0$，那么我们不妨设计一个$dp$方程使其在$dp$过程中始终满足这个性质。我们令$f_i$为$b$序列最后一个元素二进制第$i$位为$1$的最长的子序列，那么此时转移方程为：

$f_i=[a[j]\&(1<<i)\ne 0,a[j]\&(1<<k)\ne 0]\;max(f_k+1)$

此时复杂度就变为了$O(n\log a_i)$，直接计算即可

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=100010,LOGN=31;
int n;
int a[MAXN];
int f[MAXN];
int ans=0;
int main()
{
    read(n);
    for(int i=1;i<=n;++i) read(a[i]);
    for(int i=1;i<=n;++i)
    {
        int maxn=0;
        for(int j=0;j<LOGN;++j)
        if(a[i]&(1<<j)) maxn=max(maxn,f[j]);
        for(int j=0;j<LOGN;++j)
        if(a[i]&(1<<j)) f[j]=max(f[j],maxn+1);
    }
    for(int i=0;i<LOGN;++i) ans=max(ans,f[i]);
    write(ans),putchar('\n');
	return 0;
}