【BZOJ 4260】Codechef REBXOR

66 阅读 0 评论 44 点赞

我是靠谱客的博主迷人红牛，最近开发中收集的这篇文章主要介绍【BZOJ 4260】Codechef REBXOR，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.题目链接。给定一个数组，找出两个不相交的区间，得这两个区间元素异或和加起来最大。

2.首先第一个需要解决的问题是：如何找出n个数里，找一个区间他们异或和最大。解决这个问题其实不难，DP[i]表示前i个数异或起来最大，然后我们做一个前缀异或和，然后在更新DP时，顺序插入字典树，在第i个位置时，这里的转移：DP[i]=max(DP[i-1),query(pre[i]).这里不难理解，因为前缀异或的性质，pre[i]^pre[j]=a[i]^a[i+1]^...a[j].所以我们在查询pre[i]的最值时，在它前边已经字典树上插入了前i-1个前缀，在字典树上找到最值，这个最值代表的一定是一段连续的区间，因为相同的部分会被抵消掉。所以通过这种手段就找到异或最大的那段区间的最值。同理做一个后缀异或和，但是怎么保证区间不重复呢？很简单，枚举当前位置，我们把这个位置当作第二个区间，也就是后缀区间最大值+前缀区间最大值，而前缀区间最值就是dp[i-1].所以再继续刚才的操作，维护答案即可。

#include<bits/stdc++.h>
#define MAXN 400010
using namespace std;
int a[MAXN];
int dp[MAXN], pre[MAXN], suf[MAXN];
struct Trie
{
	int tol;
	int val[MAXN * 32];
	int ch[MAXN * 32][2];
	void init()
	{ //初始化 
		tol = 1;
		ch[0][0] = ch[0][1] = 0;
	}
	void insert(int x)
	{
		int u = 0;
		for (int i = 32; i >= 0; i--)
		{
			int v = (x >> i) & 1;
			if (!ch[u][v])
			{
				ch[tol][0] = ch[tol][1] = 0;
				val[tol] = 0;
				ch[u][v] = tol++;
			}
			u = ch[u][v];
		}
		val[u] = x;
	}
	int query(int x)
	{
		int u = 0;
		for (int i = 32; i >= 0; i--)
		{
			int v = (x >> i) & 1;
			if (ch[u][v ^ 1]) u = ch[u][v ^ 1];
			else u = ch[u][v];
		}
		return x ^ val[u];
	}
}tr;

int main()
{
	int n;
	while (~scanf("%d", &n))
	{
		for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
		suf[n + 1] = pre[0] = 0;
		for (int i = 1; i <= n; i++)pre[i] = pre[i - 1] ^ a[i];
		for (int i = n; i >= 1; i--)suf[i] = suf[i + 1] ^ a[i];
		memset(dp, 0, sizeof(dp));
		tr.init();
		tr.insert(pre[0]);
		for (int i = 1; i <= n; i++)
		{
			dp[i] = max(dp[i - 1], tr.query(pre[i]));
			tr.insert(pre[i]);
		}
		tr.init();
		tr.insert(suf[n+1]);
		int ans = 0;
		for (int i = n; i >= 1; i--)
		{
			ans = max(ans, tr.query(suf[i]) + dp[i - 1]);
			tr.insert(suf[i]);
		}
		printf("%dn", ans);
	}
	return 0;
}