洛谷 P4310 题解

洛谷 P4310 题解

$\text{Description}$

给定一个序列 $\{a\}_{i=1}^{n}$,求出其满足任意非首元素与之前驱元素的按位与非零的子序列的最大长度。

$n\le 10^5,a_i\le 10^9$.

$\text{Solution}$

这题和最长上升子序列挺像,首先考虑正常 DP:

设 $f(i)$ 表示以第 $i$ 个元素结尾的满足条件的子序列的最大长度,则有:

思考优化的方式,由于题目与位运算有关,我们可以从二进制的角度观察。假设当前准备计算 $f(i)$,我们自然而然地想到将 $a_i$ 写成二进制,我们发现它仅会被与其有至少一个二进制位都为 $1$ 的前面的数转移。

考虑记 $M(k)$ 表示当前考虑的前若干个数中 $2^k$ 这一二进制位上有 $1$ 的数的 $f$ 的最大值。若准备计算 $f(i)$,我们可以枚举它所有为 $1$ 的二进制位,然后用 $M(k)+1$ 更新。在更新结束后,我们再用 $f(i)$ 更新 $M(k)$ 即可。

$\text{Code}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
#define REG register
using namespace std;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}

int n;

int Mx[35],Ans,Tmp1,Tmp2;

inline void Work(){
read(n);
for(REG int i=1;i<=n;++i){
read(Tmp1);
for(REG int B=0;B<=29;++B)
if(Tmp1&(1<<B)) Tmp2=max(Tmp2,Mx[B]+1);
for(REG int B=0;B<=29;++B)
if(Tmp1&(1<<B)) Mx[B]=Tmp2;
Ans=max(Ans,Tmp2);
}
printf("%d\n",Ans);
}

int main(){Work();}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×