LintCode 炼码 - 更高效的学习体验!
子数组的最大异或和_牛客题霸_牛客网
算法:最大子数组异或和_异或值最大的子数组-CSDN博客
#include <iostream>
#include <limits>
#include <new>
#include <vector>
using namespace std;struct Trie {std::vector<Trie*> next;int val;Trie() {val = -1;next.resize(2, nullptr);}
};void insert(Trie* root, int num) {if (!root) {return;}for (int i = 31; i >= 0; --i) {int index = (num >> i) & 1;if (!root->next[index]) {root->next[index] = new (std::nothrow) Trie;}root = root->next[index];}root->val = num;
}int search(Trie* root, int num) {if (!root) {return -1;}for (int i = 31; i >= 0; --i) {int index = (num >> i) & 1;int target = 1 - index;if (i == 31) {target = index;}if (root->next[target]) {root = root->next[target];} else {root = root->next[1 - target];}}return root->val;
}class Solution {
public:Solution() {}int solve(std::vector<int>& nums) {Trie* root = new (std::nothrow) Trie;int result = -1;int prefix_sum = 0;insert(root, 0);for (auto num : nums) {prefix_sum ^= num;insert(root, prefix_sum);int tmp = search(root, prefix_sum);result = max(result, tmp ^ prefix_sum);}return result;}
};int main() {int a, b; while (cin >> a) { // 注意 while 处理多个 casestd::vector<int> nums;nums.reserve(a);for (int i = 0; i < a; ++i) {cin >> b;//cout << "b :" << b << endl;nums.push_back(b);}Solution sol;cout << sol.solve(nums) << endl;}
}
// 64 位输出请用 printf("%lld")