ZOJ 4057 XOR Clique(位运算)

XOR Clique

BaoBao has a sequence a​1​,a​2,...,a​n. He would like to find a subset S of {1,2,...,n} such that ∀i,j∈S, a​i ⊕a​j<min(ai ,aj) and ∣S∣ is maximum, where ⊕ means bitwise exclusive or.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains an integer n (1≤n≤100000), indicating the length of the sequence.

The second line contains n integers: a​1​​ ,a​​2​ ,...,a​n(1≤ai≤10的9次方), indicating the sequence.

It is guaranteed that the sum of n in all cases does not exceed 100000.

Output

For each test case, output an integer denoting the maximum size of S.

Sample Input

3

3

1 2 3

3

1 1 1

5

1 2323 534 534 5

Sample Output

2

3

2

题意,求在a数组中找出s子集,要求子集中任意两个数异或之后比这两个数都小,求最大子集里面元素的个数;

可以知道,2进制的0和1异或才是1,其他是0,要求两个数异或要更小,则必须两个相同长度的数二进制的最高位要都是1,所以,只需要知道在每个长度的集合中,存在多少个元素,元素最多的那个就是答案;

例3中,对应的log2(x)为0,11,9,9,2,可以得到534和534在长度9的子集中,最大子集元素个数为2;

#include<iostream>
#include<algorithm>
#include<string.h>
#include<cmath>
#include<map>
using namespace std;
map<int,int>m;//记录符合条件的子集元素个数
int main()
{
//init();
int T;
scanf("%d",&T);
while(T--)
{
m.clear();
int n,x;
scanf("%d",&n);
while(n--){
scanf("%d",&x);
m[log2(x)]++;//求二进制位数并记录出现次数
}
int cnt=0;
map<int,int>::iterator it;
for(it=m.begin();it!=m.end();it++)
cnt=max(cnt,it->second);//求m中最大值
printf("%d\n",cnt);
}
return 0;
}
/*
log2(x)求法
int w[31];
void init(){
for(int i=0;i<30;i++)
w[i]=1<<i;
}
int find(int x)
{
int l=0,r=30;
while(r-l>1)
{
int mid=l+r>>1;
if(w[mid]<=x)
l=mid;
else r=mid;
}
if(w[r]<x)
return r;
else
return l;
}*/
上一篇:织梦dedecms后台发布文章提示“标题不能为空”


下一篇:HDU1039 Easier Done Than Said?