Codeforces Round #539 (Div. 2) C. Sasha and a Bit of Relax(前缀异或和)

转载自：https://blog.csdn.net/Charles_Zaqdt/article/details/87522917

题目链接：https://codeforces.com/contest/1113/problem/C

题意是给了n个数字，让找出一个长度为偶数的区间[l, r]，使得al ^ al+1 ^ .... ^ amid = amid + 1 ^ ... ^ ar这个等式成立(l到mid的异或和等于mid+1到r的异或和)，求出有多少个满足要求的区间。

想要满足上述要求，即左边等于右边，那么整段l到r区间的抑或和的结果为0。那么反过来区间异或值为0，左边和右边相等吗？答案是肯定的。（其实任意分的两段都相等）。

同时由于异或满足类似于加法和减法性质，即如果a^b=c，则c^a=b,c^b=a。所以这里我们可以想到用抑或前缀和，因为我们可以理用前缀和很快的查找pre[r]^pre[l-1]得到这一段的抑或值，所以这道题就变成了求前缀抑或和的pre[r] - pre[l-1] = 0 而且l到r的长度必须是偶数的个数有多少个，其实判断长度为偶数也不是很难，我们把每一位前缀抑或和都按顺序标记上奇偶，对于r和l-1位置的奇偶性相同的话，这个区间就一定是长度为偶数的区间。

那么这道题就变成了寻找pre[r] = pre[l-1] 且 r位置和l-1位置的奇偶性相同的区间有多少个了，还有要注意的是第二个样例中求出来了pre前缀异或和的数组中有0的存在，也就是前4个的异或和为0也是符合要求的，那么对于这种数据的处理，我们可以在第0位加一个0就好了，就像第二个样例，pre[4] = pre[1-1] = 0，这样也是符合要求的，还有就是如果有多个符合要求的数，求的应该是他们的组合数，比如说求出来的前缀和是3 3 3 3那么方案就是1 + 2 + 3。

大致思路就是这样，写法有很多种，我的写法是用map+pair实现的，用map标记(这个数和这个数的奇偶性)出现的次数。

AC代码：

 #include<cstdio>

 #include<map>

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> P;

 map<P, int>ma;

 int main()

 {

     int n;

     scanf("%d", &n);

     ma[P(, )] = ;        //补充一个(0,0)

     int pre = ;            //异或前缀和

     LL ans = ;

     for (int i = ; i <= n; i++)

     {

         int tmp;

         scanf("%d", &tmp);

         pre ^= tmp;

         ans += ma[P(pre, i % )]++;

     }

     printf("%I64d\n", ans);

     return ;

 }

巴特西

Codeforces Round #539 (Div. 2) C. Sasha and a Bit of Relax(前缀异或和)

最新文章

热门文章