Решение задачи К-периодичная гирлянда с Codeforces

С пояснением   Просмотров: 869

Вам задана гирлянда, состоящая из n ламп. Состояния ламп описываются строкой s длины n. i-й символ строки si равен '0', если i-я лампа выключена, или '1', если i-я лампа включена. Вам также задано положительное целое число k.

За один ход вы можете выбрать одну лампу и изменить ее состояние (то есть включить ее, если она выключена, и наоборот).

Гирлянда называется k-периодичной, если расстояние между каждой парой соседних включенных ламп равно в точности k. Рассмотрим случай k=3. Тогда гирлянды «00010010», «1001001», «00010» и «0» являются хорошими, а гирлянды «00101001», «1000001» и «01001100» не являются хорошими. Заметьте, что гирлянда не является цикличной, то есть первая включенная лампа не идет после последней включенной лампы и наоборот.

Ваша задача — найти минимальное количество ходов, необходимое для того, чтобы получить k-периодичную гирлянду из заданной.

Вам необходимо ответить на t независимых наборов тестовых данных.

Код 

#include <bits/stdc++.h>

using namespace std;

int main() {
	auto solve = [](const string &s) {
		int n = s.size();
		int all = count(s.begin(), s.end(), '1');
		int ans = all;
		vector<int> res(n);
		int pref = 0;
		for (int i = 0; i < n; ++i) {
			int cur = (s[i] == '1');
			pref += cur;
			res[i] = 1 - cur;
			if (i > 0) res[i] += min(res[i - 1], pref - cur);
			ans = min(ans, res[i] + all - pref);
		}
		return ans;
	};
	
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		string s;
		cin >> n >> k >> s;
		vector<string> val(k);
		int cnt = count(s.begin(), s.end(), '1');
		for (int i = 0; i < n; ++i) {
			val[i % k] += s[i];
		}
		int ans = 1e9;
		for (auto &it : val) ans = min(ans, solve(it) + (cnt - count(it.begin(), it.end(), '1')));
		cout << ans << endl;
	}
	
	return 0;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Пусть t[i] равно строке, содержащей все символы s, имеющие индексы i,i+k,i+2k и так далее (то есть все такие позиции, которые имеют остаток i по модулю k). Допустим, мы выбрали, что все включенные лампы будут иметь остаток i по модулю k. Тогда нам необходимо удалить все единицы на позициях, которые не принадлежат этому остатку. Также, рассматривая строку ti, нам необходимо потратить минимальное количество ходов, чтобы сделать эту строку вида «последовательный блок из нулей, последовательный блок из единиц и еще подин последовательный блок из нулей», потому что рассмотрение символов по модулю k приведет нас именно к такому шаблону (заметьте, что некоторые блоки могут быть пустыми).

Как посчтиать ответ для строки ti за линейное время? Пусть dpi[p] равно количеству ходов, необходимому для того, чтобы исправить префикс ti до p-го символа таким образом, что p-й символ ti равен '1'. Пусть cnt(S,l,r) равно количеству единиц в S на отрезке [l;r]. Заметим, что мы можем посчитать все необходимые значения cnt за линейное время при помощи префиксных сумм. Тогда мы можем посчитать dpi[p] как min(cnt(ti,0,p−1)+[ti[p]≠ ′1′],dpi[p−1]+[ti[p]≠ ′1′]), где [x] равно значению булевого выражения x (1, если x является правдой и 0 в ином случае). Пусть len(s) равно длине s. Тогда настоящий ответ для строки t[i] может быть посчитан как ans[i]=min(cnt(t[i],0,len(t[i])−1),min[p]=0len(ti)−1(dpi[p]+cnt(t[i],p+1,len(t[i])−1))) (таким образом, мы рассмотрели случай, когда получившаяся строка не содержит единиц вообще, и рассмотрели каждую позицию как последнюю позицию какой-то единицы).

Таким образом, настоящий ответ может быть посчитан как mini=0k−1(ans[i]+cnt(s,0,len(s)−1)−cnt(t[i],0,len(t[i])−1)).

Асимптотика решения: O(n).


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp