By yusijia

Updated:

Contents
  1. 1. 分析：

分析：

　　用bit[]记录下每个数的最高位(二进制形式)的位置。然后找到每个数的最高位后面
的第一个0，这个位置对应的最高位的数与这个数异或后肯定比原来的两个数大，所以
ans += bit[left];

  • 异或
  • 通过与运算找出某个数(二进制形式)的最高位的位置
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92


暴力去做会超时
/*
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

int date[100000];

bool cmp(int a, int b)
{
    return a < b;
}

int main()
{
    int T, n, counts;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        counts = 0;
        for(int i = 0; i < n; i++)
            scanf("%d", &date[i]);
        sort(date, date + n, cmp);
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if((date[i] ^ date[j]) > date[j])
                    counts++;
            }
        }
        printf("%d\n", counts);
    }
    return 0;
}
*/

正解：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

int bit[33];                    //bit[left]记录最高位(二进制形式)为left的数的个数
int a[100000+5];

void solve(int a)
{
    int left = 31;              //题目说每个数最多不超过10的9次方   (1 << 31) - 1为int的上限
    while(left >= 0){
        if(a & (1 << left)){    //找这个数(二进制形式)的最高位是第几位
            bit[left]++;        //记录最高位为left的数的个数
            return ;
        }
        left--;
    }
    return ;
}

int main()
{
    int T, n;
    scanf("%d", &T);
    while(T--){
        memset(bit, 0, sizeof(bit));
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            scanf("%d", &a[i]);
            solve(a[i]);
        }
        int ans = 0;
        for(int i = 0; i < n; i++){
            int left = 31;
            while(left >= 0){
                if(a[i] & (1 << left))     //找到这个数(二进制形式)的最高位
                    break;
                left--;
            }
            while(left >= 0){
                if(!(a[i] & (1 << left)))
                    ans += bit[left];
                left--;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
Contents
  1. 1. 分析：