[原创]ZOJ 3870 Team Formation 第12届浙江省省赛B题 [位运算+思维]【数学】

Tabris

CSDNZOJ位运算数学

发布于：2016年4月18日

次浏览

[原创]ZOJ 3870 Team Formation 第 12 届浙江省省赛 B 题 [位运算 + 思维]【数学】

2016-04-18 22:51:32 Tabris_ 阅读数：611

博客爬取于 2020-06-14 22:44:32
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51183322

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3870

Team Formation

Time Limit: 3 Seconds Memory Limit: 131072 KB

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 T indicating 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 ith integer 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
2
3
1 2 3
5
1 2 3 4 5

Sample Output
1
6

题目大意：就是给你 N 个数，找寻其中的两个数使得这两个数的异或值大于这两个数中的任意一个的情况数。

解题思路 :
正常的时候应该两两计算异或值判断，复杂度为 O(n^2)，但是因为题目的数据量比较大为 10^6，会超时所以不可行。
那怎么办呢，。
既然题目说的是异或，那么就是位运算，那么就在二进制上思考。
题目要的又是异或的值大于这两个值的每一个也就是满足大于这两个数中大的一个即可，那么就想一想仅在二进制下，两个数怎么比较大小。
我们知道二进制下的值换算成 10 进制就是 2 的整数次幂加和的形式
example：
x = 100001110（2） = 2^8+2^3+2^2+2^1；
y = 100011010（2） = 2^8+2^4+2^3+2^1；
看等式右边很容易就能得出 x < y;
从最高位开始比较如果相同就比较下一位，直到出现不同的情况，如果不同即一为 0 一为 1 , 则这位为 1 的大，这时候后面的位数怎样都不重要了，变化的这一位在数值上已经比后面的位数最大的情况还要大了，所以不需要考虑;

知道这些在异或
二进制下同位运算相异为 1 (0^1/1^0) 相同为 0 (1^1/0^0)

一个数在异或运算之后要比本身大，需要的是其与其异或运算的数在最高位(不计算前导 0)的位上为 0;
解释一下：
100001110 想要得到一个比它大的一个数只需要在它为 0 的任意 1 位上变为 1 即可(这时需要在这位的前面的任何一位都不改变，而后面的值则无所谓，前文已经解释)
所以另 1 个数的最高位在这个数为 0 的位上即可

明白了以上几点，本题就可以做了，
首先要把每个数的二进制上的为 0 的位数都记录下来(前导 0 不算)
在把每个数在二进制上的最高位的 1（必为 1）记录下来
比如说在二进制上的某一位存在在这位上为 0 的数为 n 个，存在最高位在这位上的数为 m 个
则满足题目的结果就为 n*m 个；

而题目的数据为最大 10^9 那么在二进制上就不超过 int 整型既是 32 位;
所以只需要计算这 32 位的的情况的和即可

把每位的情况分别用两个数组来存就行

看下代码吧很短很好理解

# include<stdio.h>
# include<iostream>
# include<math.h>
# include<string.h>
using namespace std;
int a[40];
int b[40];

int main()
{
    int t,n,x,m,num;
    scanf("%d",&t);
    while(t--)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&x);
            num=0,m=0;
            while(x)
            {
                if(x&1)  m=num;
                else     a[num]++;
                num++;
                x>>=1;
            }
            b[m]++;
        }
        long long int sum=0;
        for(int i=0;i<=32;i++)
        {
            sum+=a[i]*b[i];
        }
        printf("%lld\n",sum);
    }
    return 0;
}