Блог пользователя taras.klaskovsky

XOR maximization[Решена]
Автор taras.klaskovsky, 13 лет назад, По-русски
Находил эту задачу на нескольких тестирующих серверах с задачами, подскажите как решать :)


Спасибо.

upd: АС. Красивое решение. Спасибо всем)
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Думаю здесь надо составить ДП.
По одному вводить числа и учитывать их в сумме или нет.

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Что даст нам после ввода 63 степеней двойки 2^63 возможных вариантов? По-моему, не здорово)
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну понятно, что это либо дп, либо структуры данных :D На геометрию тут не тянет.

    Но что вы предлагаете хранить в дп? Маска это 2^10000, сам ответ это 10^18.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Если найти базис системы векторов, то ответ будет очевиден. Я почти уверен, что это решается с помощью онлайнового Гаусса.
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Да, это похоже на правду. За N*64*64 можно найти базис, в нем не более 64 векторов.

    UPD: Возможно,  я туплю на ночь глядя, только все равно не ясно, как найти ответ даже с 64 векторами.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Тогда может сортировка по убыванию,
после его получаем числа в таком виде:
11001000
11010000
10000100
01110000
01000000
00101000
...............

дальше можно попробовать к числам со старшей единицей подбирать числа со второй единицей, после нахождения максимума искать следующее слагаемое в следующей группе . . .
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Попробовать подбирать это слишком расплывчато. К тому же, нужно не выбрать число с единицей в старшем бите, а выбрать множество чисел с нечетным количеством этих единичных старших битов
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Надо использовать, что a ^ a = 0.

Будем идти от старших разрядов к младшим и набирать ксор числами у кого в самых старших битах - единички. Если для некоторого разряда несколько вариантов, то можно взять одно из чисел, а остальные поксорить с ним, тогда в последующих разрядах мы сможем в случае чего отменить/изменить наш выбор. Например были 3 числа: a, b, c с единичкой в старшем разряде и мы выбрали a (и соответственно поксорили b и c c a -- b ^ a, c ^ a), то на более поздних разрядах мы можем изменить выбор в пользу b поксорив ответ с (b ^ a), так как a ^ (b ^ a) = b. Подобное верно и для более сложного случая, когда например надо выбрать некоторое подмножество из чисел с самой старшей единичкой.

Когда идем от старших к младшим есть два варианта, в ответе уже в этом разряде 
1) стоит единичка: тогда с ним не надо ничего ксорить, но надо также выбрать какое-то число и поксорить с остальными у кого в этом разряде единичка.
2) стоит нолик: тогда любое из чисел с единичкой поксорить с ответом и с остальными числами с единичкой в текущем разряде.

Как-то так.

P.S. такая же задача на acm.sgu.ru: http://acm.sgu.ru/problem.php?contest=0&problem=275
→ Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится
Я ее сдал с помощью Гаусса. Так-то.

Нужно найти базис. Причем ведущим элементом в каждом векторе должен быть старший ненулевой разряд. То есть, для чисел 11 и 3 базис должен быть таким (подчеркнуты ведущие элементы):

1011

0011

А не таким:

0011

1000

Следующее, что нужно сделать, это занулить все столбцы, где есть ведущий элемент:

1000

0011

Ответом является XOR всех векторов базиса, так как:

  1. Это базис. То есть, все вектора, которые можно выразить исходной системой, выражаются и с помощью базиса.
  2. Если мы не возьмем хотя бы один вектор из нашего базиса, то результат будет меньше, чем если бы мы взяли все вектора. Потому что если не взять какой-то вектор, то соответствующий его ведущему элементу старший разряд будет равен нулю, хотя мог бы быть равным единице.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
На зимних сборах 2008ого года в Петрозаводске была такая задача, правда там еще требовалось найти кол-во таких поднаборов что их xor максимален
→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А как делать, если можно взять только фиксированное количество чисел — допустим, k: 1 ≤ k ≤ n?

→ Ответить