|
|
|
|
|
|
|
| 1 Мисник Андрей Сергеевич, 22 октября 2019 г. 21:27:52 |
| Тут несложная двумерная динамика с bfsом, но пришлось помучаться с памятью и временем. Вначале сделал 3 массива по 9 миллионов unsigned intов - 102 мегабайта, пришлось избавиться от 2 из них - зашло по памяти, но слетало по времени из-за того, что заменил массив на map. Мораль такова: нужно использовать один статичный массив ответа и vector<vector<int>> для хранения графа циклов.
|
|
|
| 2 Винк В В, 22 июня 2019 г. 8:51:32 |
| Весь список циклов можно представить в виде одного или нескольких деревьев. Например цикл, где Li = -4, это потомок цикла номер 4. Можно доказать, что общее количество повторений не зависит от рисунка переплетения деревьев, но всегда равно произведению этих величин от каждого дерева в отдельности. Чтобы найти, сколько раз переменая цикла принимает какое-то конкретное значение, нужно у всех потомков найти сумму тех же величин, начиная с этого значения и до максимального, и перемножить их. В листьях это единицы. Достаточно одного обхода в глубину и общего времени O(N^2).
|
|
|
| 3 Чернышов Андрей Максимович, 29 октября 2018 г. 2:34:27 |
| Не очень сложное двумерное ДП на дереве. Пришлось изучить, как представлять в Java 32-битный беззнаковый тип. Хорошо гуглится по фразе: "Unsigned Integer Arithmetic API".
|
|
|
| 4 Зеленовская Екатерина Сергеевна, 22 августа 2016 г. 19:19:36 |
| Есть ли у кого схема теста, требущего долгих вычислений? 3000 циклов, завязанных на 1м или вложенных считает махом, тем не менее TLE на 6 тесте.
|
|
|
| 5 Прогер, 03 июля 2015 г. 11:20:37 |
| в примере 3 происходит переполнение 32-битового беззнакового типа
|
|
|
| 6 Прогер, 20 июня 2015 г. 22:16:16 |
что-то я пример №3 не понимаю.
кто-нибудь объясните пожайлуста
|
|
|
| 7 Прогер, 20 июня 2015 г. 22:14:10 |
...граница i-го цикла: Li и Ri (1-i <= Li <= 3 000, 0 <= Ri <= 3 000)...
может в скобках не "1-i <= Li ..." а "0-i <= Li..." ?
|
|
|
| 8 Асландуков Матвей Николаевич, 03 июня 2015 г. 14:36:16 |
Не могу понять почему эта задача относится к теме "Рекурсия, перебор"?
На мой взгляд она на Динамическое Программирование
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
