首页 > 其他 > 详细

Codeforces Round #539 (Div. 2) C. Sasha and a Bit of Relax

时间:2019-02-21 01:00:03      阅读:221      评论:0      收藏:0      [点我收藏+]

链接:https://codeforces.com/problemset/problem/1113/C

题意:长度为n的序列 ,若l,r满足技术分享图片,则称这对l,r为funny,其中mid=(r-l+)/2

求出共有几对funny

思路:上式等价为al^al+^......ar-1^ar=0,可利用前缀和的思想进行求解,用a数组保存a0连续异或到ai的值,上式即等价于al=ar

由于题目只要考虑r-l+1为偶数的情况,易得r,l同奇偶,用二维数组b记录

代码:

 1 #include<bits/stdc++.h>
 2 #define inf 0x3f3f3f3f
 3 typedef long long ll;
 4 const int M = int(1e5)*3 + 5;
 5 using namespace std;
 6 ll a[M],b[2][(1<<20)+3];
 7 int main()
 8 {
 9     int n; cin >> n;
10     ll ans = 0;
11     b[0][0] = 1;
12     for (int i = 1; i <= n; i++)
13     {
14         int x;
15         cin >> x;
16         a[i] = a[i - 1] ^ x;
17         ans += b[i % 2][a[i]];
18         b[i % 2][a[i]]++;
19     }
20     cout << ans << endl;
21     return 0;
22 }

备注:异或运算的性质

Codeforces Round #539 (Div. 2) C. Sasha and a Bit of Relax

原文:https://www.cnblogs.com/harutomimori/p/10410055.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!