首页 > 代码库 > Codeforces 282E Sausage Maximization(字典树)
Codeforces 282E Sausage Maximization(字典树)
题目链接:282E Sausage Maximization
题目大意:给定一个序列A,要求从中选取一个前缀,一个后缀,可以为空,当时不能重叠,亦或和最大。
解题思路:预处理出前缀后缀亦或和,然后在字典树中维护,每次添加并查询,过程中维护ans。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
struct Tire {
int sz, g[maxn * 100][2];
void init();
void insert(ll s);
ll find(ll s);
}T;
int N;
ll A[maxn], prefix[maxn], suffix[maxn];
int main () {
scanf("%d", &N);
for (int i = 1; i <= N; i++)
scanf("%lld", &A[i]);
for (int i = 1; i <= N; i++)
prefix[i] = prefix[i-1] ^ A[i];
for (int i = N; i; i--)
suffix[i] = suffix[i+1] ^ A[i];
ll ans = 0;
T.init();
for (int i = N; i >= 0; i--) {
T.insert(suffix[i+1]);
ans = max(ans, T.find(prefix[i]));
}
printf("%lld\n", ans);
return 0;
}
void Tire::init() {
sz = 1;
memset(g[0], 0, sizeof(g[0]));
}
void Tire::insert(ll s) {
int u = 0;
for (int i = 60; i >= 0; i--) {
int v = (s>>i)&1;
if (g[u][v] == 0) {
memset(g[sz], 0, sizeof(g[sz]));
g[u][v] = sz++;
}
u = g[u][v];
}
}
ll Tire::find (ll s) {
int u = 0;
ll ret = 0;
for (int i = 60; i >= 0; i--) {
int v = ((s>>i)&1) ^ 1;
if (g[u][v])
ret |= (1LL<<i);
else
v = v ^ 1;
u = g[u][v];
}
return ret;
}
Codeforces 282E Sausage Maximization(字典树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。