题目：
#10051. 「一本通 2.3 例 3」Nikitosh 和异或
解析：
首先我们知道一个性质(xoplus 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_Loplus sum_R}1leq L<Rleq 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;
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
