Решение для максимального xor вторичного в массиве целых чисел

Question

Я пытаюсь решить эту проблему codeforces

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

Учитывая массив целых чисел, найти максимальную xor первого и второго элемента max в любой из подпоследовательностей?

Я не могу найти оптимальный подход для решения этой проблемы. Немногие из методов решения, которые я сформулировал, использовали сортировку, стек, но я не мог найти правильное решение.

Я гуглил и узнал код установщика проблемы для решения. Но я не мог понять решение, как это в C++, и я наивен к нему.

Ниже приведен код установщика проблемы в 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 (индекс, по которому current_value появился в 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, уважать A в указателе it_after найден P отслеживает последние элементы в каждой подпоследовательности (?)), и если current_value XORed с этим значением из A больше, чем любой предыдущий кандидат (res), затем обновите res с новым большим значением.

Это делает что-то похожее с P_rev,

В заключение...

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

Добавляет индекс current_value в A в P а также P_rev для будущих итераций.

Итак, хотя я не объяснил, почему или как работает алгоритм (я даже не читал формулировку проблемы), я думаю, что это должно прояснить, что делает C++, с чем, как вы сказали, вы боретесь - вы оставайся наедине с собой;-).