pro
2014-02-10 22:07:34| 分类:
默认分类
| 标签:
|举报
|字号大中小 订阅
寝室里面旁边各神犇讨论的题目,DAY2下午的一道题目,给你一串数组,求其XOR和AND值相同的子序列的个数,如1 2 3 3 的答案为 6,如 1 2 3 3 123 234 。
首先我们枚举右边为结束点,然后我们就是求以之为右端点R的满足答案的个数。那么正常情况我们得枚举每一个点作为左端点。但是AND有一个非常奇葩的性质,假设我们已经知道了A(R)的二进制了,我们只需要知道从右往左起第一个在它的二进制中是1的地方是0的数,然后那个数之后的AND都是A(R),即一个确定右端点的子序列最多只有O(LogN)级别的答案,所以我们只要在O(1)找到每一个点,这个也可以用链表维护满足条件的数的前后顺序,从后到前,添加新数的时候先插在头部,求出其二进制,对于同一位为0的删掉,O(LogN)可以做。然后对异或值用HASH挂链表即可倍增在O(LogN)找到答案,这样复杂度就是O(NLog^2N),对于N< >
< >
评论这张
转发至微博
转发至微博
评论