企业官网建设流程全解析

LintCode 炼码 - 更高效的学习体验！

子数组的最大异或和_牛客题霸_牛客网

算法：最大子数组异或和_异或值最大的子数组-CSDN博客

这段代码是为了处理可能包含负数的整数数组，而负数的最高位（第 31 位）是符号位。在求最大异或值时，我们希望异或结果的数值尽可能大，而符号位为 0 的结果一定是正数，大于任何负数。因此，对于符号位，我们尽量让异或结果为 0，即num和target的符号位相同，所以target = index。而对于其他位（30 ~ 0），我们希望异或结果为 1，所以选择相反位target = 1 - index。

#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 处理多个 case std::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")