K 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(a?i??,a?j??) 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≤10?5??), indicating the length of the sequence.
The second line contains n integers: a?1??,a?2??,...,a?n?? (1≤a?i??≤10?9??), indicating the sequence.
It is guaranteed that the sum of n in all cases does not exceed 10?5??.
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?i???a?j??<min(a?i??,a?j??)的集合且这个集合的元素最多，输出这个最多的值就是结果
我们在纸上画画就会发现，只有二进制位数相同的情况下才会满足情况，那么只有求出每一位的对应的元素数量，然后输出最大的数量就是答案
#include<bits/stdc++.h>
using namespace std;
int main()
{int t;scanf("%d", &t);while (t--){int n;int a[100005]={0};scanf("%d", &n);int k=0;for (int i = 0; i < n; ++i){int x,sum=0;scanf("%d", &x);while(x){sum++;x/=2;}a[sum]++;}for(int i=0;i<10000;i++){k=max(k,a[i]);}printf("%d\n",k );}}