Nikitosh 和异或(trie树)

题目：

解析：

首先我们知道一个性质$x\oplus x=0$

我们要求$$\bigoplus_{i = l}^ra_i$$的话，相当于求$$(\bigoplus_{i = 1}^la_i)\oplus (\bigoplus_{i = 1}^ra_i)$$

所以我们维护一个异或前缀和$sum_i$

我们用$l_i$表示从左往右到第$i$位时的区间最大异或和

$r_i$表示从右往左到第$i$位时的区间最大异或和

显然$l_i = max\{sum_L\oplus sum_R\}1\leq L<R\leq i$

$r_i$同理

最后枚举求和$ans=max\{ans,l_i+r_{i+1}\}$

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 5e6 + 10;

int n, m, num, ans;

int a[N], sum[N], l[N], r[N];

struct node {

	int nx[2];

} e[N]; 

void insert(int x) {

	bitset<35>b(x);

	int rt = 0;

	for (int i = 30; i >= 0; --i) {

		int v = (int)b[i];

		if (!e[rt].nx[v]) e[rt].nx[v] = ++num;

		rt = e[rt].nx[v];

	}

}

int query(int x) {

	bitset<35>b(x);

	int rt = 0, ret = 0;

	for (int i = 30; i >= 0; --i) {

		int v = (int)b[i];

		if (e[rt].nx[v ^ 1]) ret = ret << 1 | 1, rt = e[rt].nx[v ^ 1];

		else ret <<= 1, rt = e[rt].nx[v];

	}

	return ret;

}

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), sum[i] = sum[i - 1] ^ a[i];

	insert(0);

	for (int i = 1; i <= n; ++i) {

		ans = max(ans, query(sum[i]));

		l[i] = ans;

		insert(sum[i]);

	}

	num = ans = 0;

	memset(e, 0, sizeof e);

	for (int i = n; i >= 1; --i) {

		ans = max(ans, query(sum[i]));

		r[i] = ans;

		insert(sum[i]);

	}

	ans = 0;

	for (int i = 1; i < n; ++i) ans = max(ans, l[i] + r[i + 1]);

	cout << ans;

}

巴特西

Nikitosh 和异或(trie树)

题目：

解析：

代码

最新文章

热门文章