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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【迈克杯二弹番外】【hash】【异或运算】  

2013-11-03 21:38:53|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
  题目大意就是寻找区间s[i..j]使得s[i]xor s[i+1]...xor s[j]=k
  咱首先了解一个性质 a xor b xor b=a,也就是说异或相同的东西就变成了0,然后a 异或之就是还是等于a,那么我们把这个结论运用到这道题目中,假设有 s[i..j]满足异或和为0,那么 s[1..i-1] xor s[i..j] xor k 会等于什么呢?显然会等于s[1..i-1],也就是说假设我们固定了右端点,那么 所有满足异或和为K的i必有 s[1..i-1]=s[1..j] xor k,那么我们可以枚举右端点j,然后求满足s[1..i-1]=s[1..j] xor k的i有多少个就可以了,怎么做呢?最快的方法当然就是用HASH毫无压力,初始值不超过10000,10000最多14位,我们只需要将HASH表开到16384就可以了,然后读入的时候处理每一个前缀异或和,将它插入HASH表中,然后我们枚举j,算出s[1..i-1]的值p,然后直接让ans加上hash[p]就可以了。
注意要先更新ans再将s[i]插入,不然会将s[i+1,i]这种算进去的。
========================================================================

program xorr;
var hash:array[0..16384]of longint;
    s:array[0..5000]of longint;
    n,k:longint;
procedure init;
var i,j,p:longint;
    ans:longint;
begin
 read(n,k);
 fillchar(hash,sizeof(hash),0);
 s[0]:=0; ans:=0;
 inc(hash[s[0]]);
 for i:=1 to n do
  begin
    read(j);
    s[i]:=s[i-1] xor j;
    p:=s[i] xor k;
    inc(ans,hash[p]);
    inc(hash[s[i]]);
  end;
 write(ans);
end;

begin
  init;
end.

  评论这张
 
阅读(11)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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