异或和XOR 题解

这道题最先想到的应该是暴力枚举
代码如下:

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

const int N=5e5+10;
int n,cnt,k,a[N],p[N];

int main(){
    cin>>n>>k;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        p[i]=p[i-1]^a[i];
    }

    for (int i=1;i<=n;i++){ // 区间的left
        for (int j=i;j<=n;j++){ // 区间的right
            int t=p[j]^p[i-1];
            if (t==k){
                cnt++;
                i=j;
                break;
            }
        }
    }
    cout<<cnt;

    return 0;
}

这样很明显是错的

举个例子:
8 3
2 3 0 3 1 0 7 4
上述代码仅会输出 2 （2 3 0 3 1 和 0 7 4）

这说明从左到右枚举是不合理的

那从右到左呢?
代码如下:

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

const int N=5e5+10;
int n,cnt,k,a[N],p[N];

int main(){
    cin>>n>>k;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        p[i]=p[i-1]^a[i];
    }

    int lr=0; // 最新区间的right
    for (int i=1;i<=n;i++){
        for (int ll=i;ll>lr;ll--){ // 区间的left
            int t=p[i]^p[ll-1];
            if (t==k){
                cnt++;
                lr=i;
                break;
            }
        }
    }
    cout<<cnt;

    return 0;
}

很好，程序已经能过15个测试点了，只有5个超时，那开始优化吧
很明显可以用动规
代码如下:

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

int n, k, a[500010], p[500010], dp[500010];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] ^ a[i];
    }

    map<int, int> p_cnt;
    p_cnt[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];      // 后面发现的区间数 总不小于 前面

        int tg = p[i] ^ k;      // 期望的异或值
        // 在p-cnt(map)里尝试找tg
        if (p_cnt.find(tg) != p_cnt.end()) {  // 找到
            // 当前区间是否与已有区间交叉(实现较复杂)
            // 注:在本程序中,比较数量的大小即可
            if (dp[i] < p_cnt[tg] + 1) {
                dp[i] = p_cnt[tg] + 1;
            } else {
                // 放弃此区间
            }
        }

        // 在p-cnt(map)里更新前缀和值
        p_cnt[p[i]] = dp[i];
    }

    cout << dp[n];

    return 0;
}

至此，题解

谢谢观看!