子数组异或和为0的最多划分

有两个结论:
1.设区间[0,i]的异或值为XOR[0,i]
由异或运算的性质，XOR[i,j]=XOR[0,j]^XOR[0,i]
例如:2^3^8^9
有 8^9= 2^3^8^9 ^(2^3)
2.如果有区间[k,i]和[k,j],i<j。并且这两个区间都有使得异或和为0的子区间，那么必然是选择[k,i]，然后再以i为起点，检查后面的区间。因为这样的话，可以多出[i,j]区间。有点绕，不知道该怎么描述。

有了这个结论后，这题就很简单了，为了使区间[i,j]的子区间异或值为零，只需要找到某个k，使得XOR[i,k]==XOR[i,j],那么就有XOR[k+1,j]等于0。这里我们借助hash_map来保存并查找前面的异或值。

#include 
(849)#include 
#include 
(849)#include 
using namespace std;
int main() {
    std::ios::sync_with_stdio(false);
#ifdef NOWCODER_THIS_PC
    freopen("in.txt", "r", stdin);
(963)#endif
    int n;
    while (cin >> n) {
        vector nums(n);
        unordered_set hash_set;
        int XOR=0;
        int ans=0;
        for (int i=0;i<n;i++){
            int num;
            cin>>num;
            XOR^=num;
            if (XOR==0){
                hash_set.clear();
                ans++;
                continue;
            } else{
                if (hash_set.find(XOR)!=hash_set.end()){
                    XOR=0;
                   ans++;
                   hash_set.clear();
                } else{
                    hash_set.insert(XOR);
                }
            }
        }
        cout<<ans<<endl;
    }
}

N = int(input())
nums = list(map(int, input().split()))
mp = {}
mp[0] = -1
dp = [0]*N
res = 0
Xor = 0
for i in range(N):
    Xor = Xor ^ nums[i]
    if Xor in mp:
        if mp[Xor] == -1:
            dp[i] = 1
        else:
            dp[i] = dp[mp[Xor]] + 1
    if i > 0:
        dp[i] = max(dp[i-1], dp[i])
    mp[Xor] = i
    res = max(res, dp[i])
print(res)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, x, s=0, Max=0;
    cin>>n;
    int dp[n];
    memset(dp, 0, sizeof(dp));
    map<int,int> M;
    M[0] = -1;
    for(int i=0;i<n;i++){
        cin>>x;
        s ^= x;
        if(M.find(s)!=M.end()){
            if(M[s]==-1)
                dp[i] = 1;
            else
                dp[i] = dp[M[s]]+1;
        }
        if(i>0)
            dp[i] = max(dp[i], dp[i-1]);
        M[s] = i;
        Max = max(Max, dp[i]);
    }
    cout<<Max<<endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n == 0) {
            System.out.println(0);
            return;
        }
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(getRes(arr));
    }
    
    
    /*
    dp[i]位置有两种情况：
    
    1. arr[i]位置无法被算进最后一组异或和为0的子数组中，此时dp[i] = dp[i-1]；
    2. 可以被算进最后一组异或和为0的子数组中，dp[i] = dp[k-1] + 1, 
    其中arr[k...i]为最后一组异或和为0的子数组。
    */
    public static int getRes (int[] arr) {
        //dp[i]表示0...i最多有几个异或和为0的子数组
        int[] dp = new int[arr.length];
        if(arr[0] == 0)
            dp[0] = 1;
        //map记录从[0...i]得到的所有异或和，以及最近一次他们出现的数位
        HashMap<Integer, Integer> map = new HashMap<>();
        //表示没开始遍历前，异或和为0
        map.put(0, -1);
        map.put(arr[0], 0);
        //记录每一次更新的异或和
        int eor = arr[0];
        for (int i = 1; i < arr.length; i++) {
            eor ^= arr[i];
            //如果之前在k-1位置出现过一次eor，那么k...i表示最近的最后一组异或和为0的子数组
            if (map.containsKey(eor)) {
                int index = map.get(eor);
                dp[i] = index == -1 ? 1 : (dp[index]+1);
            }
            dp[i] = Math.max(dp[i], dp[i-1]);
            map.put(eor, i);
        }
        return dp[dp.length-1];
    }
    
}

int main()
{
    int n;
    cin>>n;
    vector<int> dp(n+1,0);//dp[i]=k 表示前面i个数字异或和=k
    vector<int> Max(n+1,0);
    unordered_map<int,int> mp; //mp[k]=i 表示异或结果为k 的最后一个下标为i
    mp[0]=0;
    int tmp;
    for(int i=1;i<=n;i++)
    {
        cin>>tmp;
        dp[i]=dp[i-1]^tmp;
        Max[i]=Max[i-1];
        if(mp.find(dp[i])!=mp.end())  //若之前存在异或结果为 dp[i]  =》 mp[dp[i]]+1 => i 是一组异或为0的子数组
        {
            Max[i]=max(Max[i-1],1+Max[mp[dp[i]]]);//那么当前已有的子数组最多的个数
        }
        mp[dp[i]]=i;//当前异或值下标 放入map  
    }
    cout<<Max[n]<<endl;
}