P4310 绝世好题 题解
由比滨丶雪乃
2019-08-22 23:48:29
# P4310 绝世好题
- [题目链接](https://www.luogu.org/problem/P4310)
- [位运算基础知识](https://www.baidu.com/s?wd=%E4%BD%8D%E8%BF%90%E7%AE%97%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86&ie=utf-8&tn=90562692_hao_pg)
- [更好的阅读体验](https://www.luogu.org/blog/Hikigaya/p4310-jue-shi-hao-ti-ti-xie)
- [我的博客qwq](https://www.luogu.org/blog/Hikigaya/)
## 1、暴力90分的做法
###### ~~可怜，弱小，又无助，不会卡常，只会暴力qwq~~
**暴力的做法很容易想到，定义状态 _fi_ 为以 _ai_ 结尾满足条件的子序列最长长度**
**那么很容易得到方程**
### _fi=max（f[i]，f[j]+1）_
**1<=j<i&&a[i] and a[j]！=0**
**复杂度为O（n^2）**
CODE
```cpp
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int n;
int ans;
int a[1000010];
int f[1000010];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i]=1;//初始化
}
for(int i=2;i<=n;i++)
for(int j=1;j<i;j++)//如上文解释的qwq
{
if(a[i]&a[j])
f[i]=max(1+f[j],f[i]);
ans=max(ans,f[i]);
}
printf("%d\n",ans);
return 0;
}
```
## 2、正解
**考虑到位运算的性质，当两个数在二进制的表示下时，有一位都为 1 时，就满足了题目所要求的条件**
**那我们就可以选择对于每一个数，找到其在二进制表示下为1的位数，做一个预处理**
**接下来是设计状态**
**设b[i]表示为在二进制的表示下第i位为1时题目所求子序列的最长长度**
**方程大致相同，需要注意每次循环进行维护**
时间复杂度 O（n log n），空间复杂度 O（n）
Code
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 100010
using namespace std;
int a[maxn],b[maxn];
int f[maxn];
int n;
int k;
int ans=-1;
inline int max(int a,int b)//自定义max函数，貌似会快一丢丢（雾）
{
return a>b?a:b;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
int Maxn=-1;
for(int j=1;j<=32;j++)//枚举到2^32 就好了
{
if(a[i]&(1<<j))//判断第j位是否为1
Maxn=max(Maxn,b[j]+1);//如果是的话，进行每一位答案的维护
}
for(int j=1;j<=32;j++)
{
if(a[i]&(1<<j))
b[j]=Maxn;//维护
}
ans=max(ans,Maxn);//记录qwq
}
printf("%d",ans);//AC
return 0;
}
```