Description
给定一个长度为n的数字序列a,从中选取一个长为m的子序列b满足 b[i]&b[i-1]!=0 (2<=i<=m)
求最大的m。
Input
第一行输入一个整数t,代表有t组测试数据。
每组数据第一行输入一个整数n代表a序列的长度,接下来一行输入n个正整数表示ai(0<i<=n)。
1<=t<=20,0<=n<=100000,0<=ai<=1e9。
Output
一个整数表示最大的m。
Sample Input
1
3
1 1 1
Sample Output
3
这里面要的是子序列 并非连续 但也不是乱序 但是要从前往后来统计
a&b!=0 即转化为二进制后 在相同的位置是同为1 即1和2 用二进制即1和10 在相同位置上没有同是1 所以1&2=0
如8和9 二进制为1000和1001 因为在第一位同为1 则8&9!=0
因为数比较大 非常好的覆盖更新 话不多话 看代码
#include<algorithm> #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<math.h> using namespace std; #define INF 0x3f3f3f3f #define LL long long #define N 100010 int a[100],sum[N],num[N]; int ans; void q(int x,int d) {int k=0;while(x>0)///将数字转化为二进制 因为a&b!=0 即在二进制中的同一位同为1 {a[k++]=x%2;x=x/2;}for(int i=0;i<k;i++){if(a[i]==1){sum[d]=max(sum[num[i]]+1,sum[d]);///因为在这一位上为1 即要找到在这一位上 已经有多少个 当然要最大值num[i]=d;///num不断的更新使得在这一位上的数越来越大 在同是这一位上 肯定是d越大的数sum越大ans=max(ans,sum[d]);///每次进来 都可能改变最大值 }} } int main() {int T,n,e;scanf("%d",&T);while(T--){memset(sum,0,sizeof(sum));memset(num,0,sizeof(num));ans=0;scanf("%d",&n);for(int i=1;i<=n;i++)///这里面的的i 不能从0到n-1 后面会重复利用到0 {scanf("%d",&e);q(e,i);///一个一个的传进去 进行判断更新 }printf("%d\n",ans);}return 0; }