题目链接
题意分析
一看这道题我们 我们第一反应是枚举然后判断 但是这样的复杂度达到了\(O(2^{30}*n)\)
很显然是过不了的
我们冷静一波可以发现 如果将每一个数的前15位以及后15位拆开的话 也就是只考虑15位 这个复杂度是可以接受的
那么我们可以考虑使用Meet in The Middle
关键是匹配该如何匹配
我们对于前十五位 处理出一个序列\(popcount(a1 \bigoplus x)-popcount(ai \bigoplus x)\)
我们对于后十五位 处理出一个序列\(popcount(a1 \bigoplus x)-popcount(ai \bigoplus x)\)
我们把题意转化一下就可以发现 对于我们要求的x 上下两个序列是依次互为相反数的
那么我们将下面的序列取反 就是\(popcount(ai \bigoplus x)-popcount(a1 \bigoplus x)\) 也就成为了相等关系
这就成为了匹配标准
具体实现的时候 可以使用vector存储系列 然后使用map对于vector进行标记
强大的STL啊!
CODE:
#include
#include
#include
#include
#include
#include
#include
#include