Настройки поиска (Страница 4 из 15)

Мне просто очень хотелось продемонстрировать приём с двоичным поиском и вычитанием ответа

За линейное время - наверное, с помощью стека/очереди для минимума? Или есть вариант проще?

Ух ты, выглядит очень круто А набросок идеи можно описать пожалуйста?

Спасибо, "len" вместо "bl" я исправил (извечная проблема, когда копируешь рабочий код, а потом переименовываешь в нём переменные, и в итоге что-нибудь где-нибудь забываешь ).

Насчёт count и len не совсем согласен, т.к. можно их обе присвоить этому числу, так сказать, "с запасом". Последний блок может быть неполным или вовсе пустым (а при n=1 вообще будет и то, и то), однако это ничего не меняет - т.к. к лишним блокам вообще не будет обращений, а неполные блоки тоже ничего не портят.

А реализацию такое соглашение, что количество равно размеру, как-никак упрощает.

Да, в самом деле, так и есть.

По причине высокой нагрузки движка MediaWiki на хостинг, а также того, что википедия на сайте так и не набрала популярности - раздел "wiki" был закрыт.

Та немногая уникальная информация, которая там была - в ближайшее время будет перенесена в статьи раздела /algo/.

вероятно, вы не совсем правильно заполнили сеть?
ответ на этом тесте 2, но если считать рёбра неориентированными - будет 3, но для этого надо будет в матрице c[][] поставить ребро в обоих направлениях (или, во втором варианте, два раза вызвать add_edge)

У меня появилась идея: вы делаете push_back в вектора, и при этом вектор может ресайзиться, в результате пойнтеры rev начинают указывать на не существующие уже структуры.

Программу не изучал, но обычно такие признаки означают, что всё же где-то происходит выход за пределы массивов - например, обращение к минус первому элементу, или что-то в этом роде.

Astekinane
Да, так и есть - мы же не длину отрезка считаем, а число целых точек на отрезке.

Кстати, очень хотелось бы, чтобы кто-нибудь пострессил те решения, которые описаны в статье. У меня нет уверенности, что они абсолютно корректны на всяких вырожденных/отрицательных входных данных.

Ну видимо, да, только эти 6 штук.

Ну да, это я и имел в виду во фразе "меньшие (0;0)" - точки сравниваются как пары двух чисел.

Наверное, более точно будет сказать, что не добавлять в очередь такие точки - ведь перебору передаётся _кандидат_ на добавление в текущую область (хотя, видимо, ты это же имел в виду)

Можно, кстати, написать перебор связных областей так, чтобы он не генерировал повторяющиеся области.

Опишу свою реализацию (пишу по памяти, так что могут быть неточности).

У нас есть очередь кандидатов (изначально в неё добавляется точка (0;0)) - фактически, это точки-окружение текущей связной области в переборе.
Также есть глобальный массив used - в нём мы отмечаем, какие точки мы уже просматривали в текущей ветке перебора (изначально весь used заполнен false, кроме used[0][0] = true).
Перебору передаётся один аргумент - это индекс текущего элемента в очереди, и перебор пробует либо взять этот элемент в текущую область, либо не брать. А если он берёт текущий элемент, то в очередь он добавляет все 4 соседа этой точки, но, конечно, только такие, которые not used (ну и, разумеется, после рекурсивного вызова все добавленные точки надо обратно достать из очереди, сняв с них метку used).

Осталось ещё запретить перебору добавлять точки, меньшие (0;0) - и теперь он точно будет генерировать различные связные области, в которых левая нижняя точка - это точка (0;0).