Корневая на строках: различия между версиями

Версия 13:18, 18 сентября 2019

Данные идеи очень полезны в задачах, где есть ограничение на суммарный размер строк. Обозначим это ограничение за $\sum |S|$.

Разбиение на тяжелые и легкие строки

Назовем строку $S$ длинной, если $$|S| \ge \sqrt{\sum |S|} $$. Все оставшиеся строки назовем легкими.

Утверждение:
Существует не более $$2 \cdot \sqrt{\sum ''Доказательство:'' Пусть существует более $$2 \cdot \sqrt{\sum

{2} = \sum |S|$$, чего не может быть. }} ===='"`UNIQ--h-1--QINU`"'Количество разных длин==== <div style="margin-left: 5px; border-left: solid 1px black; padding-left: 7px"> ''Утверждение: '' Количество различных длин строк не более, чем $$O(\sqrt{\sum

Доказательство:
Пусть оно равно $$x$$. Тогда минимальная возможная сумма — это сумма чисел от 1 до x. $$\sum_1^x = \frac{x(x + 1)}{2}$$. Так как это число должно быть меньше, чем $$\sum

@@ Строка 2: / Строка 2: @@
 ====Разбиение на тяжелые и легкие строки====
-Назовем строку $S$ длинной, если $|S| \ge \sqrt{\sum |S|} $. Все оставшиеся строки назовем легкими.
+Назовем строку $S$ длинной, если $$|S| \ge \sqrt{\sum |S|} $$. Все оставшиеся строки назовем легкими.
 {{Утверждение
-|Утверждение=Существует не более  $2 \cdot \sqrt{\sum |S|}$ тяжелых строк.
+|Утверждение=Существует не более  $$2 \cdot \sqrt{\sum |S|}$$ тяжелых строк.
-|Доказательство=Пусть существует более $2 \cdot \sqrt{\sum |S|}$ тяжелых строк. Тогда их суммарная длина больше, чем $\frac{2 \cdot \sqrt{\sum |S|} \cdot \sqrt{\sum |S|}}{2} = \sum |S|$, чего не может быть.
+|Доказательство=Пусть существует более $$2 \cdot \sqrt{\sum |S|}$$ тяжелых строк. Тогда их суммарная длина больше, чем $$\frac{2 \cdot \sqrt{\sum |S|} \cdot \sqrt{\sum |S|}}{2} = \sum |S|$$, чего не может быть.
 }}
 ====Количество разных длин====
 {{Утверждение
-|Утверждение=Количество различных длин строк не более, чем $O(\sqrt{\sum |S|})$.
+|Утверждение=Количество различных длин строк не более, чем $$O(\sqrt{\sum |S|})$$.
-|Доказательство=Пусть оно равно $x$. Тогда минимальная возможная сумма — это сумма чисел от 1 до x. $\sum_1^x = \frac{x(x + 1)}{2}$. Так как это число должно быть меньше, чем $\sum |S|$, то $x = O(\sqrt{\sum |S|})$
+|Доказательство=Пусть оно равно $$x$$. Тогда минимальная возможная сумма — это сумма чисел от 1 до x. $$\sum_1^x = \frac{x(x + 1)}{2}$$. Так как это число должно быть меньше, чем $$\sum |S|$$, то $$x = O(\sqrt{\sum |S|})$$
 }}
+[[Категория:Корневые оптимизации]]