Решение задачи K-полное слово с Codeforces

Без пояснения   Просмотров: 166

Слово s длины n называется k-полным, если

s — палиндром, то есть si=sn+1−i для всех 1≤i≤n;
s имеет период k, то есть si=sk+i для всех 1≤i≤n−k.
Например, «abaaba» — это 3-полное слово, а «abccba» нет.

Бобу вручили слово s длины n, состоящее только из строчных букв латинского алфавита, и целое число k такое, что n делится на k. Он хочет превратить слово s в любое k-полное слово.

Для этого Боб может выбирать некоторую позицию i (1≤i≤n) и заменять букву на позиции i на любую другую строчную букву латинского алфавита.

Поэтому теперь Боба интересует минимальное количество позиций, буквы на которых ему необходимо заменить, чтобы превратить s в любое k-полное слово.

Обратите внимание, что Боб может сделать ноль изменений, если слово s уже k-полное.

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

Код 

#include <bits/stdc++.h>
using namespace std;
int main() {
	int T;
	cin >> T;
	for (int tt = 0; tt < T; ++ tt) {
		int n, k;
		string s;
		cin >> n >> k >> s;
		vector<map<char,int>> c(k);
		vector<int> a(k), b(k);
		for (int i = 0; i < n; ++ i) {
			int j = i % k;
			j = min(j, k-1-j);
			++ a[j];
			b[j] = max(b[j], ++ c[j][s[i]]);
		}
		int r = 0;
		for (int j = 0; j < k; ++ j) {
			r += a[j] - b[j];
		}
		cout << r << endl;
	}
}

         

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




Комментарии

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


© 2020 mycod   [email protected]  Карта сайта   Правообладателям