首页 > 其他 > 详细

计数区间异或为0(可交)

时间:2020-02-12 09:18:48      阅读:106      评论:0      收藏:0      [点我收藏+]

https://ac.nowcoder.com/acm/contest/3005/D

题意:给出一组数n,问有多少区间异或和为0.
解法:如果[l,r]是合法的子段,说明前缀和中xorsum[r]^xorsum[l-1] = 0, xorsum[l-1] = xorsum[r]。
求出异或前缀和,然后使用map计数每一个数字有多少个前缀和等于那个数字即可。

#include <bits/stdc++.h>
#define ME(x , y) memset(x , y , sizeof(x))
#define SC scanf
#define rep(i ,j , n) for(int i = j ; i < n ; i ++)
#define red(i , n , j) for(int i = n-1 ; i >= j ; i--)
#define INF  0x3f3f3f3f
#define mod 998244353
#define PI acos(-1)
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
using namespace std;
typedef long long ll ;
const int maxn = 2e5+9;
int a[maxn];
int pre[maxn];

int main()
{
    map<int , int>m;
    int n ;cin>>n;
    int ans = 0 ;
    ll cur = 0 ;
    m[0] = 1 ;
    rep(i , 1 , n+1){
        int x ;
        scanf("%d" , &x);
        cur ^= x ;
        ans += m[cur];
        m[cur]++;
    }
    cout << ans << endl;
    return 0;
}

 

计数区间异或为0(可交)

原文:https://www.cnblogs.com/nonames/p/12297610.html

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