Поиск k-ой в лексикографическом порядке скобочной последовательности: различия между версиями
Материал из Algocode wiki
Глеб (обсуждение | вклад) |
Глеб (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
= Решение = | = Решение = | ||
− | Будем строить нашу последовательность слева направо, как в [[Поиск k-ой в лексикографическом порядке перестановки|перестановках]]. Чтобы узнавать, сколько скобочных последовательностей мы скипнули, поставив ")" вместо "(" нам потребуется[[Количество ПСП с заданным балансом и нужной длиной|динамика, которая возвращает количество ПСП с заданным балансом и нужной длиной]] . | + | Будем строить нашу последовательность слева направо, как в [[Поиск k-ой в лексикографическом порядке перестановки|перестановках]]. Чтобы узнавать, сколько скобочных последовательностей мы скипнули, поставив ")" вместо "(" нам потребуется [[Количество ПСП с заданным балансом и нужной длиной|динамика, которая возвращает количество ПСП с заданным балансом и нужной длиной]] . |
{{Автор|Александр Гришутин|rationalex}} | {{Автор|Александр Гришутин|rationalex}} | ||
[[Категория:Конспект]] | [[Категория:Конспект]] |
Текущая версия на 15:04, 6 февраля 2021
Решение
Будем строить нашу последовательность слева направо, как в перестановках. Чтобы узнавать, сколько скобочных последовательностей мы скипнули, поставив ")" вместо "(" нам потребуется динамика, которая возвращает количество ПСП с заданным балансом и нужной длиной .
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex