Всем привет, добро пожаловать на чтениетема codeforces.
Тема выбрана сегодняПоследний вопрос игры Div3, тоже самый сложный вопрос. Основная причина выбора этого вопроса — помочь вам укрепить уверенность, потому что некоторые друзья сказали мне, что вопрос, который я выбрал ранее, был немного сложным, и я чувствовал, что не смогу справиться с вопросом о codeforces. Поэтому сегодня я специально выбрал самую сложную задачу в игре Div3, чтобы придать всем немного уверенности.
Соревнование Div3 — наименее сложное соревнование, оно предназначено для новичков в алгоритме и очень подходит для всех в качестве вводного упражнения. Так как это последний вопрос, количество людей, сдавших этот вопрос, не очень велико, около 530 человек. Но этот вопрос не сложный, я чувствую, что он примерно такой же, как вопрос C в нашем Div2.
Ссылка: https://codeforces.com/contest/1426/problem/F
Без лишних слов, давайте сразу к делу.
смысл названия
Дана строка, содержащая только abc и ?, где ? можно произвольно заменить на a, b или c. Мы предполагаем, что всего их k, так что мы можем получить в общей сложностиразные струны.
Требуется, чтобы все эти строки имели abcпоследующая последовательностьПодпоследовательность относится к подмножеству, полученному путем удаления элементов исходной строки без изменения относительного порядка элементов. Например, baacbc имеет две подпоследовательности abc, которые представляют собой комбинации индексов (2,5,6) и (3,5,6).
Поскольку окончательное число может быть большим, требуется, чтобы этот результатВозьми по модулю.
Образец
Есть две строки ввода, первой строке задано целое число n(), указывающий длину строки. Во второй строке вводится строка длины n, необходимая для возврата количества подпоследовательностей abc.
Пояснение к первому примеру:
отвечать
Эта проблема выглядит более сложной, и не так просто найти решение, чтобы решить ее в лоб. Итак, давайте сначала поставим некоторые условия и начнем с самых простых идей.
минимальный случай
Прежде всего, нам нужно решить задачу, то есть когда нет ?, как нам найти количество подпоследовательностей abc? Например, acabac, как нам найти количество подпоследовательностей abc? Ответ 2, откуда взялась эта 2?
так какЧтобы убедиться, что b появляется после a, а c появляется после b, мы, конечно, можем использовать тройной цикл для перебора всех комбинаций, но это явно не лучший способ. Давайте подумаем об этом, это проблема ограниченных комбинаций.Легко обнаружить, что каждая буква b может быть соединена со всеми a перед ней, чтобы сформировать ab, и каждая буква c также может образовать abc с любой последовательностью ab перед ней. .
Затем мы можем использовать идею динамического программирования для ее решения.Мы используем три переменные d[0], d[1], d[2] для поддержания количества строк a, ab и abc соответственно. Когда мы встречаем a, d[0] увеличивается на 1, а когда мы встречаем b? Добавляет ли d[1] 1? явно не потомуb может образовать ab с каждым предыдущим a, поэтому к d[1] нужно добавить не 1, а d[0]. Точно так же при встрече с c то же самое верно, d[2] следует добавить к d[1].
Это позволяет нам найти количество подпоследовательностей, удовлетворяющих условию без ?.
d = [0, 0, 0]
for i in range(n):
if s[i] == 'a':
d[0] += 1
elif s[1] == 'b':
d[1] += d[0]
else:
d[2] += d[1]
Расширенное использование
Теперь, когда мы решили ситуацию, когда нет ?, что нам делать, если мы добавим ??
Давайте проанализируем это дальше, для каждого ? на самом деле есть три варианта. Например, a?c, после расширения будет три случая aac, abc и acc. Так можем ли мы принять во внимание все три эти ситуации, когда столкнемся с этим?
когда мы встретимсяСкопируйте массив d в три копии, используемый для хранения случаев ?=a, ?=b и ?=c соответственно. Сначала мы копируем массив d в d1, d2 и d3. Мы используем эти три массива для представления трех разных значений и, наконец, объединяем их вместе, чтобы получить новый массив d_new.
Поскольку d1, d2 и d3 на самом деле являются d, мы все еще можем использовать d для их представления после того, как окончательно их проинтегрируем.
Здесь нет никакой проблемы, верно, на самом деле здесь скрыт подвох. Этот трюк очень скрытый и его трудно обнаружить. То есть в случае ?=a наше d1[0] += 1 здесь на самом деле неверно, и мы хотим добавить не 1. Давайте возьмем пример, чтобы понять, например, a??c.
У нас есть два ?s в этой строке.Для первого ?, когда это a, d[0] += 1 не проблема. Но проблема возникает, когда второй — не 1. Мы просто добавили 1, чтобы быть неправильным. Мы также можем понять это в обратном порядке, для первого вопросительного знака мы объединяем три возможности. Когда мы устанавливаем второй вопросительный знак равным a, за первым вопросительным знаком фактически скрываются 3 возможности, поэтому мы хотим добавить здесь не 1, а 3. Что, если у нас есть 3 вопросительных знака? Третий знак вопроса, очевидно, 9. То есть для k-го вопросительного знака.
Этот трюк заметил, то AC это само собой разумеющееся.
n = int(input())
s = input()
ret = 0
Mod = int(1e9+7)
dp = [0, 0, 0]
cnt = 1
for i in range(n):
if s[i] == 'a':
dp[0] += cnt
elif s[i] == 'b':
dp[1] += dp[0]
elif s[i] == 'c':
dp[2] += dp[1]
else:
dp[2] = (3 * dp[2] + dp[1]) % Mod
dp[1] = (3 * dp[1] + dp[0]) % Mod
dp[0] = (3 * dp[0] + cnt) % Mod
cnt = (cnt * 3) % Mod
print(dp[2] % Mod)
Сегодняшний выбор - соревнование div3 с наименьшим количеством людей, прошедших его, что является самым сложным вопросом. Но когда мы это сделаем, мы обнаружим, что на самом деле используется самая основная идея динамического программирования.Хотя придумать решение непросто, сложность на самом деле в порядке.
Поэтому, если вы хотите улучшить свои способности к алгоритмам, но беспокоитесь, что задача слишком сложна для вас, вы можете рассмотреть возможность участия в соревнованиях div3. Поверьте, это будет не слишком сложно.
Вот и все, что касается сегодняшней статьи, и я искренне желаю вам удачи каждый день. Если вам все еще нравится сегодняшний контент, пожалуйста, зайдите на одинТройная поддержкабар~(Нравится, подписывайтесь, делайте репост)