首页 > 其他 > 详细

【ATcoder】Xor Sum 2

时间:2019-03-01 22:23:05      阅读:200      评论:0      收藏:0      [点我收藏+]

题目大意:给定一个 N 个点的序列,求有多少个区间满足\(\oplus_{i=l}^ra[i]=\sum\limits_{i=l}^ra[i]\)

题解:
小结论:\(a\oplus b=a+b\rightarrow a\&b=0\)
对每个点来说,考虑向右延伸能够满足条件的右端点的位置,显然右端点的位置单调不减,双指针扫一遍即可。

代码如下

#include <cstdio>
using namespace std;
const int maxn=2e5+10;

int n,a[maxn];
long long ans;

void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int l=1,r=1,now=0;l<=n;){
        while(r<=n&&now+a[r]==(now^a[r]))now^=a[r++];
        ans+=r-l,now^=a[l++];
    }
    printf("%lld\n",ans);
}

int main(){
    solve();
    return 0;
}

【ATcoder】Xor Sum 2

原文:https://www.cnblogs.com/wzj-xhjbk/p/10458988.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!