AtCoder Regular Contest 098 D - Xor Sum 2 区间异或=相加 DP思想

2021年6月28日 12点热度 0条评论 来源: 丑心疼

题意:给出n个数,求它的连续子序列中,满足下列公式,(l,r)的对数有多少对

Al xor Al+1 xor … xor Ar=Al Al+1 + … Ar

思路:由题意可以得到,连续子序列,如果在ai这个数不符合公式的话,即之后的符合条件的对数中将不在需要这个元素,所有枚举元素来计算符合公式的对数 。

难以理解的就是异或等效于加法与减法(!!!)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define N 200005
 5 
 6 ll he[N],yi[N];
 7 
 8 int main()
 9 {
10     ll n,i,x,l,r,ans;
11 
12     while (scanf("%lld",&n)!=EOF)
13     {
14         for (i=1;i<=n;i++)
15         {
16             scanf("%lld",&x);
17             he[i]=he[i-1]+x;//计算加法前缀和 
18             yi[i]=yi[i-1]^x;//计算异或前缀和 
19         }
20 
21         l=1;//左端点 
22         ans=0;
23 
24         for (r=1;r<=n;r++)//以第r个数为结尾进行遍历 
25         {
26             for (;he[r]-he[l-1]!=(yi[r]^yi[l-1]);l++); //b到c的异或和=a到c的异或和 异或 a到b的异或和(可以证明)
27                 ans+=r-l+1;//l到r的串中共有长度个情况(1个数组成,2个数组成。。。) 
28         }
29         
30         printf("%lld\n",ans);
31         return 0;
32     }
33 
34     return 0;
35 }

 

转载于:https://www.cnblogs.com/hemeiwolong/p/9130384.html

    原文作者:丑心疼
    原文地址: https://blog.csdn.net/weixin_30599769/article/details/95854245
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。