XOR Clique
BaoBao has a sequence a1,a2,...,an. He would like to find a subset S of {1,2,...,n} such that ∀i,j∈S, ai ⊕aj<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: a1 ,a2 ,...,an(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
",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;
}*/