XOR Maximization - Codeforces

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

XOR Maximization

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

Привет

Думаю неделю над такой задачкой, ничего путного в голову не приходит:

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

Похинтуйте, пожалуйста :)

problem

Oleg
13 лет назад
15

Комментарии (14)

Показать архивные | Написать комментарий?

CherryTree

13 лет назад, # |

:)
http://codeforces.com/blog/entry/1201

→ Ответить

PavelKunyavskiy

13 лет назад, # |

← Rev. 2 →

1. Если взять одно число, и заменить какое-то другое на ксор с первым, то набор ксоров всех подмножеств не изменится.

2. Возьмем самое большое число. в нем очевидно есть самый старший бит. Заменим все числа в которых есть этот старший бит на ксор с первым числом. Ответ проксорим с нашим самым большим и выкинем его из множества.

3. Будем делать так пока в множестве не останутся один нули.

Казалось бы полученный ответ - искомый максимальный ксор. Если еще для каждого числа помнить из каких чисел начального набора оно состоит, то получим и сам набор.

→ Ответить

CherryTree

13 лет назад, # ^ |

← Rev. 3 →

→ Ответить

Sammarize

10 лет назад, # ^ |

-8

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

→ Ответить

proVIDec

10 лет назад, # ^ |

← Rev. 3 →

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

→ Ответить

Sammarize

10 лет назад, # ^ |

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

→ Ответить

proVIDec

10 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

Sammarize

10 лет назад, # ^ |

Да, действительно. Спасибо)

→ Ответить

robots.txt

10 лет назад, # ^ |

← Rev. 4 →

-10

deleted.

→ Ответить

it4.kp

10 лет назад, # ^ |

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

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

→ Ответить