CF1883B

题面

Link

题意：给你一个字符串 $s$，要你删去 $k$ 个字符使得剩下的字符重新组合后可以变成一个回文串。

思路

我们其实就是要用 $s$ 里的字符来构造一个长度为 $n-k$ 的字符串，所以我们用桶记录一下每个字符出现的次数。

假如要构造的回文串长度为偶数，那么我们就把回文串长度除以二，设为 $len$，那么我么就找一下有没有 $len$ 对字符即可（两个相同的字符为一对）。

假如要构造的回文串长度为奇数，那么和偶数的处理方法一样，最后往回文中心随便放个字符即可。

注意特判一下回文串长度为 $1$ 或者为负数的情况。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;

char a[N];
int c[27];

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n, k;
        memset(c, 0, sizeof(c));
        scanf("%d%d", &n, &k);
        scanf("%s", a);
        for(int i = 0; i < n; i++)
        {
            c[a[i] - 'a']++;
        }
        if(k == n - 1)
        {
            cout << "yes" << endl;
            continue;
        }
        else if(k > n - 1)
        {
            cout << "no" << endl;
            continue;
        }
        int len = n - k;
        len /= 2;
        int cnt = 0;
        for(int i = 0; i <= 25; i++)
        {
            cnt += c[i] / 2;
        }
        if(cnt >= len)
        {
            cout << "yes" << endl;
        }
        else cout << "no" << endl;
    }
    return 0;
}