【ZOJ 3870】 Team Formation

题意

n个数，找出有几对a、b 符合 a ^ b ＞ max(a,b) 。^表示异或号

分析

对于数a，如果它的二进制是：

1 0 1  0 0 1，那么和它 ^ 后 能比他大的数就是：

0 1 X X X X

0 0 0 1 X X

0 0 0 0 1 X

所以对应的b 在a的最高位1到后面第一次出现0之前，都为0，然后在a为0的位置里至少一个为1。

于是就是最高位1的位置有几个数储存下来就可以计算了。

代码

#include<cstdio>
#include<cstring>

int t,n,a[100005],k[35],b,p,ans;//最多32位二进制

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        memset(k,0,sizeof k);

        scanf("%d",&n);

        for(int i=1; i<=n; i++)
        {
            scanf("%d",&b);

            a[i]=b;
            p=0;
            while(b)//统计b有几位
            {
                b>>=1;
                p++;
            }
            k[p]++;//最高位在p
        }

        for(int i=1; i<=n; i++)
        {
            p=1;
            while(a[i])
            {
                if((a[i]&1)==0)//a的最高位后面出现的0
                {
                    ans+=k[p];
                }
                a[i]>>=1;
                p++;
            }
        }
        printf("%d
",ans);
    }
    return 0;
}