Блог пользователя Oleg

XOR Maximization
Автор Oleg, 14 лет назад, По-русски
Привет

Думаю неделю над такой задачкой, ничего путного в голову не приходит:
Есть  набор чисел (N <= 100000) надо из них выбрать поднабор что бы их XOR был максимальным.

Похинтуйте, пожалуйста :)
  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
:)
http://codeforces.net/blog/entry/1201
→ Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
1. Если взять одно число, и заменить какое-то другое на ксор с первым, то набор ксоров всех подмножеств не изменится. 
2. Возьмем самое большое число. в нем очевидно есть самый старший бит. Заменим все числа в которых есть этот старший бит на ксор с первым числом. Ответ проксорим с нашим самым большим и выкинем его из множества.
3. Будем делать так пока в множестве не останутся один нули.

Казалось бы полученный ответ - искомый максимальный ксор. Если еще для каждого числа помнить из каких чисел начального набора оно состоит, то получим и сам набор. 
→ Ответить
  • 14 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    → Ответить
  • 11 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Прошу прощения за некропостинг, но что-то я не понял. Вот мы заменили все числа со старшм битом на ксор с макимальным числом. И что дальше?

    → Ответить
    • 11 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

      Я так понимаю, что говорим, что ответ xor= это максимальное. Тогда независимо от последующих махинаций старший бит всегда будет 1, поскольку мы выкинем максимальное число из рассмотрения, а во всех остальных этот бит 0.

      → Ответить
      • 11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Этот-то бит 1, а остальные как определить?

        → Ответить
        • 11 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

          Так же. Поскольку все xorы подмножеств остались такими же, то если среди оставшихся чисел следующий за старшим бит у всех 0, значит его нельзя сделать 1, иначе действуем аналогично. Жадник в общем :)

          → Ответить
    • 11 лет назад, # ^ |
      ← Rev. 4   Проголосовать: нравится -10 Проголосовать: не нравится

      deleted.

      → Ответить
      • 11 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        То, что это работает легко показать по индукции. Берем старший бит чисел на отрезке (пусть 2^k). Если на этом отрезке есть число 2^k-1, то ясно что надо брать пару (2^k-1,2^k). Иначе вычтем из всех чисел отрезка 2^k и перейдем к меньшему отрезку.

        За O(1) не знаю, но на O(log(r)) можно. Просто идти по битам, начиная со старшего и действовать аналогично тому, что выше написано.

        → Ответить
      • 11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Киньте ссылку на условие, пожалуйста.

        → Ответить
    • 11 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Если я не ошибаюсь, это метод Гаусса, только по модулю 2?..

      → Ответить