Динамика и эффективная обработка данных

Содержание и основные понятия

Для ЕГЭ №27 одного правильного ответа мало: полный перебор пар O(n²) заменяют состоянием, которое обновляется за один проход.
суть и практика
11 класс
ОГЭ №6/16
ЕГЭ №16/17/23–27
01
Как это устроено
Большие данные требуют не только верной формулы, но и правильного объёма работы. Сначала оцени сложность, затем сохрани минимальное состояние, достаточное для следующего шага.
O(n²).
Перебор всех пар быстро становится непригодным на сотнях тысяч значений.
Один проход.
Каждый вход читается один раз; время обычно O(n).
Класс остатка.
При подсчёте пар с суммой, кратной k, достаточно хранить count для k классов остатков.
Префикс.
Накопленная сумма или минимум до текущей позиции заменяет повторный пересчёт отрезка.
02
Один пример в исполнении
Запусти короткую программу и переходи по строкам. Визуализатор показывает только код, текущую строку, переменные и вывод.
В задаче о числе пар с суммой, кратной k, для текущего остатка r нужны все прежние элементы остатка (-r) % k: их количество хранит
count[need]
. Сначала текущий элемент проверяют как правую границу и прибавляют
count[need]
к ответу, затем увеличивают
count[r]
; иначе один элемент образует пару сам с собой. Для другой цели, например максимальной суммы пары, вместо счётчика хранят лучший кандидат класса.
Карта алгоритма
Читай слева направо, затем запускай код.
1
Начало
2
Взять значение
3
Найти его остаток
4
Вычислить нужный предыдущий остаток
5
Использовать класс состояния
03
Запомнить
Сначала проверяй пару с прежними данными, затем обновляй класс текущим элементом.
Определи поведение при отсутствии допустимой пары.
Для ограничения расстояния добавляй элементы в состояние только после нужной задержки.
Синтаксис этой страницы
[None] * k
Создаёт массив k независимых ссылок на неизменяемое None.
value % k
Даёт класс остатка value при k > 0.
(-value) % k
Находит остаток, дополняющий value до кратности k.
max
Обновляет лучший найденный ответ.
is None
Проверяет отсутствие кандидата; не путай с == 0.
for value in values
Один линейный проход по данным.
print
Выводит договорённый ответ; no-solution случай должен быть описан условием.