https://www.luogu.com.cn/problem/P4310 第2题 最长 查看测评数据信息
给定一个长度是n的序列a[1,2,...n],现在你需要构造一个长度为m的数组b[1,2,...m],需要满足如下条件:
(1)b是a的子序列
(2)b[i]&b[i-1]!=0 (2<=i<=m)
问构造出b后,m的最大值是多少。
输入格式
输入文件共2行。第一行包括一个整数n。
第二行包括n个整数,第i个整数表示a[i]。
1<=n<=1e5,1<=a[i]<=1e9
输出格式
一个整数,表示m的最大值
输入/输出例子1
输入:
3
1 2 3
输出:
2
样例解释
无
位运算都考虑拆位!一位一位看!
做法一:
f[i]:以第i个数结尾满足的最长序列
记录lst数组,第i进制位是1属于的最近的a数组下标
https://www.luogu.com.cn/article/ncpi87q5
做法二:
逐步考虑每一位
对于每一位,二进制位数上是1的可以建一个图,例如
a的第3个进制位是1
b的第3个进制位是1
那么我们建 a->b 的有向边
图保证无环,我们找图的最长链就是答案(拓扑)
#include <bits/stdc++.h> using namespace std; const int N=1e5+5; int n, b[N], d[N], ans=0, dis[N]; vector<int> a[N]; queue<int> q; void topsort() { q.push(0); while (!q.empty()) { int u=q.front(); q.pop(); for (int i=0; i<a[u].size(); i++) { int v=a[u][i]; if (dis[v]<dis[u]+1) dis[v]=dis[u]+1; ans=max(ans, dis[v]); d[v]--; if (!d[v]) q.push(v); } } } int main() { scanf("%d", &n); for (int i=1; i<=n; i++) scanf("%d", &b[i]); for (int k=0; k<=32; k++) { int last=0; for (int i=1; i<=n; i++) if (b[i]&(1<<k)) { a[last].push_back(i); d[i]++; last=i; } } topsort(); printf("%d", ans); return 0; }
做法三:
覆盖
https://www.luogu.com.cn/article/w99xswjw
#include <bits/stdc++.h> using namespace std; const int N=50; int n, a, f[N], ans=0; int main() { scanf("%d", &n); for (int i=1; i<=n; i++) { int t=0, Max=0, cnt=0; scanf("%d", &a); t=a; while (t>0) { cnt++; if (t&1) Max=max(Max, f[cnt]); t>>=1; } cnt=0, t=a; while (t>0) { cnt++; if (t&1) f[cnt]=max(Max+1, f[cnt]); t>>=1; } } for (int i=1; i<=32; i++) ans=max(ans, f[i]); printf("%d", ans); return 0; }
标签:cnt,int,luogu,www,com,最长 From: https://www.cnblogs.com/didiao233/p/18357778