CF1718A2 Burenka and Traditions (hard version)

思路

首先可以将题目的操作转化为：

1. 将一个数 $a_i$ 异或一个常数 $k$。

2. 将连续两个数 $a_i,a_{i + 1}$ 同时异或一个常数 $k$。

那么，你发现最坏情况下，操作次数是 $n$。那么考虑如何将多余步骤给减去。

发现，如果一个区间 $[l,r]$，$\oplus_{i = l}^{r}a_i = 0$，就可以由每两个数进行一次操作 2，进而减少一次操作。

然后使这种区间的数量尽可能多即可。用 map 记录，简单贪心一下就好。

Code

#include <bits/stdc++.h>
#define re register

using namespace std;

const int N = 1e5 + 10;
int n,ans,arr[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void solve(){
    int cnt = 0;
    map<int,bool> vis;
    n = ans = read(); vis[0] = true;
    for (re int i = 1;i <= n;i++) arr[i] = read();
    for (re int i = 1;i <= n;i++){
        cnt ^= arr[i];
        if (vis[cnt]){
            vis.clear(); vis[0] = true;
            ans--; cnt = 0;
        }
        else vis[cnt] = true;
    }
    printf("%d\n",ans);
}

int main(){
    int T; T = read();
    while (T--) solve();
    return 0;
}