ZOJ 3870 數學思維

題意：給你n 個數 ，讓你找出其中有多少組數字 a 異或b 大於max（a, b）

題解：首先了解異或運算的方式 相同為0 不同為1 可以知道如果要增大肯定是要不同的位多於相同的位，其次需要知道 2的n次方等於2的n-1次訪加到2的1次訪再加1，即最高位影響大於低位之和，也就是說只有某個數字它和其他數字最大位不相同，則異或必然大於max(a, b)；

代碼：

#include
#include
#include
using namespace std;
int value[100005];
int main()
{
int T, mark[31], n, a[31];
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d", &value[i]);
}
sort(value+1, value+1+n);
int sum = 0;
memset(a, 0, sizeof(a));
for(int i = 1; i <= n; i++)
{
memset(mark, 0, sizeof(mark));
int num = 0;
sum += (i-1);
while(value[i])
{
mark[num++] = value[i]%2;
value[i] /= 2;
}
int maxx;
for(int i = 0; i < num; i++)
{
if(mark[i]) sum -= a[i], maxx = i;
}
a[maxx] ++;
}
printf("%d\n", sum);
}
}