AcWing - 3485. 最大异或和

Solost

2023 年 03 月 28 日

204 次浏览

暂无评论

1715字数

题目题解

![image(1).png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F28%2Fimage%281%29.png)

## 题目链接

[题目链接](https://www.acwing.com/problem/content/description/3488/)

## 题解

```cpp
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 3100010;
int s[N];
int tr[N][2], idx, cnt[N];
void insert(int x, int v){
    int p = 0;
    for(int i = 30; i >= 0; i--){
        int u = x >> i & 1;
        if(!tr[p][u]) tr[p][u] = ++idx;//如果当前树没有子树，那么现在子树数目加1
        p = tr[p][u];//如果存在子树，那么就把p移动到当前子树位置
        cnt[p] += v;
	/*记录当前点的子树个数，因为每个数都能对每一位产生影响，而不是之前trie树的模板提那样只把整个字符遍历完才算一个*/
    }
}

int query(int x){
    int res = 0, p = 0;
    for(int i = 30; i >= 0; i--){
        int u = x >> i & 1;
        if(tr[p][!u]) res = res * 2 + 1, p = tr[p][!u];
        else res *= 2, p = tr[p][u];
    }
    return res;
}

void solve(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        s[i] = s[i - 1] ^ x;
    }
    int ans = 0;
    insert(s[0], 1);
    for(int i = 1; i <= n; i++){
        if(i - m - 1 >= 0) insert(s[i - m - 1], - 1);
	/*
	因为异或和计算时时s[r] ^ s[l - 1], l = i - m + 1, l - 1 = i - m,所以l-1项没用
	*/
        ans = max(ans, query(s[i]));
        insert(s[i], 1);
    }
    cout << ans << endl;
}
int main(){
    // IOS;
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
```

最后修改：2023 年 03 月 28 日