下定决心开始打CF的第一个比赛就被虐得好惨，还需要继续努力啊（虽然感觉CF和面试算法题关系不大。。）
题目网址： https://codeforces.com/contest/1322/problem/B
好吧，事实上写这篇博文是因为第一次遇到这个解法，对于我这个算法小白来说还是很新颖的。
PS.做题的时候天真的以为是O(n)的解法，并且可以用数学做。。。
题目
给定$n$个数 $a_1$, $a_2$, … , $a_n$，
计算其两两之和的异或值。
分析
首先输入大小以看就不可以直接求（废话）
复杂度也就是压在O(nlogn)左右
关键点
我们可以把答案回到二进制，然后对二进制的每一位分开求。
原理
首先我们定义 $x_i = a_k + a_j$， 即 $x_i$ 是两数之和。
令 $s$ 是答案，$s_i$ 是指从右往左答案的第 $i$ 个二进制位（从0开始）
我们现在假设计算 $s_i$，我们已知所有 $x$ 的第 $i$ 位的01情况，那么求 $s_i$ 就是对它们做异或，也就等于计算 $x$ 中第 $i$ 位是1的个数的奇偶情况。
即如果1有偶数个，那么答案对应的位数是0，反之则是1。（简单的异或运算原理）
Subproblem
对于结果$s$，计算第 $i$ 位的值，即 $s_i$。
（等价问题）计算两数之和$x$的第 $i$ 位是 $1$ 的数量。
对于这个等价问题，我们先思考一个简单的情况：
假设现在有一个数 $y < 2^{i+1}$，它的第$i$位的是否位$1$取决于它是否在 $[2^{i}, 2^{i+1})$ 内。
现在把 $y$ 扩大为正数，我们可以得到其第$i$位的情况与 $y’ = y \% 2^{i+1} $。
因此，对于每个 $x$，我们可以只考虑 $x \% 2^{i+1} $。
但我们希望能通过 $a$ 直接计算出个数，而非计算 $x$ 后求出解。
既然我们可以对 $x$ 取模，自然也可以对 $a$ 取模，这对加法并不会有影响。
因此，我们首先将 $a$ 对 $2^{i+1}$ 取模，令取模后的数为 $b$。
我们可以得到 $b \in [0, 2^{i+1} )$，
即有 $x \in [0, 2^{i+2}-1 )$。
我们发现 $x$ 的范围缩小了很多，这次我们不对 $x$ 取模，
相反，我们可以直接对 $x$ 划出两个范围：$[2^i, 2^{i+1})$ 和 $[2^i + 2^{i+1}, 2^{i+2}-1 )$
因此，我们希望寻找 $x$ 在这两个范围内的个数
Subsubproblem
对于结果 $s$ 的第 $i$ 位，现有 $b$ 是对 $a$ 对于 $2^{i+1}$ 取模，求 $b$ 两两之和在 $[2^i, 2^{i+1})$ 和 $[2^i + 2^{i+1}, 2^{i+2}-1 )$ 的个数。
（简化版）给定数组 $b$，求其两两和在某一区间的个数。
这里为简化，假设求的区间是 $[k, t)$
暂时只有 $O(nlogn)$ 的解法，未知是否有更迅速的
首先将 $b$ 从小到大排序，
然后对 $b_i$ ，它可以相加的数为 $b_{i+1}$, …, $b_n$ 。
用二分查找寻找下界值为 $k-b_i$ 的下标 $p$，
用二分查找寻找上界值为 $t-b_i$ 的下标 $q$。
满足的个数就是 $q-p$。
代码
1 |
|