https://acm.khpnets.info/w39/index.php?action=history&feed=atom&title=Codeforces_100971.M 2026-06-02T23:32:55Z История изменений этой страницы в вики MediaWiki 1.39.3 https://acm.khpnets.info/w39/index.php?title=Codeforces_100971.M&diff=2038&oldid=prev 2016-06-08T20:56:01Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 20:56, 8 июня 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l21">Строка 21:</td> <td colspan="2" class="diff-lineno">Строка 21:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* двумя указателями за O(1*).</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* двумя указателями за O(1*).</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Принимаются решения с итоговой асимптотикой не хуже O(n <del style="font-weight: bold; text-decoration: none;">\</del>times; log^2(n)).</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Принимаются решения с итоговой асимптотикой не хуже O(n <ins style="font-weight: bold; text-decoration: none;">&amp;</ins>times; log^2(n)).</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Сборник задач: Codeforces]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Сборник задач: Codeforces]]</div></td></tr> </table>

Ctrlalt https://acm.khpnets.info/w39/index.php?title=Codeforces_100971.M&diff=2036&oldid=prev 2016-06-08T20:49:29Z

<p>Новая страница: «== Ссылка на задачу == * [http://codeforces.com/gym/100971/problem/M Codeforces #100971.M — Разбиение на хорошие строк…»</p> <p><b>Новая страница</b></p><div>== Ссылка на задачу ==<br /> * [http://codeforces.com/gym/100971/problem/M Codeforces #100971.M &amp;mdash; Разбиение на хорошие строки]<br /> <br /> == Комментарии ==<br /> Пусть d[i] &amp;mdash; минимальное количество хороших строк, на которые можно разбить префикс s[0]..s[i].<br /> <br /> Если s[0]..s[i] содержит ровно k различных букв, то d[i] = 1.<br /> <br /> Иначе найдём такое минимальное l &lt;= i и максимальное r &lt;= i, что s[l]..s[i] и s[r]..s[i] содержат k различных букв. Тогда d[i] = 1 + min(d[l - 1]..d[r - 1]).<br /> <br /> Поиск минимума на отрезке можно выполнять деревом отрезков за O(logn).<br /> <br /> Подсчёт количества различных букв на отрезке можно осуществлять:<br /> * 26 бинарными поисками за O(26 &amp;times; logn);<br /> * деревом отрезков отсортированных массивов за O(log^2(n));<br /> * деревом отрезков битовых масок за O(log^2(n)) (лишний логарифм на подсчёт числа единиц в результирующей маске);<br /> * разреженной таблицей битовых масок за O(logn).<br /> <br /> Определение l и r можно осуществлять:<br /> * бинарным поиском за O(logn);<br /> * двумя указателями за O(1*).<br /> <br /> Принимаются решения с итоговой асимптотикой не хуже O(n \times; log^2(n)).<br /> <br /> [[Category: Сборник задач: Codeforces]]<br /> [[Category: Задачи: Динамическое программирование — один параметр]]<br /> [[Category: Задачи: Дерево отрезков]]<br /> [[Category: Задачи: Sparse Table]]<br /> [[Category: Задачи: Бинарный поиск]]<br /> [[Category: Задачи: Два указателя]]</div>

Ctrlalt