AcWing 3485. 最大异或和
原题链接
中等
作者:
憨憨有点懒
,
2021-05-10 21:02:40
,
所有人可见
,
阅读 334
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010 * 31, M = 100010;
int n, m;
int prexor[M];
int son[N][2], cnt[N], idx;
void insert(int x, int v) {
int p = 0;
// 把二进制表示看作字符串
for (int i = 30; i >= 0; i -- ) {
int u = x >> i & 1;
if (son[p][u] == 0) son[p][u] = ++ idx;
p = son[p][u];
cnt[p] += v;
}
}
int query(int x) {
int res = 0, p = 0;
for (int i = 30; i >= 0; i -- ) {
int u = x >> i & 1;
res <<= 1;
if (cnt[son[p][!u]]) { // 求异或最大值, 则同位能取反就取反。 如果取最小值,反过来即可
p = son[p][!u];
res += 1;
}
else {
p = son[p][u];
}
}
return res;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) {
int x;
cin >> x;
prexor[i] = prexor[i - 1] ^ x;
}
int res = 0;
insert(prexor[0], 1);
for (int i = 1; i <= n; i ++ ) {
if (i > m) insert(prexor[i - m - 1], -1); // 维持长度为 m 的区间( -1 相当于删除操作)
res = max(res, query(prexor[i]));
insert(prexor[i], 1);
}
printf("%d\n", res);
return 0;
}
```
不需要
//#include [HTML_REMOVED]
//#include [HTML_REMOVED]
//#include [HTML_REMOVED]
只要
//#include[HTML_REMOVED]
你是想说万能头?万能头编译会慢一点
是的但好写一点
不需要
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
只要万能库
#include[HTML_REMOVED]