【ZOJ - 3870】Team Formation（异或，思维）

题干：

For an upcoming programming contest, Edward, the headmaster of Marjar University, is forming a two-man team from N students of his university.

Edward knows the skill level of each student. He has found that if two students with skill level A and B form a team, the skill level of the team will be A ⊕ B, where ⊕ means bitwise exclusive or. A team will play well if and only if the skill level of the team is greater than the skill level of each team member (i.e. A ⊕ B > max{A, B}).

Edward wants to form a team that will play well in the contest. Please tell him the possible number of such teams. Two teams are considered different if there is at least one different team member.

Input

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

The first line contains an integer N (2 <= N <= 100000), which indicates the number of student. The next line contains N positive integers separated by spaces. The ithinteger denotes the skill level of ith student. Every integer will not exceed 109.

Output

For each case, print the answer in one line.

Sample Input

Sample Output

1
6

题目大意：

给n个数。任选两个数，如果异或大于他们两个数，那么方案数+1。问有多少种方案数。

解题报告：

可以发现，如果要让一个数增大，只要该数化为二进制后的出现0的位置跟1异或就会变大，同时需要满足另一个数的最高位为该数出现0位置的位数，如10可以跟1异或变为11 ，100可以跟10、11、1异或分别变为110,111,101,而101只能跟两位的进行异或，因为它的0出现的位置为第二位。

以上部分来自某题解、、

就说下实现吧：其实很简单排个序后从小往大扫，边统计答案边更新数组就行了。

这种题做多了。。见到都感觉是套路了、、

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
int a[MAX];
int cnt[MAX];
int c[MAX];
int main()
{
	int t,n;
	cin>>t;
	while(t--)
	{
		memset(cnt,0,sizeof(cnt));
		scanf("%d",&n);
		for(int i = 1; i<=n; i++) scanf("%d",a+i);
		sort(a+1,a+n+1);
		for(int x,cur,i = 1; i<=n; i++)
		{
			x=a[i],cur = 0;
			while(x) {
				cnt[++cur]+=x%2;
				x/=2;
			}
			c[i]=cur;
		}
		ll ans=0;
		int all=n;
		for(int x,cur,i = 1; i<=n; i++) {
			ans += all-cnt[c[i]];
			all--;
			x=a[i],cur=0;
			while(x) {
				cnt[++cur] -= x%2;
				x/=2;
			}
		}
		printf("%lld\n",ans);
	} 
	return 0;
}