[原创]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位的的情况的和即可

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

看下代码吧 很短 很好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 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;
}