ZOJ3870 Team Formation————位运算&&思维

- 日理万妓 2022-04-23 23:58 128阅读 0赞

# Team Formation #

Time Limit: 2 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 10^9.

**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  
**Author**: LIN, Xi  
**Source**: The 12th Zhejiang Provincial Collegiate Programming Contest

--------------------

题目大意：给你n个数，让你找两个数组队，要求满足A⊕B>max(A,B),问有多少种方案

n是1e6，O(n^2)算法肯定不行，(训练的时候没想出来On的算法，所以肯定TLE了)

对于任意一个数字来说，我们都可以将它分解为二进制的形式：  
比如说: ( 10 ) 10 = ( 1010 ) 2 , (10)\_\{10\}=(1010)\_2, (10)10=(1010)2,

/*明天再写，困了，先把代码放这里*/  
好，对于x,y，我们假设x是二者比较大的，那么我们如果想要找到能够和x组队的人，那么它的值(y)应该小于等于x并且x⊕y>x  
假设x是 ( 18 ) 10 (18)\_\{10\} (18)10,那么它的二进制形式为 ( 10010 ) 2 (10010)\_2 (10010)2  
18的二进制形式中，最高位的1在第四个位置上(从右往左数,从0开始)  
我们可以想到，对于任意小于等于18的数，该数最高位1的位置刚好在18二进制形式上0的位置上，那么他俩异或的结果肯定会大于18，比如

> 1 = 1; 18^1 = 10010 ^ 1 = 10011 = 19>1  
> 8=1000; 18 ^ 8=10010 ^1000 =11010=26>18  
> 13=1101;18 ^ 13 = 10010 ^ 1101 = 11111 = 31>18  
> 15=1111 ;18 ^ 15 = 10010 ^ 1111 = 11101 = 29>18  
> …有很多

于是我们可以认为，对于任意x，任何小于等于x数的最高位1的位置刚好在x二进制形式上0的位置上  
那么 x⊕y > x(max(x,y))

那么问题就转化为统计数字最高位1的位置及个数，然后再对每一个数从最高为往低位判断，如果第i位为0，那么 ans += 二进制形式上最高为刚好是第i位的个数(因为最高位肯定是1)

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN = 1e6+7;
    int a[MAXN],bit[66];
    void f(int n)//找出数字n在二进制下最高位的1
    {
        
            int l = 31;
            while(l>=0)
            {
        
                    if(n&(1<<l))
                    {
        
                            bit[l]++;
                            break;
                    }
                    l--;
            }
    }
    int main()
    {
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            ios::sync_with_stdio(0);
            cin.tie(0);
            int t,n,x;
            cin>>t;
            while(t--)
            {
        
                    cin>>n;
                    memset(bit,0,sizeof(bit));
                    ll ans = 0;
                    for(int i=0;i<n;++i)
                    {
        
                            cin>>a[i];
                            f(a[i]);
                    }
                    for(int i=0;i<n;++i)
                    {
        
                            int l = 31;
                            while(l>=0)
                            {
        
                                    if(a[i]&(1<<l)) break;
                                    l--;
                            }
                            while(l>=0)
                            {
        
                                    if(~a[i]&(1<<l))        ans += bit[l];
                                    l--;
                            }
                    }
                    cout<<ans<<endl;
            }
            return 0;
    }