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

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

29.09.2013 в 5:30(UTC) состоится September Lunchtime contest, который будет длится 3 часа.

Этот контест проводиться в стиле IOI. Поучаствовать могут все желающие.

Автор задач — Roman Furko.

Более подробную информацию вы можете найти здесь.

Предлагаю после контеста обсудить здесь задачи.

Удачи!

  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

Подозреваю, что этот топик должен был создать автор контеста.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

What's Memory Limit in all tasks?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

The contest is over now. The editorials are being published here: http://discuss.codechef.com/tags/ltime04/

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Подскажите пожалуйста как решать задачу про xor трех чисел

  • »
    »
    13 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Решим задачу, когда нам нужно найти максимальный xor двух чисел за время O(N log N). Будем перебирать одно число и для него искать число с максимальным с ним ксором. Заведем структуру данных бор (префиксное дерево), для хранения чисел в двоичном представлении. Тогда чтобы ответить какое число из бора имеет максимальный ксор с числом K, нужно применить алгоритм : пусть мы стоим в вершине, и из нее есть два ребра 0 и 1, и соответствующий бит числа K равен b, тогда мы идем по ребру b^1 (если оно существует). Когда мы пришли к лист, он соответствует числу, xor с K которого максимален. После этого добавим число K в бор. Теперь легко обобщить задачу, когда у нас нам нужно найти xor 3-ех чисел. Будем перебирать 2 числа (пусть A и B) и искать в боре число с максимальным ксором с A^B. Время : O(N^2 log N)