Codeforce #764 Palindromes Coloring

题目链接

思路

• 首先统计每个字母出现的个数，然后遍历每个字母统计出现的对数，然后用对数除以k就是平均的长度，如果有单个字母出现并且数量大于k的话可以单个字母放到中间 平均长度加1 由于染色后可以互换位置所以不用担心构不成回文串的情况

代码

#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e5+10;
char str[N];
int cnt[30];
int main()
{
    int T;scanf("%d",&T);while(T--){
    int n,k;scanf("%d%d",&n,&k);scanf("%s",str);for(int i=0;str[i];i++)cnt[str[i]-'a']++;int p=0,odd=0;for(int i=0;i<26;i++){
    p+=cnt[i]/2;if(cnt[i]%2)odd++;}int res=2*(p/k);odd+=2*(p%k);if(odd>=k)res++;printf("%d\n",res);memset(cnt,0,sizeof cnt);}
}