CF 1624D – Palindromes Coloring(CF 1624D – Palindromes Coloring)-其他

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

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

``````#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;
}
``````