|
|
|
|
|
|
|
Вернуться
| 1 Бабушкин Олег, 17 декабря 2009 г. 21:05:49 | |
|
Забавно) похоже я и вправду намудрил))
|
|
|
| 2 Делюкин Максим Викторович, 17 декабря 2009 г. 6:39:52 | |
Пусть l и r границы текущей подстроки (изначально l = r = 0), давайте двигать правую границу до тех пор пока промежуток от l до r является "паролем".
Двигаем r на 1. Пока строка от l до r НЕ является паролем - двигаем l.
Добавляем к ответу ( r - l ).
Всё.
|7|aaarr +1 = 1
|7a|aarr +2 = 3
|7aa|arr +3 = 6
|7aaa|rr ...
7a|aa|rr +2 = 8
7a|aar|r +3 = 11
7a|aarr| +4 = 15
|a|yay +1 = 1
|ay|ay +2 = 3
|aya|y ...
a|ya|y +2 = 5
a|yay| ...
ay|ay| +2 = 7
Хотелось бы протестировать...
|
|
|
| 3 Бабушкин Олег, 16 декабря 2009 г. 22:54:22 | |
|
Если сможешь сформулировать, буду рад услышать)
|
|
|
| 4 Делюкин Максим Викторович, 16 декабря 2009 г. 18:27:14 | |
Мне кажется для Е есть более простое решение, но очень похожее.
(в смысле там не надо будет учитывать пересечения всякие)
|
|
|
| 5 Бабушкин Олег, 15 декабря 2009 г. 17:21:59 | |
|
Спасибо. ) Про дерево отрезков все понятно.
|
|
|
| 6 Нигматуллин Нияз Габдуллазянович [СПбГУ ИТМО], 15 декабря 2009 г. 10:21:57 | |
|
казалось бы просто разбить на sqrt(n) кусков и изменять по одному в он-лайн точно не получится, либо для этого надо подключать какие-то новые структуры. есть решение с деревом отрезков. сделать дерево отрезков с листьями из m + n элементов, и заполнить последние единичками, для каждого числа 1..n при этом в дереве будет ровно одна единичка, записать в массив индекс каждого числа. Дальше как выполнять запрос. надо посчитать кол-во чисел перед данным числом x. Как это посчитать? Надо найти сумму на отрезке (1, m[x]) где m[x] текущий индекс числа x в массиве. дальше надо обновить дерево. обновим элемент дерева m[x], сделаем его 0. Так как наше число должно встать первым, просто обновим элемент который перед всеми остальными и сделаем его 1. сложность O(M * log(N)). Понятно что дерева нам хватит, потому что не более M раз мы вставим элемент перед всеми остальными элементами.
|
|
|
| 7 Бабушкин Олег, 14 декабря 2009 г. 16:00:36 | |
В задаче Н тернарный поиск (?)
На счет задачи С. Кто нибудь знает, можно ли ее решить за O(n * sqrt(n)), разбив массив на кусочки по sqrt(n) элементов и на каждом шаге изменяя только один из таких кусков?
|
|
|
| 8 Бабушкин Олег, 14 декабря 2009 г. 15:53:46 | |
В "Е" идея следущая.
Пусть f(n) - ответ на задачу для строки из n символов при условии что никакие не повторяются более К раз. (формулу легко вывести).
Пусть l и r границы текущей подстроки (изначально l = r = 0), давайте двигать правую границу до тех пор пока промежуток от l до r является "паролем", придя в положение, когда r сдвинуть больше нельзя, прибавим к ответу f(l - r) и подвинем левую границу на столько, что бы снова можно было двигать правую.
На примере (k = 2) | показаны границы l r. (l = 0, r = 3, прибавляем f(3)), (l = 1, r = 4, прибавляем f(3)), (l = 3, r = 7, +f(4)). Заметим что некоторые кусочки мы посчитали 2 раза (например l = 1, r = 3), удалим их из ответа.
a7aaarrr
|a7a|aarrr
a|7aa|arrr
a7aa|arr|r
...
Думаю общая идея ясна.
|
|
|
| 9 Делюкин Максим Викторович, 14 декабря 2009 г. 1:02:09 | |
C - дерево отрезков... (?)
Е - вообще просто оказывается, линейный алгоритм....
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
