即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

BZOJ 4888 [Tjoi2017] 异或与

编程语言 SenyeLicone 110℃ 0评论
本文目录
[隐藏]

1.Description

在加里敦中学的小明最近爱上了数学竞赛,很多数学竞赛的题目都是与序列的连续和相关的。所以对于一个序列,求出它们所有的连续和来说,小明觉得十分的简单。但今天小明遇到了一个序列和的难题,这个题目不仅要求你快速的求出所有的连续和,还要快速的求出这些连续和的异或值。小明很快的就求出了所有的连续和,但是小明想考考你,在不告诉连续和的情况下,让你快速的求出序列所有的连续和的异或值。

2.Input

第一行输入一个nn,表示这序列的数字个数。

第二行输入nn个数字a1,a2,a3a1,a2,a3anan,代表这个序列。

0a1,a2,0≤a1,a2,,an0a1+a2+,an,0≤a1+a2++an106+an≤106

3.Output




输出这个序列所有的连续和的异或值。

4.Sample Input

3
1 2 3

5.Sample Output

0

6.HINT

对于20%20%的数据,1n10001≤n≤1000


对于100%100%的数据,1n105

7.Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

位运算+树状数组+思路~

先求出前缀和a[i],因为异或运算只与单个二进制位有关,所以我们按位来算,只需20位。

对于一位k,我们线性扫过所有前缀和,对于i,如果i的k位==1,那么只有当ji%(1<

或者j

位运算没有加括号……以后要注意啊~


#include

int n,a[100001],c[1<<20][2],ans,rev[21];

int read()
{
 int x=0,f=1;char ch=getchar();
 while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}
 while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
 return x*f;
}

void add(int u,int v,int k)
{
 for(u++;u<=rev[20];u+=u&(-u)) c[u][k]+=v;
}

int cal(int u,int k)
{
 int now=0;
 for(u++;u;u-=u&(-u)) now+=c[u][k];
 return now;
}

int main()
{
 n=read();rev[0]=1;
 for(int i=1;i<=20;i++) rev[i]=rev[i-1]<<1;
 for(int i=1;i<=n;i++) a[i]=a[i-1]+read();
 for(int k=0;k<20;k++)
 {
  int now=0;
  for(int i=1;i<=n;i++)
  {
   int x,y;
   x=((a[i]&rev[k])!=0);y=a[i]%rev[k];
   if(x) now++;
   now+=cal(rev[k]-1,x)-cal(y,x)+cal(y,x^1);
   add(y,1,x);
  }
  if(now&1) ans|=rev[k];
  for(int i=1;i<=n;i++) add(a[i]%rev[k],-1,(a[i]&rev[k])!=0);
 }
 printf("%d\n",ans);
 return 0;
}

转载请注明:CodingBlog » BZOJ 4888 [Tjoi2017] 异或与

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情