Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Сообщения от MBo
Заметил, что вышла бумажная книга Максима https://bhv.ru/product/algoritmicheskij … ython-i-s/
На сайте издательства недоступно, на Озоне есть.
Судя по оглавлению и фрагменту, разделу algo не вполне соответствует, начало похоже на задачник-решебник.
В форум мало заглядывают, но в шапке сайта, Максим, можно было бы прорекламировать?
Это разбиение Ломуто (Lomuto), оно проще, но делает больше обменов и хуже себя ведёт на наборах с большим количество дубликатов.
Вот пример разбора:
http://cs.stackexchange.com/questions/1 … -vs-lomuto
Источник и сток - предопределены, т.к. задача нахождения макс. потока - как раз найти поток из одной заданной вершины (источник) в другую заданную (сток).
В общем случае 2^n-1
>В общем, стоимость даже не важна
Тогда это задача о наборе суммы. Пример: есть по одной монете 1, 3 и 5 копеек. Определить,какие суммы можно набрать. Используем восходящее ДП.
Делаем массив S[] длиной MAXSUM + 1, нулевую ячейку инициализируем единицей, остальные нулями (можно логический тип использовать).
Для каждого числа M[j] пробегаем по массиву S. Встретили ненулевую ячейку с индексом k - пишем единицу в ячейку S[k + M[j]]
Состояние массива после обработки для приведенных данных:
1 1 0 1 1 1 1 0 1 1
Да какой там алгоритм - обойти список и записать в матрицу
См. метод заметающей прямой, книгу Шеймос/Препарата (есть на этом сайте)
алгоритм Бойера-Мура (не тот, что относится к строкам, другой)
Подсказка - сначала разберитесь с более простой задачей - как определить, является ли правильной последовательность левых и правых скобок.
После этого можно решать данную задачу - динамическое программирование, заполнение двумерной таблицы
Рядом подобная задача: http://e-maxx.ru/algo/intersecting_segments
Поиск всех пересечений: http://ru.wikipedia.org/wiki/Алгоритм_Бентли_—_Оттмана
http://www.cs.tufts.edu/comp/163/notes0 … andout.pdf
А что за задача?
Такие задачи обычно решаются методом sweep line (заметающей прямой)
Про арифметику по модулю знаете?
Какой ряд и какое место занимает боец с номером i в первом и во втором случае? (i = 0.. N*M-1)
нужно записать условие математически и прийти к количеству решений ЛДУ на промежутке (с=0, так что будет проще, чем описано для общего случая)
http://e-maxx.ru/algo/export_diofant_2_equation
>помогите
А есть ли смысл помогать человеку, который в двух прошлых темах ответы получил, но не соизволил сделать хотя бы минимальный отклик - понял/не понял?
Два квадрата с координатами (0,0)-(2,2) и (-1,-1)-(1,1). Что должно быть в результате - 1, 3, или 7?
Что есть фигура - объединение, пересечение? Некоторые задачи с наборами прямоугольников рассматриваются в книге Препарата, Шеймос
Точную формулировку условия стоит привести
Ну вот жеж: http://e-maxx.ru/algo/negative_cycle
Полагаю, что нужные символы могут перемежаться ненужными, хотя в задаче и в примерах это явным образом не указано.
Словарь маленький - это хорошо. Заводим два целочисленных массива, индексированных словарём (типа гистограммы). Один Wanted - заполняем из искомой строки (например, для строки aaab он будет выглядеть как [3,1,0,0...]), второй Current. Теперь нам нужно найти минимальное окно, в котором содержатся все символы искомой строки. Пусть два индекса указывают на начало и конец текущего окна. Количество найденных полезных символов Useful := 0
Сдвигаем конец вправо.
с = S[EndIndex]
Если новый символ не из нужных (Wanted[с] = 0), ничего больше не делаем на этом шаге, сдвигаем конец дальше, иначе:
Увеличиваем соответствующий элемент Current[c]
Важный момент: увеличиваем Useful в том случае, если Current[c] не превышает Wanted[с]
Если Useful равно длине искомой строки, то двигаем начало вправо, пока это возможно (т.е. начальный символ не из нужных, или соотв. элемент Current больше Wanted)
Проверяем, минимально ли получившееся окно
Сложность линейная O(Length(A)), память - O(размер словаря)
Неужели информацию по treaps трудно найти?
Здесь в разделе algo
На хабре с картинками
Посмотрите на kd-tree
MAXimal :: φορυμ » Сообщения от MBo