题目连接: /problemset/problem/1109/A
题目大意: 给定n个数 问有多少个偶数长度的区间l,r 使得mid=(l+r-1)/2,l到mid的数异或等于mid+1到r的异或
官方题解,很详细了 第一次学到异或还能求前缀和,斯巴拉西. 枚举区间的方法也是第一次学到.
sum[i]代表a1~ai的异或和, 那么题目等价于求多少对l~r 使得sum[l-1]=sum[r] 因为要求区间长度为偶数 当r为奇数时 l一定是偶数 那么l-1就是奇数,反过来也一样 .所以最后等价于 对当前枚举的i,i前面有多少与i奇偶性相同的sum[i],开了个map记录下就行.
唯一需要注意的就是 mp[0][0]的初始值为1,看了很多博客也没具体明白为什么 ,可能意思代表长度为0时异或为0也在数组中(猜的)
举个例子,输入为
2
1 1
如果不初始化 最后答案就是0 因为当i等于2时 mp[0][0]为0 ans+=mp[0][0] 导致对答案没贡献
#include<cstdio>#include<cstring>#include<cmath>#include<string>#include<iostream>#include<vector>#include<map>#include<set>#include<stack>#include<queue>#include<stdlib.h>#include<algorithm>#include<time.h>#include<unordered_map>#define bug1(g) cout<<"test: "<<g<<endl#define bug2(g,i) cout<<"test: "<<g<<" "<<i<<endl#define bug3(g,i,k) cout<<"test: "<<g<<" "<<i<<" "<<k<<endl#define bug4(a,g,i,k) cout<<"test: "<<a<<" "<<g<<" "<<i<<" "<<k<<endlusing namespace std;typedef long long ll;unordered_map<int,int>mp[2];int main(){ios::sync_with_stdio(0);ll n,x,a,ans=0;cin>>n;mp[0][0]=1;x=0;for(int i = 1;i<=n;i++){cin>>a;x^=a;ans+=mp[i%2][x];++mp[i%2][x];}cout<<ans<<endl;return 0;}
如果觉得《Codeforces #539 (Div. 1) A. Sasha and a Bit of Relax (异或 前缀和)》对你有帮助，请点赞、收藏，并留下你的观点哦！
