Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 
[Вернуться к задаче]   1
  1  Парфенов Игорь Андреевич, 21 января 2021 г. 22:26:27
     Разреженная таблица (sparse table) работает за 0.15 секунд.
  2  Дмитриев Дмитрий Андреевич, 29 марта 2020 г. 11:58:48
     Мультисет зашел... А почему ДО ловило TL на 10м тесте так и не понял(
  3  Винк В В, 28 июня 2019 г. 17:58:34
     Решение динамикой здесь несложное. Самое интересное это найти эффективное решение подзадачи : поиск минимальных значений в смежных пересекающихся подмножествах. Заметны сходства с префикс-функцией. Тривиальное решение квадратичное, но с помощью дополнительной структуры данных и небольшого трюка оно становится линейным. Можно использовать мультисет, но это далеко не самый эффективный вариант это лишь O(L*log(L)). К тому же мультисет очень громоздкий и неповоротливый. Нужна двусторонняя очередь, я использовал для неё простой массив и две переменных для хранения идексов начала и конца очереди. Маленькая подсказка, например в очереди стоят числа : 7, 23, 26, 38, 51, 59 и нужно добавить в неё число 44. Для этого сначала удаляем числа 59 и 51, после этого добавляем в конец очереди 44.
  4  Морозов Игорь Олегович, 30 июля 2014 г. 16:24:17
     Зашло O(N*L*log(R)). Когда нужно было ставить новую остановку на какую-то позицию, оптимальную позицию предыдущей остановки выбирал мультисетом. Но пришлось немного пошаманить, чтобы не делать лишних итераций.
  5  Чак Норрис, 05 августа 2011 г. 7:46:07
     Ограничения r и R распространяются так же на расстояние от начала до первой остановки, а так же от последней до конца.
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru