注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

pro   

2014-02-10 22:07:34|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
寝室里面旁边各神犇讨论的题目,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< >
< >
  评论这张
 
阅读(29)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018