Codeforces282E Sausage Maximization (01Trie)

题目链接: Sausage Maximization

大致题意

给出长度为n的序列$a$​​​, 你需要选择一个前缀与后缀, 选择的前后缀不能相交, 可以为空.

问: 在所有的选择中, 前缀与后缀的所有元素异或结果最大是多少?

解题思路

01Trie

首先考虑一个简化模型, 给出一个序列, 可以选择两个不同位置的数字, 求异或的最大结果.
我们可以用01Trie, 通过枚举其中的一个数字来计算出当前最大结果, 最后答案是所有结果取max即可.

对于本题: 我们可以把所有前缀存入Trie中, 然后枚举每一个后缀. 由于前后缀不能有交集, 因此我们可以对于每个节点记录第一次出现的位置(位置记录靠左), 每次判断一下这个节点的位置是否在后缀之中即可.

---

代码细节:
​ 由于前后缀可以取空, 因此需要插入0, 表示没有前缀的情况. 同时需要对于0进行一次查询.
​ 查询时, 空节点的位置我们是不能到达的, 注意写法需不需要对空节点进行初始化设置.

AC代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1E5 + 10, B = 40, M = N * B;
int t[M][2], ind;
int L[M];
ll a[N];

void insert(int a, ll c) {
	int x = 0;
	for (int i = B - 1; i >= 0; --i) {
		int w = c >> i & 1;
		if (!t[x][w]) t[x][w] = ++ind;
		x = t[x][w];
		if (!L[x]) L[x] = a;
	}
}

ll ask(int a, ll c) {
	int x = 0; ll res = 0;
	for (int i = B - 1; i >= 0; --i) {
		int w = c >> i & 1;
		if (L[t[x][w ^ 1]] < a) {
			res += 1ll << i;
			x = t[x][w ^ 1];
		}
		else x = t[x][w];
	}
	return res;
}
int main()
{
	int n; cin >> n;

	L[0] = 0x3f3f3f3f;
	insert(0, 0);

	ll sum = 0;
	rep(i, n) {
		scanf("%lld", &a[i]);
		sum ^= a[i];
		insert(i, sum);
	}

	ll res = ask(n + 1, 0);
	sum = 0;
	for (int i = n; i >= 1; --i) {
		sum ^= a[i];
		res = max(res, ask(i, sum));
	}

	cout << res << endl;

	return 0;
}

END