前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Codeforces Round #539 (Div. 2) C. Sasha and a Bit of Relax(前缀异或和)

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

作者头像
Ch_Zaqdt
发布2019-03-06 09:40:01
4220
发布2019-03-06 09:40:01
举报
文章被收录于专栏:Zaqdt_ACM

题目链接: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,所以这里我们可以想到用抑或前缀和,因为我们可以理用前缀和很快的查找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代码:

代码语言:javascript
复制
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int pre[300005];
typedef pair<int,int> p;

int main()
{
  int n;
	cin>>n;
	ll ans = 0;
	int xx = 0;
	map<pair<int,int> ,int> ma;
	ma[p(0, 0)] = 1;
	for(int i=1;i<=n;i++){
		cin>>pre[i];
		pre[i] ^= pre[i-1];
		ans += ma[p(pre[i], i % 2)] ++;
	}
	cout<<ans<<endl;
  return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年02月17日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档