CF1883B Chemistry

One_JuRuo · 2023-10-23 13:18:40 · 题解

思路

性质题，因为可以随便排序，所以只需要考虑数量满不满足条件即可。

一个回文串，应该满足所有的字符的数量都是偶数或者其中一个字符的数量是奇数。

所以可以直接扫一遍字符串，统计每个字符的数量，然后再统计数量是奇数的个数，如果这个个数大于 k+1 就无解，否则有解。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,m,num[50],ans;
char s[100005];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%s",&n,&m,s+1),ans=0;
        for(int i=1;i<=n;++i) ++num[s[i]-'a'];
        for(int i=0;i<26;++i)
        {
            if(num[i]%2==1) ans++;
            num[i]=0;
        }
        if(ans-1<=m) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}