[洛谷P3760][TJOI2017]异或和

题目描述

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

输入输出格式

输入格式

第一行输入一个n,表示这序列的数序列 第二行输入n个数字a1,a2...an代表这个序列 0<=a1,a2,...an，0<=a1+a2...+an<=10^6

输出格式

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

输入输出样例

输入样例

3 1 2 3

输出样例

0

说明

【样例解释】

序列1 2 3有6个连续和，它们分别是1 2 3 3 5 6，则1 xor 2 xor 3 xor 3 xor 5 xor 6 = 0

【数据范围】

对于20%的数据，1<=n<=100 对于100%的数据，1<=n <= 10^5

---

想法

这个题还挺有意思的。

最初的想法是记录前缀和sum[]，枚举每个区间，计算异或和。复杂度O(\(n^2\)) 但这样明显过不了100%的数据，所以不能枚举每个区间。

依旧使用前缀和，每段区间和为sum[i]-sum[j] 注意到sum[n] \(\leq\) \(10^6\) ，于是可以一位位考虑区间对答案的贡献。 假设考虑到答案从右往左的第k位，当前区间和s=sum[i]-sum[j] 当s的第k位为1时对答案有贡献 s的第k位为1有这么几种可能： sum[i]第k位为1，sum[j]第k位为0，且相减时不会在第k位借位（即sum[i]的前k-1为组成的数>sum[j]的前k-1位组成的数） sum[i]第k位为1，sum[j]第k位为1，且相减时会在第k位借位 sum[i]第k位为0，sum[j]第k位为1，且相减时不会在第k位借位 sum[i]第k位为0，sum[j]第k位为0，且相减时会在第k位借位

将区间从左往右扫一遍，树状数组分别维护第k位为0或1的sum的前k-1位组成的数 按上边那几种可能计算对当前sum[i]有多少sum[j]满足sum[i]-sum[j]的第k位为1 cnt加一下 对于答案第k位，若cnt为偶数，则为0，否则为1

---

代码

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1000005; int sum[100005]; struct Bit{ int c[N],size; void clear(){ memset(c,0,sizeof(c)); size=0; } int lowbit(int x) { return x&(-x); } void add(int x){ size++; while(x<N){ c[x]++; x+=lowbit(x); } } int query(int x){ int ret=0; while(x){ ret+=c[x]; x-=lowbit(x); } return ret; } }p,q; //p:0 q:1 int n; int main() { int a; scanf("%d",&n); sum[0]=0; for(int i=1;i<=n;i++){ scanf("%d",&a); sum[i]=sum[i-1]+a; } int ans=0,cur,w; for(int i=0;i<20;i++){ cur=0; p.clear(); q.clear(); for(int j=0;j<=n;j++){ w=sum[j]&((1<<i)-1); if(sum[j]&(1<<i)){ cur+=p.query(w+1)+q.size-q.query(w+1); q.add(w+1); } else{ cur+=p.size-p.query(w+1)+q.query(w+1); p.add(w+1); } } if(cur&1) ans+=(1<<i); } printf("%d\n",ans); return 0; }

转载于:https://www.cnblogs.com/lindalee/p/8393239.html

相关资源：数据结构—成绩单生成器