CF 1624D – Palindromes Coloring(CF 1624D – Palindromes Coloring)

题目链接:

https://codeforces.com/problemset/problem/1624/D

题目大意:

长为 \(n\) 的字符串,有 \(k\) 种颜色,对字符串进行染色,每种颜色都要出现,但不用每个字符都染色。同一种颜色的字符构成要构成一个回文字符串,求能获得的回文子串中最短的长度的最大值。

思路:

先不染色,找到最大的回文子串,然后将回文子串平分成 \(k\) 份,分了之后的回文字串再在中间加入一个字符仍然是回文的,所以再计算除了分好的字符外,剩下的字符是否大于 \(k\),若大于,那么长度可以再加一。

代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
const int mod = 1;
int T, n, k;
string s;
void solve(){
	scanf("%d%d", &n, &k);
	cin >> s;
	vector <int> cnt(26);
	for (char c : s)
		cnt[c - 'a']++;
	int cntP = 0, cntO = 0;
	for (int x : cnt){
		cntP += x / 2;  //计算总的回文子串的长度
		cntO += x % 2;  //计算剩下的字符的数量
	}
	int ans = 2 * (cntP / k);
	cntO += 2 * (cntP % k);
	if (cntO >= k) ans++;  //若满足条件,则答案加一
	cout << ans << "\n"; 
}
int main(){
	cin >> T;
	while(T--)
		solve();
	return 0;
}
————————

< strong > title link: < / strong >

https://codeforces.com/problemset/problem/1624/D

< strong > main idea of the topic: < / strong >

A string with a length of \ (n \) has \ (K \) colors. Color the string. Each color should appear, but not every character. Characters of the same color shall form a palindrome string, and the maximum value of the shortest length in the palindrome substring can be obtained.

< strong > ideas: < / strong >

First, do not dye, find the largest palindrome substring, and then divide the palindrome substring into \ (K \) parts. After dividing the palindrome string, add a character in the middle, which is still palindrome. Therefore, calculate whether the remaining characters are greater than \ (K \) in addition to the divided characters. If greater than, the length can be added by one.

< strong > code: < / strong >

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
const int mod = 1;
int T, n, k;
string s;
void solve(){
	scanf("%d%d", &n, &k);
	cin >> s;
	vector <int> cnt(26);
	for (char c : s)
		cnt[c - 'a']++;
	int cntP = 0, cntO = 0;
	for (int x : cnt){
		cntP += x / 2;  //计算总的回文子串的长度
		cntO += x % 2;  //计算剩下的字符的数量
	}
	int ans = 2 * (cntP / k);
	cntO += 2 * (cntP % k);
	if (cntO >= k) ans++;  //若满足条件,则答案加一
	cout << ans << "\n"; 
}
int main(){
	cin >> T;
	while(T--)
		solve();
	return 0;
}