xor

//感觉可以优化，但是通过了= =
//直观的思路
#include<iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    int a[n];
    for(int i = 0; i < n; i++) {
        cin>>a[i];
    }
    int dp[n][n][2];
    for(int i = 0; i < n; i++) {
        dp[i][i][0] = a[i];
        dp[i][i][1] = (a[i] == 0) ? 1:0;
    }
    
    for(int j = 1; j < n; j++) {
        for(int i = 0; i+j < n; i++) {
            dp[i][i+j][0] = dp[i][i+j-1][0]^a[i+j];
            dp[i][i+j][1] = (dp[i][i+j][0] == 0) ? 1:0;
            for(int k = 0; k < j; k++) {
                dp[i][i+j][1] = max(dp[i][i+j][1], dp[i][i+k][1]+dp[i+k+1][i+j][1]);
            }
        }
    }
    cout<<dp[0][n-1][1]<<endl;
    
    return 0;
}

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

int main(){
    int n, x, s=0, cnt=0;
    scanf("%d", &n);
    unordered_map<int, bool> mp;
    mp[0] = true;
    while(n--){
        scanf("%d", &x);
        s ^= x;
        if(mp[s]){
            cnt++;
            mp.clear();
        }
        mp[s] = true;
    }
    printf("%d\n", cnt);
    return 0;
}

/// @brief 给出n个数字 a_1,...,a_n，问最多有多少不重叠的非空区间，使得每个区间内数字的xor都等于0
/// https://www.nowcoder.com/questionTerminal/7cffea0c097c4337821ab3ba25447c1c
///
/// @file maxNonOverlapSeg.cpp
/// @author cuichao
/// @date 2018-09-08

#include <stdio.h>
#include <iostream>

using namespace std;

/// @brief find max num of non-overlap segments in array
///
/// find max segment num in array, such that xor of numbers in each segment
/// is zero
/// 
/// @param a Input array
/// @param maxSeg Recorded intermedia results, maxSeg[i] is max non-onverlap
/// segment num for array[i:end] 
/// @param be Begin idx of subarray to search
/// @param n Lenght of input array
/// @return int Max num of non-overlap segments
int findMaxNonOverlapSeg(const int a[], int maxSeg[], int be, int n){
    if(be >= n) return 0;
    if(maxSeg[be] > 0) return maxSeg[be];

    int maxSegNum = 0, segNum = 0;
    int j, re_xor;
    for(int i=be; i<n; i++){
        j = i;
        re_xor = a[j++];
        while(j<n && re_xor!=0) re_xor ^= a[j++];

        if(re_xor == 0){
            segNum = 1 + findMaxNonOverlapSeg(a, maxSeg, j, n);
            maxSegNum = max(maxSegNum, segNum);
        }
    }
    maxSeg[be] = maxSegNum;
    return maxSeg[be];
}

int main(){
    int N;
    cin >> N;

    int a[N];
    int maxSeg[N];
    for(int i=0; i<N; i++){
        cin >> a[i];
        maxSeg[i] = 0;
    }

    int maxSegNum = findMaxNonOverlapSeg(a, maxSeg, 0, N);
    printf("%d\n", maxSegNum);
    return 0;
}

#用一个set或者map更新一下。每重复出现一次就清空一下所有信息并且答案++，
#然后重新保存set或map。开始的时候要放一个map[0]为了考虑边界条件（也就是一开始就是0的情况）
a=[3,0,2,2]
num = set([0])
last = 0
ans = 0
for i in a:
    last ^= i
    if last in num: 
        print(last)
        ans += 1
        num = set([0])    #
        last = 0
    else:
        num.add(last)
print(ans)

//B站讲解https://www.bilibili.com/video/BV13g41157hK?t=1897.1&p=30
#include <iostream>
#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<int>nums(n);
    // dp[i] -> arr[0..i]在最优划分的情况下，异或和为0最多的部分是多少个
    vector<int>dp(n);
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }

    int xor1 = 0;
    // key : 从0出发的某个前缀异或和
	// value : 这个前缀异或和出现的最晚位置(index)
    unordered_map<int, int>hash;
    hash[0]=-1;
    for(int i=0;i<n;i++){
        xor1^=nums[i];// xor -> 0..i所有数的异或和
        if(hash.count(xor1)){// 上一次，这个异或和出现的位置 
            // pre -> pre + 1 -> i , 最优划分，最后一个部分的开始位置
            // (pre+1, i)最后一个部分
            // a    0..a   (a+1..i)
            int pre=hash[xor1];
            dp[i]=pre==-1? 1:(dp[pre]+1);
        }
        if(i>0){
            dp[i]=max(dp[i-1],dp[i]);
        }
        hash[xor1]=i;//xor1的下标只存最近位置的
    }
    cout<<dp[n-1];
    return 0;


}
// 64 位输出请用 printf("%lld")

// 牛客 XOR
// https://www.nowcoder.com/questionTerminal/7cffea0c097c4337821ab3ba25447c1c
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int mostXOR(vector<int> &arr)
{
    if (arr.empty())
        return 0;

    unordered_map<int, int> map;
    vector<int> dp(arr.size(), 0);

    int eor = 0;
    map[0] = -1;
    map[arr[0]] = 0;
    dp[0] = arr[0] == 0 ? 1 : 0;
    for (int i = 1; i != arr.size(); ++i)
    {
        eor ^= arr[i];
        if (map.find(eor) != map.end())
        {
            int preEorIndex = map[eor];
            dp[i] = preEorIndex == -1 ? 1 : (dp[preEorIndex] + 1);
        }
        dp[i] = std::max(dp[i - 1], dp[i]);
        map[eor] = i;
    }
    return dp.back();
}

int main()
{
    int N;
    cin >> N;
    vector<int> arr(N, 0);
    for (auto &i : arr)
        cin >> i;
    cout << mostXOR(arr) << endl;
    return 0;
}