AcWing 3485. 最大异或和
原题链接
中等
作者:
acm_wf
,
2021-05-11 20:20:12
,
所有人可见
,
阅读 304
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 31 * N;
int n, m, idx;
int cnt[M];
int s[N];
int son[M][2];
void insert(int x, int flag) {
int p = 0;
for (int i = 30; i >= 0; i --) {
int u = x >> i & 1;
if (!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
cnt[p] += flag;
}
}
int query(int x) {
int p = 0, res = 0;
for (int i = 30; i >= 0; i --) {
int u = x >> i & 1;
if (cnt[son[p][!u]]) {
res = res * 2 + 1;
p = son[p][!u];
} else {
res = res * 2;
p = son[p][u];
}
}
return res;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
s[i] = s[i - 1] ^ x;
}
insert(s[0], 1);
int res = 0;
for (int i = 1; i <= n; i ++) {
if (i > m) insert(s[i - m - 1], -1);
res = max(res, query(s[i]));
insert(s[i], 1);
}
cout << res << endl;
return 0;
}
java 代码
import java.util.Scanner;
public class Main{
private static final int N = 100010, M = 31 * N;
private static int n, m;
private static int[] s;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
s = new int[N];
for (int i = 1; i <= n; i ++) {
int x = scanner.nextInt();
s[i] = s[i - 1] ^ x;
}
Trie trie = new Trie(M);
trie.insert(s[0] , 1);
int res = 0;
for (int i = 1; i <= n; i ++) {
if (i > m ) {
trie.insert(s[i - m - 1], -1);
}
res = Math.max(res, trie.query(s[i]));
trie.insert(s[i], 1);
}
System.out.println(res);
}
private static class Trie {
private final int BIT = 30;
private int idx;
private int[] cnt;
private int[][] son;
public Trie(int m) {
cnt = new int[m];
son = new int[m][2];
}
public void insert(int x, int flag) {
int p = 0;
for (int i = BIT; i >= 0 ;i -- ) {
int u = x >> i & 1;
if (son[p][u] == 0) {
son[p][u] = ++ idx;
}
p = son[p][u];
cnt[p] += flag;
}
}
public int query(int x) {
int p = 0, res = 0;
for (int i = BIT; i >= 0; i --) {
int u = x >> i & 1;
if (cnt[son[p][u ^ 1]] > 0) {
res = res * 2 + 1;
p = son[p][u ^ 1];
} else {
res = res * 2;
p = son[p][u];
}
}
return res;
}
}
}