整数数组中最大异或次级的解决方案

Question

我正在尝试解决这个 codeforces 问题

 http://codeforces.com/contest/281/problem/D

给定一个整数数组，找出任意子序列中第一个和第二个最大元素的最大异或值？

我想不出解决这个问题的最佳方法。我阐明的解决方法很少使用排序、堆栈，但我找不到正确的解决方案。

我用谷歌搜索并找到了问题 setter 的解决方案代码。但我无法理解 C++ 中的解决方案，我对此很天真。

下面是问题setter的c++代码

using namespace std;
using namespace io;

typedef set<int> Set;
typedef set<int, greater<int> > SetRev;

namespace solution {
  const int SIZE = 100000 + 11;
  int n;
  int A[SIZE];
  II S[SIZE];

  Set P;
  SetRev P_rev;

  int result;
}

namespace solution {
  class Solver {
  public:
      void solve() {
        normalize();
        result = get_maximum_xor();
      }

      int get_maximum_xor() {
        int res = 0;

        for (int i = 0; i < n; i++) {
          int current_value = S[i].first;
          Set::iterator it_after = P.upper_bound(S[i].second);
          Set::iterator it_before = P_rev.upper_bound(S[i].second);

          if (it_after != P.end()) {
            int after_value = A[*it_after];
            res = max(res, current_value ^ after_value);
          }

          if (it_before != P_rev.end()) {
            int before_value = A[*it_before];
            res = max(res, current_value, before_value);
          }  

          P.insert(S[i].second);
          P_rev.insert(S[i].second);
        } 

        return res;
      }

      void normalise() {
        for (int i = 0; i < n; i++) {
            S[i] = II(A[i], i);
        }
        sort(S, S + n, greater<II>());
      } 


}

有人可以向我解释一下解决方案，我所理解的方法是零碎的而不是完全的吗？

Answer 1

好的，所以 Solver::solve() 首先调用 normalise:

  void normalise() {
    for (int i = 0; i < n; i++) {
        S[i] = II(A[i], i);
    }
    sort(S, S + n, greater<II>());
  }

它正在做的是获取一个整数数组 A - 比如 {4, 2, 9}，并填充一个数组 S，其中 A 的值被排序并与它们出现在 A 中的索引 - 对于我们的示例，{{2, 1}, {4, 0}, {9, 2}}.

然后求解器调用 get_maximum_xor()...

    for (int i = 0; i < n; i++) {
      int current_value = S[i].first;
      Set::iterator it_after = P.upper_bound(S[i].second);
      Set::iterator it_before = P_rev.upper_bound(S[i].second);

"for i" 循环用于从 S 中获取连续排序的值（这些值最初来自 A）。虽然您还没有发布完整的程序，所以我们无法确定 P 中没有预填充任何值，我假设是这样。我们确实知道 P 是 std::map 并且 upper_bound 搜索以查找 P 中大于 S[i].second 的第一个元素（[=31 所在的索引=] 出现在 A) 和上面的值中，然后是 P_rev 类似的东西，它是一个 std::map，其中值按降序排列，很可能它会被填充相同的值作为 P 但同样我们没有代码。

那么...

      if (it_after != P.end()) {
        int after_value = A[*it_after];
        res = max(res, current_value ^ after_value);
      }

...表示如果 P 中的任何值是 >= S[i].second，请在找到的索引 it_after 中查找 A （现在感觉 P 跟踪每个子序列中的最后一个元素（？）），并且如果 current_value 与来自 A 的值进行异或运算的结果多于任何较早的结果候选者（res)，然后用新的较大值更新 res。

它做的事情与 P_rev 类似。

终于...

      P.insert(S[i].second);
      P_rev.insert(S[i].second);

将 current_value 在 A 中的索引添加到 P 和 P_rev 以供将来迭代。

所以，虽然我没有解释算法为什么或如何工作（我什至没有阅读问题陈述），但我认为应该清楚 C++ 在做什么，也就是你说的正在挣扎 - 剩下的就靠你自己了 ;-).

整数数组中最大异或次级的解决方案

Solution for maximum xor secondary in an array of integers

c++

sorting

algorithm

xor