題目連接: https://codeforces.com/problemset/problem/1109/A

題目大意: 給定n個數(shù) 問有多少個偶數(shù)長度的區(qū)間l,r 使得mid=(l+r-1)/2,l到mid的數(shù)異或等于mid+1到r的異或

官方題解,很詳細(xì)了 第一次學(xué)到異或還能求前綴和,斯巴拉西. 枚舉區(qū)間的方法也是第一次學(xué)到.
sum[i]代表a1~ai的異或和, 那么題目等價于求多少對l~r 使得sum[l-1]=sum[r] 因?yàn)橐髤^(qū)間長度為偶數(shù) 當(dāng)r為奇數(shù)時 l一定是偶數(shù) 那么l-1就是奇數(shù),反過來也一樣 .所以最后等價于 對當(dāng)前枚舉的i,i前面有多少與i奇偶性相同的sum[i],開了個map記錄下就行.
唯一需要注意的就是 mp[0][0]的初始值為1,看了很多博客也沒具體明白為什么 ,可能意思代表長度為0時異或?yàn)?也在數(shù)組中(猜的)
舉個例子,輸入為
2
1 1
如果不初始化 最后答案就是0 因?yàn)楫?dāng)i等于2時 mp[0][0]為0 ans+=mp[0][0] 導(dǎo)致對答案沒貢獻(xiàn)

#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<<endl using 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; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces #539 (Div. 1) A. Sasha and a Bit of Relax (异或 前缀和)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。