【5.10】AcWing夏季·最大异或和

2021年05月10日 21时53分

标签：滑动窗口二进制前缀和 Trie树

## 题目描述

给定一个非负整数数列 a，初始长度为 N。

请在所有长度不超过 M 的**连续**子数组中，找出子数组异或和的最大值。

子数组的异或和即为子数组中所有元素按位异或得到的结果。

注意：子数组可以为空。

#### 输入格式

第一行包含两个整数 N,M。

第二行包含 N 个整数，其中第 i 个为 ai。

#### 输出格式

输出可以得到的子数组异或和的最大值。

#### 数据范围

对于 20% 的数据，`1≤M≤N≤100`
对于 50% 的数据，`1≤M≤N≤1000`
对于 100% 的数据，`1≤M≤N≤10^5,0≤ai≤2^31−1`

#### 输入样例：

```
3 2
1 2 4
```

#### 输出样例：

```
6
```

#### 来源

> 来源：AcWing 3485
> 链接：[3485. 最大异或和 - AcWing题库](https://www.acwing.com/problem/content/description/3488/)

## 解题思路

前缀异或和 + Tire树求最大异或对 + 滑动窗口，简单思路可见代码。

需要使用如下的亦或运算的重要性质（[【5.7】LeetCode每日一题 ](http://www.vison307.com/90/)）：

![截屏2021-05-07 下午12.08.58.png](https://pic.stackoverflow.wiki/uploadImages/157/0/72/180/2021/05/07/12/09/30bdaedb-d561-47eb-913d-bff07ec41638.png)

## 代码

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
int xorSum[N];

struct node{
	int val;
	int cnt;
	node* next[2];
	node(int x = 0){
		val = x;
		cnt = 0;
		next[0] = next[1] = nullptr;
	}
};

class Trie{
	private:
		node* root;
	public:
		Trie(){
			root = new node();
		}
		
		// 将数字x插入Trie树(mode=1插入，mode=-1删除)
		void insert(int x, int mode){
			node* p = root;
			for(int i = 31; i >= 0; --i){
				int t = x >> i & 1;
				if(!p->next[t]){
					node* n = new node(t);
					p->next[t] = n;
				}
				p->next[t]->cnt += mode;
				p = p->next[t];
			}
		}
		
		// 在所有整数中，找到与x进行异或运算能够得到的最大结果
		int maxXor(int x){
			node* p = root;
			int res = 0;
			for(int i = 31; i >= 0; --i){
				int t = x >> i & 1;
				// 存在和x的第i位相反的数字
				if(p->next[!t] && p->next[!t]->cnt){
					res = res << 1 | 1;
					p = p->next[!t];
				}else{
					res = res << 1;
					p = p->next[t];
				}
			}
			return res;
		}
};

int main(void){
	Trie trie;
	int n, m, res = 0;
	
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++){
		int t;
		scanf("%d", &t);
		xorSum[i] = t ^ xorSum[i-1];
	}
	
	trie.insert(xorSum[0], 1);
	// 维护一个长度为M+1的滑动窗口，求其中的最大异或对（AcWing 143)
	// 为什么是M+1？因为S[i+M] ^ S[i] = a[i+1] ^ a[i+2] ^ ... ^ a[i+M]
	// S[i+M]~S[i]长度为M+1，对应长度为M的 a[i+1] ^ a[i+2] ^ ... ^ a[i+M]
	for(int i = 1; i <= n; i++){
		// 插入新进入滑动窗口的
		trie.insert(xorSum[i], 1);
		// 删除最左边不在滑动窗口里的
		if(i > m) trie.insert(xorSum[i-m-1], -1);
		res = max(res, trie.maxXor(xorSum[i]));
	}
	
	printf("%d\n", res);
	return 0;
	
}
```

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【5.10】AcWing夏季·最大异或和

所有评论

暂无评论

新增评论