Codeforces 1054D Changing Array 贪心+异或和

题意

给一个长度为\(n\)的位数为\(k\)的整数数列\(a\)，一次操作可将任意\(a_i\)取反，问经过任意次操作后最多有多少个区间异或和不为\(0\)

分析

求出前缀异或和，区间异或和为\(0?\)的区间数转化为求有多少对前缀异或和相等，然后用总区间数减一下，

对一个\(a_i?\)取反等同于对这个位置的前缀异或和取反，所以每个位置的前缀异或和有两种，贪心取当前值出现次数最小的一种，

总区间数为\(n*(n+1)/2?\) ,对于每个非\(0?\)数字减去\(C(x,2)?\),\(x?\)为这个数的出现次数，对于\(0?\)要减去\(C(x+1,2)?\)，可以在数列中加一个\(0?\)消除这个影响

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define bug cout<<"--------------"<<endl
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-6;
const int inf=1e9;
const ll llf=1e18;
const int mod=1e9+7;
const int maxn=2e5+10;
int n,k;
int a[maxn];
int b[maxn];
map<int,int>f;
int col(int x){
    return ((1<<k)-1-x);
}
vector<int>q;
int main(){
    ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]^=a[i-1];
    }
    for(int i=0;i<=n;i++){
        int x=col(a[i]);
        if(f[x]<f[a[i]]){
            a[i]=x;
        }
        if(!f[a[i]]) q.push_back(a[i]);
        f[a[i]]++;
    }
    ll ans=1ll*n*(n+1)/2;
    for(int x:q){
        ans-=1ll*f[x]*(f[x]-1)/2;
    }
    cout<<ans;
    return 0;
}

Codeforces 1054D Changing Array 贪心+异或和

原文：https://www.cnblogs.com/xyq0220/p/10882524.html