Сессия 4: задачи
Задачи относятся к темам сессии 4 (см. учебно-тематический план). Каждая задача содержит условие, формат входных и выходных данных, пример и краткую идею решения. Ответы в примерах получены эталонными решениями, которые сверены с перебором на случайных данных.
Битовые операции
Теория — в уроке Битовые операции.
Задача 1. Число, которое встречается один раз
Условие. Дан массив целых неотрицательных чисел. Каждое число в нём встречается ровно два раза, кроме одного, которое встречается ровно один раз. Найдите это число.
Входные данные. В первой строке записано нечётное число $n$ ($1 \le n \le 2 \cdot 10^5$) — длина массива. Во второй строке через пробел записаны $n$ чисел $a_i$ ($0 \le a_i < 2^{31}$).
Выходные данные. Одно число — то, которое встречается ровно один раз.
Пример.
Входные данные: 5 4 1 2 1 2 Выходные данные: 4
Идея решения. Побитовое исключающее ИЛИ (XOR) коммутативно и ассоциативно, и при этом $x \oplus x = 0$, $x \oplus 0 = x$. XOR всех чисел массива равен XOR пар одинаковых чисел (каждая пара даёт $0$) и искомого числа, то есть самому искомому числу. Память $O(1)$, время $O(n)$.
Задача 2. Единицы в двоичной записи чисел от 1 до n
Условие. Найдите суммарное количество единичных битов в двоичных записях всех целых чисел от $1$ до $n$ включительно. Например, для $n = 5$ записи чисел $1, 2, 3, 4, 5$ — это $1$, $10$, $11$, $100$, $101$, и в них $1 + 1 + 2 + 1 + 2 = 7$ единиц.
Входные данные. Одно целое число $n$ ($1 \le n \le 10^{15}$).
Выходные данные. Одно целое число — искомая сумма.
Пример.
Входные данные: 5 Выходные данные: 7
Идея решения. Считаем вклад каждого бита $k$ отдельно. Числа $0, 1, \dots, n$ разбиваются на блоки длины $2^{k+1}$, и в каждом блоке первые $2^k$ чисел имеют $k$-й бит, равный $0$, а следующие $2^k$ — равный $1$. Поэтому количество чисел с единицей в бите $k$ равно $$\Bigl\lfloor \frac{n + 1}{2^{k+1}} \Bigr\rfloor \cdot 2^k + \max\Bigl(0,\ (n + 1) \bmod 2^{k+1} - 2^k\Bigr).$$ Ответ равен сумме этих величин по всем битам $k$ от $0$ до $49$ (так как $n < 2^{50}$). Число $0$ единиц не содержит, поэтому суммирование по $[0, n]$ совпадает с суммированием по $[1, n]$.
Теория графов
Теория — в уроке Деревья и графы. Система непересекающихся множеств.
Задача 3. Число компонент связности
Условие. Граф задан $n$ вершинами, пронумерованными числами от $1$ до $n$, и списком из $m$ рёбер. Найдите количество компонент связности графа, то есть классов вершин, в каждом из которых любые две вершины соединены путём из рёбер.
Входные данные. В первой строке записаны числа $n$ и $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$). В каждой из следующих $m$ строк записаны две вершины $u$ и $v$ ($1 \le u, v \le n$) — концы ребра. Петли (ребро из вершины в неё саму) и кратные рёбра допускаются.
Выходные данные. Одно число — количество компонент связности.
Пример.
Входные данные: 5 2 1 2 2 3 Выходные данные: 3
Компоненты: $\{1, 2, 3\}$, $\{4\}$ и $\{5\}$.
Идея решения. Сначала каждая вершина образует отдельное множество, и компонент ровно $n$. Каждое ребро, соединяющее вершины из разных множеств, объединяет их и уменьшает число компонент на единицу. Ответ равен $n$ минус число успешных объединений. Структура «система непересекающихся множеств» выполняет объединение и запрос о множестве за $O(\alpha(n))$ амортизированно, где $\alpha$ — обратная функция Аккермана; на практике это почти константа.
Задача 4. Дерево или нет
Условие. Дан граф с $n$ вершинами и $m$ рёбрами. Определите, является ли он деревом, то есть связным графом без циклов. Петля и пара рёбер, соединяющих одни и те же две вершины, образуют цикл.
Входные данные. Такие же, как в задаче 3.
Выходные данные. Выведите YES, если граф является деревом, и NO в противном случае.
Пример.
Входные данные: 4 3 1 2 2 3 1 3 Выходные данные: NO
Идея решения. Рёбра добавляются по одному. Если ребро соединяет две вершины, которые уже лежат в одной компоненте, оно замыкает цикл, и ответ NO. Если циклов не было, граф является лесом, и он будет деревом тогда и только тогда, когда компонента одна. В примере ребро $1$–$3$ замыкает цикл $1$–$2$–$3$, а вершина $4$ изолирована.
Алгоритмы на строках
Теория — в уроке Алгоритмы на строках.
Задача 5. Вхождения образца в текст
Условие. Даны текст $t$ и образец $p$. Найдите количество позиций $i$ (нумерация с нуля), таких что подстрока текста длины $|p|$, начинающаяся в позиции $i$, совпадает с $p$. Вхождения могут перекрываться.
Входные данные. В первой строке записан текст $t$, во второй — образец $p$. Обе строки состоят из строчных латинских букв, и выполнено неравенство:
$$1 \le |p| \le |t| \le 2 \cdot 10^5.$$
Выходные данные. Одно число — количество вхождений.
Пример.
Входные данные: abababa aba Выходные данные: 3
Вхождения начинаются в позициях $0$, $2$ и $4$.
Идея решения. Используем алгоритм Кнута — Морриса — Пратта. По образцу строится префикс-функция $\pi_i$: длина наибольшего собственного префикса строки $p_0 \dots p_i$, который одновременно является её суффиксом. Затем проходим по тексту, поддерживая длину $k$ текущего совпадения с образцом. Когда $k = |p|$, фиксируем вхождение и переходим к $k = \pi_{|p|-1}$. Время работы $O(|t| + |p|)$.
Задача 6. Равенство подстрок
Условие. Дана строка $s$ длины $n$ и $q$ запросов. Каждый запрос задаёт два отрезка строки одинаковой длины: $s[l_1 \dots r_1]$ и $s[l_2 \dots r_2]$. Нумерация символов начинается с единицы, концы отрезков входят в них. Для каждого запроса выведите YES, если эти подстроки совпадают, и NO, если не совпадают.
Входные данные. В первой строке записана строка $s$ из строчных латинских букв ($1 \le n \le 2 \cdot 10^5$). Во второй строке записано число $q$ ($1 \le q \le 2 \cdot 10^5$). В каждой из следующих $q$ строк записаны четыре числа $l_1, r_1, l_2, r_2$ ($1 \le l_1 \le r_1 \le n$, $1 \le l_2 \le r_2 \le n$, $r_1 - l_1 = r_2 - l_2$).
Выходные данные. Выведите $q$ строк: для каждого запроса YES или NO.
Пример.
Входные данные: abracadabra 2 1 4 8 11 1 4 5 8 Выходные данные: YES NO
Идея решения. Строим префиксные хеши $H_0 = 0$, $H_i = (H_{i-1} \cdot B + c_i) \bmod M$, где $c_i$ — код $i$-го символа, $B$ — основание, $M$ — большое простое число (например, $2^{61} - 1$). Хеш отрезка вычисляется за $O(1)$: $$h(l, r) = \bigl(H_r - H_{l-1} \cdot B^{\,r - l + 1}\bigr) \bmod M,$$ а степени $B^k$ предвычисляются. Отрезки сравниваются по хешам. Одинаковые хеши у различных строк возможны, но при случайном основании $B$ маловероятны; для надёжности сравнивают два независимых хеша.
Вычислительная геометрия
Теория — в уроке Вычислительная геометрия.
Задача 7. Площадь многоугольника
Условие. Дан простой многоугольник, то есть многоугольник, стороны которого не пересекаются, кроме соседних по обходу. Вершины заданы по порядку обхода границы. Найдите удвоенную площадь многоугольника $2S$; при целых координатах она всегда является целым числом.
Входные данные. В первой строке записано $n$ ($3 \le n \le 10^5$) — число вершин. В каждой из следующих $n$ строк записаны целые координаты $x_i$ и $y_i$ вершины ($|x_i|, |y_i| \le 10^6$).
Выходные данные. Одно целое число — $2S$.
Пример.
Входные данные: 4 0 0 4 0 4 3 0 3 Выходные данные: 24
Прямоугольник $4 \times 3$ имеет площадь $12$, а удвоенная площадь равна $24$.
Идея решения. Используем формулу шнурования: $$2S = \Bigl| \sum_{i=1}^{n} \bigl(x_i y_{i+1} - x_{i+1} y_i\bigr) \Bigr|, \qquad P_{n+1} = P_1.$$ Каждое слагаемое $x_i y_{i+1} - x_{i+1} y_i$ — удвоенная ориентированная площадь треугольника $O P_i P_{i+1}$, где $O$ — начало координат. Сумма даёт удвоенную площадь многоугольника со знаком, а модуль убирает зависимость от направления обхода. Каждое слагаемое по модулю не превосходит $2 \cdot 10^{12}$, поэтому сумма не выходит за пределы $2 \cdot 10^{17}$, и 64-битных целых хватает.
Задача 8. Пересекаются ли отрезки
Условие. На плоскости заданы отрезки $AB$ и $CD$ с целыми координатами; концы каждого отрезка различны. Выясните, есть ли у отрезков хотя бы одна общая точка. Касание концом и совпадение участков на одной прямой тоже считаются пересечением.
Входные данные. В одной строке записаны восемь целых чисел $x_A, y_A, x_B, y_B, x_C, y_C, x_D, y_D$ ($|x|, |y| \le 10^6$) — координаты точек $A$, $B$, $C$ и $D$.
Выходные данные. Выведите YES, если отрезки имеют общую точку, и NO в противном случае.
Пример.
Входные данные: 0 0 4 4 0 4 4 0 Выходные данные: YES
Отрезки пересекаются в точке $(2, 2)$.
Идея решения. Ориентация точки $X$ относительно направленной прямой $PQ$ определяется знаком величины:
$$(Q_x - P_x)(X_y - P_y) - (Q_y - P_y)(X_x - P_x).$$
Пусть $d_1$ и $d_2$ — ориентации точек $A$ и $B$ относительно прямой $CD$, а $d_3$ и $d_4$ — ориентации точек $C$ и $D$ относительно прямой $AB$. Отрезки пересекаются, если выполнено одно из условий: 1) числа $d_1$ и $d_2$ ненулевые и имеют разные знаки, и числа $d_3$ и $d_4$ ненулевые и имеют разные знаки; 2) один из концов одного отрезка лежит на прямой другого отрезка (его ориентация равна нулю) и принадлежит ограничивающему прямоугольнику этого отрезка, то есть лежит на самом отрезке. Сравниваются знаки ориентаций, а не их произведения, чтобы не выйти за пределы 64-битных целых (см. урок Вычислительная геометрия).