【题解】异或序列

题目描述

Venn有一个数列\(a_1,a_2,...,a_n\).有一天，BLUESKY007拿来了一个正整数\(X\)。Venn是一个特别喜欢异或(xor)运算的孩子，她也很喜欢BLUESKY007。于是，Venn就想知道，自己能找到多少对数(i,j)能够满足\(a_i \ xor \ a_j = X\). 两个数对\((i_1,j_1)\)与\((i_2,j_2)\)不同，当且仅当\(i_1 \neq i_2\)或者\(j_1 \neq j_2\)。

思路

这题暴力肯定要超时（50分）。固要用二分查找。

解析

这道题除了用上面的算法外，还有一个比较容易理解的方法，详见代码。

这道题首先需要知道一个性质: 如果 a ^ b = c, 则 a ^ c = b, b ^ c = a.

不知道这个性质, 这道题西奈.

当你有一个有序数组, 应该怎样快速的判断这个数组里有多少个值等于 x 的数呢?

eg. a[] = {1, 2, 4, 5, 5, 6, 6, 10, 23, 74}; 且数组长度 n = 10, 你要查询这个数组里出现了多少次 x = 5.

先求出第一个大于 x 的数的地址, 再求出第一个大于等于 x 的数的地址, 两者相减就是答案. 即：

1	ans = std::upper_bound(a, a+n, x) - std::lower_bound(a, a+n, x);

那么有同学要问了: std::upper_bound 和 std::lower_bound 不是返回地址吗?

Answer:

1
2
3

 (std::upper_bound(a, a+n, x) - a) - (std::lower_bound(a, a+n, x) - a)
=std::upper_bound(a, a+n, x) - a - std::lower_bound(a, a+n, x) + a // 两个 a 抵消, 得
=std::upper_bound(a, a+n, x) - std::lower_bound(a, a+n, x)

时间复杂度为 \(O(log n) \ll O(n)\).

不知道这个性质, 这道题西奈.

这道题还有一个比较坑的, 就是时限太小. 所以你必须手写排序或者手写二分以提高效率.

不知道这一点, 这道题西奈.

#include <iostream>
#include <algorithm>
#include <cstring>
typedef long long LL;
const int N = 1e6 + 9;
int n, x, a[N];
int b[N], c[260];
void rsort() {
    for (int k = 0; k < 32; k += 8) {
        memset(c, 0, sizeof c);
        for (int i = 1; i <= n; ++i) ++c[a[i]>>k & 0xFF];
        for (int i = 1; i <= 0xFF; ++i) c[i] += c[i-1];
        for (int i = n; i; --i) {
            int t = a[i]>>k & 0xFF;
            b[c[t]--] = a[i];
        }
        memcpy(a+1, b+1, n*sizeof(int));
    }
}
int main() {
    scanf("%d%d", &n, &x);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    rsort();
    LL ans = 0, last = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == a[i-1]) {
            ans += last;
            continue;
        }
        int t = a[i] ^ x;
        last = std::upper_bound(a+1, a+n+1, t) - std::lower_bound(a+1, a+n+1, t);
        ans += last;
        // printf("when i=%d, last=%d\n", i, last);
    }
    printf("%lld", ans);
    return 0;
}