1 Тема от Senya

  • Senya
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-01
  • Сообщений: 11

Тема: какая структура данных?

какую структуру данных на массиве лучше взять чтоб быстро выполнять операции типа взять две соседние подстроки ([ai..aj] и [a{j+1} ... ak]) и поменять местами? в просто массиве долго переставлять, а в списке - долго искать iй элемент.. если еще какоето дерево сверху посторить то в нем нада еще чето менять.. вощем чето я не понимаю.

на прошлом 1/4ть финале асма была такая задача - нужно было выполнять много циклических сдвигов подстрок. фактически циклический сдвиг на к - это и есть поменять две соседние подстроки. Мы тогда эту задачу решили на прямую просто классом string - и прокатило.. но жури потом заявило что у них прост почему-то не было большего теста...

2 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: какая структура данных?

про большой тест - смешно smile а какой четвертьфинал?

правильное решение - неявное декартово дерево. оно умеет обменивать два подмассива местами (даже не обязательно соседних). на сайте вроде более-менее описано это.

Сайтe-maxx

3 Ответ от Senya Отредактировано Senya (2010-10-10 20:28:38)

  • Senya
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-01
  • Сообщений: 11

Re: какая структура данных?

год назад Москва..
спасибо. ушел перечитывать декартово дерево

4 Ответ от Oleg

  • Oleg
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-22
  • Сообщений: 86

Re: какая структура данных?

В такой постановке задачи - когда идут только циклические сдвиги на K, нам достаточно иметь один счетчик и прибавлять это K к нему.

5 Ответ от Senya

  • Senya
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-01
  • Сообщений: 11

Re: какая структура данных?

to Oleg - не понял.. какой счетчик? мы делаем сдвиг для подстроки. много запросов. ну разумеется для разных подстрок

такс, на счет декартова дерева.. я правильно понимаю что если нам явным образом не нужны сами приоритеты приоритеты, то они сводятся только к тому чтобы получить "хорошее" дерево, т.е. можно их просто заменить случайным выбором кого к кому прицеплять в операции merge? (ну аналогично системе непересекающихся множеств)

6 Ответ от Oleg

  • Oleg
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-22
  • Сообщений: 86

Re: какая структура данных?

Это я про 1/4финальное условие - "фактически циклический сдвиг на к - это и есть поменять две соседние подстроки"

Для этого условия сместить вначале на a потом на b =   сместить один раз на (a + b) (по модулю)

7 Ответ от Senya

  • Senya
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-01
  • Сообщений: 11

Re: какая структура данных?

а если мы сначала сдвигаем [x1 ... x9] на 5 а потом [x5 ... x23] на 15 ? Я ж говорю разные подстроки сдвигаем. впрочем это уже не важно..