Создадим строку s=codeforces. Прочитаем строку t и сравним её с s поэлементно. Посчитаем количество несовпадений и выведем его.

Решение на C++

Решим задачу двумя указателями. Прочитаем все элементы массива. Теперь выставим $$$i$$$ в первый элемент, $$$j$$$ сделаем равным $$$i$$$ и пока $$$a_i = a_j$$$ и не вышли за пределы массива, двигаем $$$j$$$ вправо. Таким образом, мы нашли полуинтервал $$$[i,j)$$$, состоящий только из одинаковых элементов, равных $$$a_i$$$. Если $$$a_i = 0$$$, то обновляем ответ за счёт $$$j-i$$$. Затем ставим $$$i$$$ в позицию $$$j$$$ и повторяем процесс, пока $$$i$$$ не выйдет за пределы массива.

Классическая идея, но на соревновании важно оптимально её реализовать (без багов и быстро). Я всегда использую описанную выше реализацию с двумя циклами по $$$i$$$ и по $$$j$$$.

Решение на C++

Мы либо учим 10 и 01, либо сразу учим 11. Давайте посчитаем минимум среди всех книг с битмасками 01, 10 и 11. Тогда ответ это min(min01 + min10, min11).

Решение на C++

Давайте сразу поделим оба числа на их наибольший общий делитель и будем работать уже с изменёнными числами $$$s$$$ и $$$t$$$. Хотим $$$s$$$ превратить в $$$t$$$.

Каждое действие это:

• либо поделить $$$s$$$ на $$$3$$$;
• либо поделить $$$s$$$ на $$$3$$$ и умножить на $$$2$$$;

Найдём, сколько раз $$$s$$$ и $$$t$$$ делятся на $$$2$$$ и на $$$3$$$. Для этого можно написать функцию и вызвать её $$$4$$$ раза. В самой функции будем делить число до тех пор пока делится.

Теперь мы знаем $$$s_2, s_3, t_2, t_3$$$ — сколько раз данное число делится на $$$2$$$ и на $$$3$$$.

Мы не сможем получить ответ, если в $$$s$$$ и $$$t$$$ есть какие-то другие простые множители (например, множитель $$$5$$$). Давайте проверим это. Если не выполняется:

• $$$s = 2^{s_2} \times 3^{s_3}$$$;
• $$$t = 2^{t_2} \times 3^{t_3}$$$.

То ответа нет. Проверить можно возведением в степень.

Теперь мы будем делить на $$$3$$$, поэтому должно выполняться $$$s_3 \ge t_3$$$. Также мы будем умножать на $$$2$$$, поэтому должно выполняться $$$s_2 \le t_2$$$. Также мы не можем умножить на $$$2$$$ больше раз, чем поделить на $$$3$$$, поэтому должно выполняться $$$t_2-s_2 \le s_3 - t_3$$$. Если всё-всё-всё выполняется, то ответ YES, иначе NO.

Решение на C++

Давайте рассмотрим эту задачу как задачу на графы. Вершины графа — наши клетки на сетке. Ребра графа — переходы вверх, вниз, влево и вправо. На таком графе нам нужно найти компоненты связности. Для каждой компоненты найти сумму чисел в ней. Среди всех компонент найти максимальную сумму и вывести её.

Найти компоненты связности можно при помощи поиска в глубину или в ширину. Сумму для каждой компоненты можно поддерживать, зная номер этой компоненты, и при переходе в ненулевую вершину увеличивать эту сумму, а максимум можно вычислить потом, когда будут посчитаны все значения.

Решение на C++

Давайте найдём центр дерева. Центр — это середина диаметра. Диаметр ищется так:

1. берём вершину $$$1$$$ и запускаем из неё поиск в ширину до всех остальных вершин;
2. знаем расстояния от $$$1$$$ до всех остальных. Находим наиболее удалённую вершину $$$s$$$;
3. берём вершину $$$s$$$ и запускаем из неё поиск в ширину до всех остальных вершин;
4. знаем расстояния от $$$s$$$ до всех остальных. Находим наиболее удалённую вершину $$$t$$$;
5. берём вершину $$$t$$$ и запускаем из неё поиск в ширину до всех остальных вершин;

Итого, величина диаметра, это расстояние от $$$s$$$ до $$$t$$$, которое равно $$$4$$$, а центр — это такая вершина $$$u$$$, у которой distFromS[u] == 2 && distFromT[u] == 2.

Нашли центр. Теперь $$$x$$$ — это размер списка смежности вершины $$$u$$$, а $$$y$$$ — размер списка смежности любого соседа вершины $$$u$$$, вычесть $$$1$$$ (вычитаем ребро в саму вершину $$$u$$$).

Решение на C++

Повернём треугольник на 45 градусов, получим что-то вроде такого (возведения в квадрат опущены):

1 3 6 10
2 5 9
4 8
7

Теперь надо считать сумму в прямоугольнике с правым нижним углом в $$$n$$$, а левым верхним в $$$1$$$. С этим и будем работать.

Оценим число строк и столбцов в нашей матрице. Если мы возьмём её фрагмент из $$$2000$$$ строк и $$$2000$$$ столбцов, то будет примерно $$$2$$$ миллиона элементов, и этого достаточно, чтобы удовлетворить ограничениям, итак, решить можно следующим образом:

Теперь мы готовы отвечать на наш первый запрос и все остальные запросы. Читаем число, вспоминаем, в каком столбце и строке оно лежало, достаём предподсчитанную сумму и выводим её.

Решение на C++

Заметим, что ограничения на $$$a_i$$$ довольно маленькие: всего $$$64$$$ варианта. Также побитовое И варьируется от $$$0$$$ до $$$63$$$ включительно. Давайте посчитаем ответ динамикой dp[n][bitwise_and] — сколько подпоследовательностей на префиксе длины $$$n$$$ имеют побитовое И, равное bitwise_and. Не будем хранить пустую подпоследовательность в динамике, так как она одна такая.

Инициализация динамики: dp[0][0...63] = 0 — на префиксе длины $$$0$$$ нет подпоследовательностей.

Переход: пусть смотрим префикс длины $$$i$$$. Последний элемент на этом префиксе это $$$a_i$$$. Давайте либо добавим его во все подпоследовательности префикса $$$(i-1)$$$, либо не будем добавлять. Для этого переберём, какое побитовое И было у последовательности на предыдущем префиксе, и обновим за счёт значения $$$a_i$$$. Также не забудем, что мы могли взять подпоследовательность с одним $$$a_i$$$, то есть, к пустой подпоследовательности добавить $$$a_i$$$.

Итого:

1. dp[i][0...63] = dp[i-1][0...63] — не добавляем a[i];
2. dp[i][was & a[i]] += dp[i-1][was] для всех was от $$$0$$$ до $$$63$$$ — добавляем a[i];
3. dp[i][a[i]] += 1 — одна подпоследовательность, состоящая лишь из a[i].

Решение