2020牛客寒假算法基础集训营4.D——子段异或【前缀】

2020牛客寒假算法基础集训营4.D——子段异或【前缀】

​​题目传送门​​

题目描述

输入描述:

第一行一个整数 n ，代表数列长度。 第二行 n 个整数，代表数列。

输出描述:

输出一个整数，代表答案。

输入

5 1 2 3 2 1

输出

2

说明

子段 [1,3] 和子段 [3,5] 是合法子段。

备注:

题解

AC-Code

#include using namespace std;#defineconst int maxn = 2e5 + 7;int a[maxn];int main() { int n; cin >> n; ll ans = 0; int num = 0; map mp; mp[0] = 1; for (int i = 0; i < n; i++) { cin >> a[i]; num ^= a[i]; // 记录前缀和 ans += mp[num]; // 加上之前前缀和是num的次数 mp[num]++; // 次数++ } cout << ans << endl; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。